C二叉查找树删除实现

Question

我正在尝试用 C 实现二叉搜索树的删除功能，但是我运行遇到了问题。

我有以下树和节点结构

typedef struct {
    double value;

    struct Node *parent;
    struct Node *right_child;
    struct Node *left_child;
} Node;

typedef struct {
    struct Node *root;
} Tree;

我还有一个中序遍历函数

void inOrderTraversalNode(Node *n) {

    if (n != NULL) {

        inOrderTraversalNode(n->left_child);
        printf("%f\n", n->value);
        inOrderTraversalNode(n->right_child);
    }
}

一个子树最小函数

Node * minimum(Node *n) {

    while (n->left_child != NULL) {
        n = n->left_child;
    }

    return n;
}

还有移植功能

void transplant(Tree *t, Node *u, Node *v) {

    Node *p = u->parent;

    //replace u's parent's child pointer to v
    if (p == NULL) {
        t->root = v;
    } else if (u == p->left_child) {
        p->left_child = v;
    } else {
        p->right_child = v;
    }

    //set v's parent pointer to u's parent
    if (v != NULL) {
        v->parent = p;
    }
}

终于有了删除功能

void delete(Tree *t, Node *z) {

    //if node z has no left subtree, replace z with right subtree and vice-versa.
    if (z->left_child == NULL) {
        transplant(t, z, z->right_child);

    } else if (z->right_child == NULL) {
        transplant(t, z, z->left_child);
    } else {
        Node *y = minimum(z->right_child);

        if (y->parent != z) {
            transplant(t, y, y->right_child);

            Node *y_right_child = y->right_child;

            y_right_child = z->right_child;
            y_right_child->parent = y;
        }
        transplant(t, z, y);

        Node *y_left_child = y->left_child;

        y_left_child = z->left_child;
        y_left_child->parent = y;
    }

}

但是当我运行下面的代码在main

int main(void) {

        Node n1;
        Node n2;
        Node n3;
        Node n4;
        Node n5;
        Node n6;
        Node n7;
        Node n8;

        n1.value = 4;
        n1.parent = NULL;
        n1.left_child = &n2;
        n1.right_child = &n5;

        n2.value = 2;
        n2.parent = &n1;
        n2.left_child = &n3;
        n2.right_child = &n4;

        n3.value = 1;
        n3.parent = &n2;
        n3.left_child = NULL;
        n3.right_child = NULL;

        n4.value = 3;
        n4.parent = &n2;
        n4.left_child = NULL;
        n4.right_child = NULL;

        n5.value = 6;
        n5.parent = &n1;
        n5.left_child = &n6;
        n5.right_child = &n7;

        n6.value = 5;
        n6.parent = &n5;
        n6.left_child = NULL;
        n6.right_child = NULL;

        n7.value = 7;
        n7.parent = &n5;
        n7.left_child = NULL;
        n7.right_child = NULL;


        Tree t;

        t.root = &n1;

        printf("In order traversal\n");
        inOrderTraversalNode(t.root);

        printf("Delete node\n");
        delete(&t,&n1);
        inOrderTraversalNode(t.root);


        return EXIT_SUCCESS;
    }

它returns1,2,3,4,5,6,7为第一次遍历。但是删除n5后的第二次遍历是returns1,2,3,4,7，这是不正确的，因为它漏掉了包含5的n6节点。我不明白为什么会这样。我在删除函数中插入了一些打印语句，n7 节点将 n6 节点添加为其左子节点，但由于某种原因，它在遍历期间没有被打印出来。

Answer 1

这段代码引起了我的注意：

        Node *y_right_child = y->right_child;

        y_right_child = z->right_child;
        y_right_child->parent = y;

您为变量 y_right_child 赋值，然后您立即将其替换为不同的值。您打算做的，似乎是将节点 z 的权利 child 转移到节点 y。那将是这样的：

        y->right_child = z->right_child;
        y->right_child->parent = y;

此时您无需记住或修改 y 的原始权限 child，因为它已通过函数 transplant() 处理。

其他 child-transfer 代码也存在类似问题：

    Node *y_left_child = y->left_child;

    y_left_child = z->left_child;
    y_left_child->parent = y;

同样，您为变量赋值，然后立即替换它。您似乎真正想要的是：

    y->left_child = z->left_child;
    y->left_child->parent = y;

请注意，因为节点 y 开始时是其子树的最小值，所以您可以确定 y->left_child 最初为 NULL。

Answer 2

就您的代码而言，类型 struct Node 未在任何地方声明或定义。代码顶部的 typedef 无法完成此操作；它定义了一个名为 Node 的不同类型。参见 typedef struct vs struct definitions。这应该会在您的编译中引起大量警告。不要忽视他们！

这似乎也是真正错误的间接原因。在 delete 你有代码

        Node *y_right_child = y->right_child;

        y_right_child = z->right_child;
        y_right_child->parent = y;

这显然是不对的。你想改变 y 的右子指针。但是当你写下你真正想要的东西时：

        y->right_child = z->right_child;
        y->right_child->parent = y;

您遇到错误，因为 y->right_child 属于未定义类型 struct Node *，因此无法取消引用。您没有正确修复此问题，而是引入了局部变量 y_right_child，它至少使代码可以编译。但是，如果代码无法运行，那么编译的代码有什么用呢？分配给 y_right_child 只是改变局部变量的值；它不会更改指针 y->right_child 本身的值。

将第一行更改为 typedef struct Node { 会导致 struct Node 被定义为您想要的（并且 typedef Node 被定义为相同的类型）。然后将 y_right_child 更改为 y->right_child 并完全删除变量 y_right_child，并对 y->left_child 执行相同的操作，删除按预期工作。

C二叉查找树删除实现

C binary search tree deletion implementation

c

algorithm

binary-search-tree