提问人：johanwww 提问时间：11/10/2023 最后编辑：Armen Michaelijohanwww 更新时间：11/10/2023 访问量：35
为什么我的二叉树删除会删除树的整个左侧部分？
Why does my binary tree deletion remove entire left portion of tree?
问：
我有一个任务，我需要在 C 中实现二叉搜索树。在我尝试为树实现删除函数时，如果要删除的节点在左侧，我未能实现不会删除整个（或几乎整个）树。这是我写的函数：
btree_node *btree_remove(const int x, btree_node *root) {
//if the value cant be found return null;
if (root == NULL) return root;
//search for the node to be deleted
if (x < root->data) {
root->left = btree_remove(x, root->left);
}
if (x > root->data){
root->right = btree_remove(x, root->right);
}
else {
//case when there is no child
if ((root->left == NULL) && (root->right == NULL)) {
free(root);
return NULL;
}
//case when it has one child
else {if (root->right == NULL){
btree_node* temp = root->left;
free(root);
return temp;
}
if (root->left == NULL) {
btree_node* temp = root->right;
free(root);
return temp;
}
}
//case when it has two children
if((root->left != NULL) && (root->right !=NULL)){
btree_node* minNode = findMin(root->right);
root->data = minNode->data;
root->right = btree_remove(minNode->data, root->right);
return root;
}
}
}
我使用插入函数制作的二叉树如下所示：
10
/ \
5 17
/ \
2 NULL
当我尝试删除节点 （5） 时，预期结果是：
10
/ \
2 17
/ \
NULL NULL
使用此函数的结果是：
17
/ \
2 NULL
/ \
NULL NULL
答：
1赞
Lajos Arpad
11/10/2023
#1
你需要有一个--结构。目前，如果为 true（实际上是 5 < 17），则第一个将计算为 ，将被分配给 5（在内部执行和评估之后），然后将是 false（因为 5 > 5 不为真），并且将被错误地执行。ifelse ifelsex < root->dataiftrueroot->leftbtree_removex > root->dataelse
您实际需要的是区分 from，并且像条件一样，块也应该是互斥的：x < root->datax > root->dataelse
if (x < root->data) {
root->left = btree_remove(x, root->left);
}
else if (x > root->data){
root->right = btree_remove(x, root->right);
}
else {
//case when there is no child
if ((root->left == NULL) && (root->right == NULL)) {
free(root);
return NULL;
}
//case when it has one child
else {if (root->right == NULL){
btree_node* temp = root->left;
free(root);
return temp;
}
if (root->left == NULL) {
btree_node* temp = root->right;
free(root);
return temp;
}
}
评论
findMin