当二叉搜索树有 2 个子节点时如何删除节点

Question

我正在创造我的第一棵树。看起来我陷入了如何在树有 2 个子节点时从树中删除节点的问题。目前我正在努力：

• 找到中序后继者（右孩子的最左孩子）
• 用它替换要删除的节点
• 然后将后继指向前一个节点所指向的右子节点

但是当我在删除节点后尝试打印树时，它会陷入循环，并最终导致堆栈溢出。

void _rm_node(Node **n, int i)
{
    if (*n == NULL)
    {
        return;
    }

    if (i < (*n)->index)
    {
        _rm_node(&(*n)->left, i);
    }
    else if (i > (*n)->index)
    {
        _rm_node(&(*n)->right, i);
    }
    else
    {
        // no children
        if ((*n)->left == NULL && (*n)->right == NULL)
        {
            free(*n);
            *n = NULL;
        }
        //only left child
        else if ((*n)->left && (*n)->right == NULL)
        {
            Node *tmp = *n;
            *n = (*n)->left;
            free(tmp);
        }
        //only right child
        else if ((*n)->left == NULL && (*n)->right)
        {
            Node *tmp = *n;
            *n = (*n)->right;
            free(tmp);
        }
        else
        //2 children, replace n with inorder successor
        //right tree's leftmost/lowest index
        {
            Node *tmp = *n;
            Node *successor = (*n)->right;
            while (successor->left)
            {
                successor = successor->left;
            }

            *n = successor;
            (*n)->left = tmp->left;
            if (tmp->right->index != successor->index)
            {
                (*n)->right = tmp->right;
            }
            else
            {
                (*n)->right = NULL;
            }
            free(tmp);
        }
    }
}

void PrintTree(Node *t)
{
    if (t == NULL)
    {
        return;
    }
    printf("tree %d\n", t->index);
    PrintTree(t->left);
    PrintTree(t->right);
}

Answer 1

1. 您需要更新继承者的父级。 (a) 如果父节点是您正在编写的节点，则没问题，否则 (b) 您需要找到该指针

   prev

   。

2. *n = successor

   有点繁琐，因为您只需要覆盖

   index

   ，并且在情况下 (a) 是正确的指针。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    struct Node *left;
    struct Node *right;
    int index;
} Node;

Node *BuildTree(size_t n, int indices[n]);
void RemoveNode(Node **n, int i);

void PrintTree(Node *n) {
    if(!n) return;
    printf("tree %d\n", n->index);
    PrintTree(n->left);
    PrintTree(n->right);
}

void RemoveNode(Node **n, int i) {
    if (*n == NULL)
        return;
    if (i < (*n)->index) {
        RemoveNode(&(*n)->left, i);
        return;
    }
    if (i > (*n)->index) {
        RemoveNode(&(*n)->right, i);
    } else {
        // no children
        if ((*n)->left == NULL && (*n)->right == NULL)
        {
            free(*n);
            *n = NULL;
        }
        //only left child
        else if ((*n)->left && (*n)->right == NULL)
        {
            Node *tmp = *n;
            *n = (*n)->left;
            free(tmp);
        }
        //only right child
        else if ((*n)->left == NULL && (*n)->right)
        {
            Node *tmp = *n;
            *n = (*n)->right;
            free(tmp);
        }
        else
        {
            //2 children, replace n with inorder successor
            //right tree's leftmost/lowest index
            Node *prev = *n;
            Node *successor = (*n)->right;
            for(; successor->left; prev = successor, successor = successor->left);
            (*n)->index = successor->index;
            if(*n == prev)
                (*n)->right = successor->right;
            else
                prev->left = successor->right;
            free(successor);
        }
    }
}

Node *InsertNode(Node *root, int index) {
    Node *n = calloc(1, sizeof *n);
    n->index = index;
    if(!root)
        return n;
    Node **p = &root;
    while(*p) {
        if(index <= (*p)->index)
            p = &(*p)->left;
        else
            p = &(*p)->right;
    }
    *p = n;
    return root;
}

Node *BuildTree(size_t n, int indices[n]) {
    if(!n) return NULL;
    Node *t = NULL;
    for(size_t i = 0; i < n; i++)
        t = InsertNode(t, indices[i]);
    return t;
}

int main(void) {
    Node *a = BuildTree(5, (int []) {10, 6, 2, 7, 9});
    printf("Before:\n\n");
    PrintTree(a);
    RemoveNode(&a, 6);
    printf("\n\nAfter:\n\n");
    PrintTree(a);

    Node *b = BuildTree(6, (int []) {10, 6, 2, 8, 7, 9});
    printf("\n\nBefore:\n\n");
    PrintTree(b);
    RemoveNode(&b, 6);
    printf("\n\nAfter:\n\n");
    PrintTree(b);
}