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;
    }

第一次遍历返回 1,2,3,4,5,6,7。但它在删除 n5 后返回 1,2,3,4,7 进行第二次遍历，这是不正确的，因为它错过了包含的 n6 节点5。我不明白为什么会这样。我在删除函数中插入了一些打印语句，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 的右子节点转移到节点 y。那将是这样的:

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

此时您不需要记住或修改 y 的原始右 child ，因为它已经通过函数 transplant() 处理了。

另一个子传输代码也有类似的问题:

    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。