BST - 递归插入
问题描述:
我已经为BST编写了一个递归插入算法。但是,算法中存在一个错误。如果有人可以请给我一个指针,它将不胜感激。在最初的通话中请不要说y = NULL
。BST - 递归插入
void insert_recursive(Node **root, Node *z, Node *y) {
// z is the pointer to the node being inserted, and y keeps track of z's parent
Node *x = *root;
if (x != NULL) {
y = x;
if (z->val < x->val)
insert_recursive(&(x->left), z, y);
else
insert_recursive(&(x->right), z, y);
}
else {
if (y == NULL)
{ *r = z; printf("inserting root, %d\n", z->val); }
else if (z->val < x->val)
{ y->left = z; printf("inserting left of %d, item %d\n", y->val, z->val); }
else
{ y->right = z; printf("inserting right of %d, item %d\n", y->val, z->val); }
}
}
答
它可能不是唯一的问题,但你行
else if (z->val < x->val)
的if (x != NULL)
的else
子句中出现。换句话说,x在这里保证为NULL。
+0
谢谢!是的,我的坏。它应该是'y-> val'不''x-> val'。我会接受你的回答。 – yukon
哪一系列'insert'命令最能证明错误? – sarnold
只有第一个节点作为根插入;该函数然后不传播。谢谢... – yukon
for循环中的调用是.. recursive_insert(&root,z,NULL),其中z是指向正在插入的节点的指针 – yukon