使用 free(N) 删除 BST 中的节点

Question

我正在编写二叉搜索树，但在寻找有效删除节点的方法时遇到了一些麻烦。

我有这段代码：

struct node* deleteNode(int i, struct node *N)

{
    if (N==NULL)
    {
        return NULL;
    }
    else if (i<N->value)
    {
        N->size--;
        N->lChild=deleteNode(i,N->lChild);
    }
    else if (i>N->value)
    {
        N->size--;
        N->rChild=deleteNode(i,N->rChild);
    }
    else if (N->lChild==NULL)
    {
        return N->rChild;
    }
    else if (N->rChild==NULL)
    {
        return N->lChild;
    }
    else
    {
        N->size--;
        N->value=findMin(N->rChild);
        N->rChild=deleteNode(N->value,N->rChild);
    }
    return N;
}

N 是一个节点结构，有 5 个字段：值、lChild、rChild、大小、高度。 事实上，我在这里所做的是使树不指向我想要删除的节点，但是当我尝试放置类似以下内容时：

    else if (N->rChild==NULL)
    {
        free(N);
        N=NULL;
        return N->lChild;
    }

或每个类似的代码，它不起作用。有人可以指出我正确的方向吗？ 谢谢。

Answer 1

首先，您说 N=NULL ，然后调用 N->lchild N 为 null 并指向任何内容，那么您期望如何获得 lchild 值？

由于这是作业，我不会给出直接答案，而是给出提示。

要删除该节点，请检查它是否有子节点，如果没有则释放它并删除对其的引用，例如父节点指针。
如果它有 1 个子节点，则将指向要删除的节点的 ptr 与子节点交换并释放该节点。如果您还有 2 个孩子，同样适用。