我有一个任务,需要用C语言实现一个二叉搜索树.在try 实现树的删除函数时,如果要删除的 node 在左侧,我未能实现不删除整个(或几乎整个)树的实现.这是我写的函数:
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;
}
}
}
我使用INSERT函数创建的二叉树如下所示:
10
/ \
5 17
/ \
2 NULL
然后,当我try 删除 node (5)时,预期的结果是:
10
/ \
2 17
/ \
NULL NULL
使用此函数的结果是:
17
/ \
2 NULL
/ \
NULL NULL