在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;
}

我希望我的问题很清楚。任何帮助/建议将不胜感激！

谢谢：）

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);

为什么您将开始以零填充数组，因此请传递零（并摆脱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 ++代码。您确实应该对此代码进行审查。