c - 从二叉树搜索中删除节点

Question

我认为我的代码中有多个错误，用于从 BST 中删除节点。我就是想不通是什么！这是我的代码。提前致谢！

void del(int val){
    help = root;
    f = help;
    while (help){
        if(help->data==val) break;
        f  = help;
        if (val > help-> data) help = help->right;
        else help = help->left;
    } if(help->data != val) printf("\nElement not found!");
    else{
        printf("Element found!");
        target = help;
        if(val>f->data){
            if(target->right && !target->left) {f->right = target->right; f = target->right;}
            else {f->right = target->left; f = target->left;}
        } else{
            if(target->right && !target->left) {f->left = target->right; f = target->right;}
            else {f->left = target->left; f = target->left;}
        }
        while(help ->right) help = help->right;
        if(help->left) help = help->left;
        f->right = help;
        free(target);
    }
}

Answer 1

我发现的一个错误是，如果要删除树中的左节点，那么最后几行可能不起作用，因为它们不是对称的。因此，假设树的根为 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);
}

Answer 2

typedef struct xxx {
        struct xxx *left;
        struct xxx *right;
        int data;
        } ;
#define NULL (void*)0
#define FREE(p) (void)(p)

void treeDeleteNode1 (struct xxx **tree, int data)
{
    struct xxx *del,*sub;

        /* Find the place where node should be */
    for (       ; del = *tree; tree = (data < del->data) ? &del->left : &del->right ) {
        if (del->data == data) break;
        }
        /* not found: nothing to do */
    if ( !*tree) return;

        /* When we get here, `*tree` points to the pointer that points to the node_to_be_deleted
        ** If any of its subtrees is NULL, the other will become the new root
        ** ,replacing the deleted node..
        */
    if ( !del->left) { *tree = del->right; FREE(del); return; }
    if ( !del->right) { *tree = del->left; FREE(del); return; }

        /* Both subtrees non-empty:
        ** Pick one (the left) subchain , save it, and set it to NULL */
    sub = del->left;
    del->left = NULL;

        /* Find leftmost subtree of right subtree of 'tree' */
    for (tree =  &del->right; *tree; tree =  &(*tree)->left) {;}
        /* and put the remainder there */
    *tree = sub;
    FREE(del);
}

被称为：

...
struct xxx *root;
...
treeDeleteNode1( &root, 42);
...