我正在尝试编写一个对数组的整数元素进行排序的程序,使用二叉搜索树(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;
}
我希望我的问题足够清楚。任何帮助/建议将不胜感激!
谢谢 :)
唯一似乎错误的是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] 删除。
我来说两句