我发现的一个错误是,如果要删除树中的左节点,那么最后几行可能不起作用,因为它们不是对称的。因此,假设树的根为 6,左子节点为 4,右子节点为 8。现在,您要删除 4。因此,在第一个 while 子句中找到节点后,您将点击"if (val > f->data){" 的 else 子句。此时,f 将指向 6,target 和 help 将指向 4。现在,您将 f 的左侧设置为 target 的右侧,因此 6 的左侧将指向 NULL,而 f 本身将指向 NULL。到目前为止,一切都很好!但是,一旦进入 while 循环,由于 help 没有正确的节点,因此 help 将继续指向 6。最后,您使 f 的正确节点(顺便说一句,此时 f 已经为 NULL)来帮助和你实际上最终会崩溃!
while (help->right)
help = help->right;
if (help->left)
help = help->left;
f->right = help;
另一个错误是您没有更新根指针,以防您最终删除了根节点。
一种更简单的方法是将其分为三种情况。我正在为所有三种情况提供代码。对这三种情况中的每一种都使用示例树,然后对其进行调试/测试。
首先,如果找到的节点(您的文件 while 循环正在执行)没有子节点,则将其删除并将其父节点设置为 NULL,您就完成了。这是第一种情况的粗略切割:
/* If the node has no children */
if (!help->left && !help->right) {
printf("Deleting a leaf node \n");
f = help->parent;
if (f) {
if (value > f->value)
f->right = NULL;
else
f->left = NULL;
}
/* If deleting the root itself */
if (f->value == root) {
root = NULL;
}
free(help);
return 0;
}
其次,如果找到的节点只有子节点(左或右),则将其拼接出来,找到的节点的子节点成为父节点的子节点。这是第二种情况:
/* If the node has only one child node */
if ((help->left && !help->right)
|| (!help->left && help->right)) {
printf("Deleting a node with only one child \n");
f = help->parent;
if (help->left) {
child_node = help->left;
} else {
child_node = help->right;
}
if (f) {
if (value > f->value) {
f->right = child_node;
} else {
f->left = child_node;
}
} else {
/* This must be the root */
root = child_node;
}
free(help);
return 0;
}
第三种情况很棘手——这里找到的节点有两个子节点。在这种情况下,您需要找到该节点的后继节点,然后将找到的节点的值替换为后继节点,然后删除后继节点。这是第三种情况:
/* If the node has both children */
if (help->left && help->right) {
successor_found = find_successor(help, help->data);
printf("Deleting a node with both children \n");
if (successor_found) {
successor_value = successor_found->value;
del(successor_found->value);
help->value = successor_value;
}
return 0;
}
而且,这里是寻找后继者的代码:
binary_node_t *node find_successor(binary_node_t *node, int value) {
binary_node_t *node_found;
if (!node) {return NULL; }
node_found = node;
old_data = node->data;
/* If the node has a right sub-tree, get the min from the right sub-tree */
if (node->right != NULL) {
node = node->right;
while (node) {
node_found = node;
node = node->left;
}
return node_found;
}
/* If no right sub-tree, get the min from one of its ancestors */
while (node && node->data <= old_data) {
node = node->parent;
}
return (node);
}