免责声明:这是一个任务。我不是要求明确的代码答案,只是帮助理解我的代码为什么不起作用。
我正在尝试实现一个基本的二叉搜索树,但我的_addNode(...)
功能有问题。
这就是问题所在。当我使用调试器浏览我的代码时,我注意到叶节点在两侧(左侧和右侧)无限创建,因此除了创建根之外,叶节点永远不会是NULL
. 问题是我要求我的程序在找到NULL
叶子所在的值时创建一个新节点。因此,如果没有任何NULL
值,就永远不会产生新的叶子,对吧?
我遇到的另一个问题是我的compare(...)
功能。在调试器中单步执行会显示它会多次迭代函数,但实际上从未返回值。当它返回到调用函数时,它又回到compare(...)
函数中并无限循环。同样,考虑到我在每个语句中都有有效的返回语句,我不知道为什么会发生这种情况if
。
这是您可能需要的所有代码。如果我遗漏了什么,请告诉我,我会发布它。
struct Node {
TYPE val;
struct Node *left;
struct Node *right;
};
struct BSTree {
struct Node *root;
int cnt;
};
struct data {
int number;
char *name;
};
int compare(TYPE left, TYPE right)
{
assert(left != 0);
assert(right != 0);
struct data *leftData = (struct data *) left;
struct data *rightData = (struct data *) right;
if (leftData->number < rightData->number) {
return -1;
}
if (leftData->number > rightData->number) {
return 1;
} else return 0;
}
void addBSTree(struct BSTree *tree, TYPE val)
{
tree->root = _addNode(tree->root, val);
tree->cnt++;
}
struct Node *_addNode(struct Node *cur, TYPE val)
{
assert(val != 0);
if(cur == NULL) {
struct Node * newNode = malloc(sizeof(struct Node));
newNode->val = val;
return newNode;
}
if (compare(val, cur->val) == -1) {
//(val < cur->val)
cur->left = _addNode(cur->left, val);
} else cur->right = _addNode(cur->right, val);
return cur;
}
编辑:添加以下功能
int main(int argc, char *argv[])
{
struct BSTree *tree = newBSTree();
/*Create value of the type of data that you want to store*/
struct data myData1;
struct data myData2;
struct data myData3;
struct data myData4;
myData1.number = 5;
myData1.name = "rooty";
myData2.number = 1;
myData2.name = "lefty";
myData3.number = 10;
myData3.name = "righty";
myData4.number = 3;
myData4.name = "righty";
/*add the values to BST*/
addBSTree(tree, &myData1);
addBSTree(tree, &myData2);
addBSTree(tree, &myData3);
addBSTree(tree, &myData4);
/*Print the entire tree*/
printTree(tree);
/*(( 1 ( 3 ) ) 5 ( 10 ))*/
return 1;
}