在 C++ 中使用二叉搜索树对数组进行排序

Question

我正在尝试编写一个对数组的整数元素进行排序的程序，使用二叉搜索树 (BST) 作为支持数据结构。这个想法是，一旦给定了数组，就可以使用 BST 对其元素进行排序；例如：

如果我的数组是：{120, 30, 115, 40, 50, 100, 70}

然后我像这样构建一个 BST：

一旦有了这个 BST，我就可以进行中序树遍历，从最低元素到最高元素按顺序遍历每个节点并修改数组。结果将是一个排序数组 {30, 40, 50, 70, 100, 115, 120}

我写了这段代码，但我不明白我在哪里犯了错误。它编译没有任何错误，但显然有问题：

#include<iostream>
using namespace std;

struct Node
{
    int label;
    Node* left;
    Node* right;
};


void insertSearchNode(Node* &tree, int x)       //insert integer x into the BST
{
    if(!tree){
        tree = new Node;
        tree->label = x;
        tree->right = NULL;
        tree->left = NULL;
        return;
    }
    if(x < tree->label) insertSearchNode(tree->left, x);
    if(x > tree->label) insertSearchNode(tree->right, x);
    return;
}

void insertArrayTree(int arr[], int n, Node* &tree)     //insert the array integer into the nodes label of BST
{
    for(int i=0; i<n; i++){
        insertSearchNode(tree, arr[i]);
    }
    return;
}

int insertIntoArray(int arr[], Node* &tree, int i)      //insert into the array the node label touched during an inorder tree traversal
{
    i=0;
    if(!tree) return 0;
    i += insertIntoArray(arr, tree->left, i) +1;
    arr[i] = tree->label;
    i += insertIntoArray(arr, tree->right, i) +1;
    return i;

}

int main()
{
    Node* maintree;
    maintree = NULL;
    int num;
    cin>>num;
    int arr[num];
    for(int i=0; i<num; i++){    //initialize array with num-elements
     cin>>arr[i];
    }
    insertArrayTree(arr, num, maintree);    //insert elements into BST
    int index;
    insertIntoArray(arr, maintree, index);  //modify array sorting his elements using the BST

    for(int y=0; y<num; y++) cout<< arr[y] << ' ';

    return 0;
}

我希望我的问题足够清楚。任何 help/advice 将不胜感激！

谢谢:)

Answer 1

所以我修改了相当多的代码。首先要注意的是我使用的是 Node** 而不是 Node* &。在处理树和遍历算法时，这是一个非常常见的习惯用法。原因是您需要能够修改传入的指针（我认为这就是您使用 Node* & 的原因，您也可以那样做）。 insertIntoArray 的最大区别在于 int i 变为 int* i，这样每次调用 insertIntoArray 都可以共享相同的递增索引。我还添加了一点内存管理。

我还需要警告您 int arr[num]; 是可变长度数组 (VLA)，不是标准的 C++。 std::vector 是你应该走的路。（事实上它使这个问题更容易，因为你可以很容易地追加）

#include <iostream>

using namespace std;

struct Node
{
    int label;
    Node* left;
    Node* right;

    ~Node() {
      delete left;
      delete right;
    }
};

void insertSearchNode(Node** tree, int x)       //insert integer x into the BST
{
    if (*tree) {
        if (x < (*tree)->label)
            insertSearchNode(&(*tree)->left, x);
        else
            insertSearchNode(&(*tree)->right, x);
    } else {
        *tree = new Node;
        (*tree)->label = x;
        (*tree)->right = NULL;
        (*tree)->left = NULL;
    }
}

void insertArrayTree(int arr[], int n, Node** tree)     //insert the array integer into the nodes label of BST
{
    for (int i = 0; i < n; i++)
        insertSearchNode(tree, arr[i]);
}

void insertIntoArray(int arr[], Node** tree, int* i)      //insert into the array the node label touched during an inorder tree traversal
{
    if (*tree) {
        if ((*tree)->left) insertIntoArray(arr, &(*tree)->left, i);
        arr[(*i)++] = (*tree)->label;
        if ((*tree)->right) insertIntoArray(arr, &(*tree)->right, i);
    }
}

int main()
{
    Node* maintree = NULL;

    int num;
    cin >> num;

    int arr[num];

    for (int i = 0; i < num; i++)    //initialize array with num-elements
        cin >> arr[i];

    insertArrayTree(arr, num, &maintree);    //insert elements into BST
    int index = 0;
    insertIntoArray(arr, &maintree, &index);  //modify array sorting his elements using the BST

    delete maintree;

    for (int y = 0; y < num; y++) 
        cout << arr[y] << ' ';
    cout << '\n';
}

Answer 2

唯一似乎有问题的是insertIntoArray()。

第一个问题是您将单元化变量作为参数传递：

int index;
insertIntoArray(arr, maintree, index);

为什么。您开始从零开始填充数组，因此传递零（并删除索引变量）。

insertIntoArray(arr, maintree, 0);

我无法完全理解你的 insertIntoArray() 版本。不过这个版本好像可以。

int insertIntoArray(int arr[], Node* tree, int i)
{
    // If you fall of a leaf then there is nothing to do.
    // So simply return the index as it has not changed.
    if (!tree) {
        return i;
    }


    // Since it is a BST we always go left first.
    // The return value is where we have reached when we
    // have inserted all the left values. 
    i = insertIntoArray(arr, tree->left, i);

    // Now put the current value in and increment the index position.
    arr[i] = tree->label;
    ++i;

    // Now do the right sub-tree.
    i = insertIntoArray(arr, tree->right, i);

    // Return the point index we have reached so far.
    return i;
}

好的。所以它应该工作。 BUT 这并不意味着这都是好的 C++ 代码。您真的应该审查此代码。

在 C++ 中使用二叉搜索树对数组进行排序

Sorting an array using a Binary Search Tree in C++

c++

sorting

algorithm

computer-science

binary-search-tree