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

维托里奥 A.

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

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

然后我构建了一个这样的 BST:

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

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

谢谢 :)

马丁·约克

唯一似乎错误的是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;
}

行。所以它应该工作。并不意味着这是所有优秀的C ++代码。你真的应该审查这段代码。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章