c - 删除二叉搜索树根节点的问题

Question

我正在尝试从 BST 中删除根节点，然后按顺序打印树。根删除似乎是一个问题，所有其他节点都已成功删除。

根号是 20。

订单打印 5 6 7 8 9 10 17 18 20 23 24 25 29 55 56 57 58 59

提供要删除的节点

20

删除后

5 6 7 8 9 10 17 18 20 5 6 7 8 9 10 17 18 23 24 25 29 55 56 57 58 59

正如您所见，删除后，二叉树与预期不符。粗体键是不需要的。 下面是我的代码

void treeDeleteNode (binTreeT **tree, binTreeT *node)
{
    binTreeT *succs;
    binTreeT *parent;
    binTreeT *root = *tree;

    if (node->rchild == NULL) {
        transplantTree (&root, node, node->lchild);
    }
    else if (node->lchild == NULL) {
        transplantTree (&root, node, node->rchild);
    }
    else {
        succs = treeMin (node->rchild);
        parent = getParentNode (root, succs);
        if (parent != node) {
            transplantTree (&root, succs, succs->rchild);
            succs->rchild = node->rchild;
        }
        transplantTree (&root, node, succs);
        succs->lchild = node->lchild;
    }
}


void transplantTree (binTreeT **root, binTreeT *old, binTreeT *new)
{
    binTreeT *rootRef = *root;
    binTreeT *parent;

    parent = getParentNode(rootRef, old);
    if (NULL == parent) {
        *root = new;
    }
    else {
        if (parent->lchild == old) {
            parent->lchild = new;
        }
        else {
            parent->rchild = new;
        }
    }
}


binTreeT* treeMin (binTreeT *tree)
{
    while (tree->lchild != NULL) {
        tree = tree->lchild;
    }
    return tree;
}


binTreeT* getParentNode(binTreeT *root, binTreeT* node)
{
    binTreeT *parent = NULL;

    while (root->data != node->data) {
        parent = root;
        if (node->data < root->data) {
            root = root->lchild;
        }
        else if(node->data > root->data) {
            root = root->rchild;
        }
    }
    return parent;
}


void inOrderPrint (binTreeT *tree)
{
    if (NULL != tree) {
        inOrderPrint (tree->lchild);
        printf("%d \t", tree->data);
        inOrderPrint (tree->rchild);
    }
}

......任何帮助表示赞赏......

Answer 1

在函数 treeDeleteNode 中，每次调用 transplantTree 函数时，都应该将它的 tree 作为第一个参数传递，而不是 &root >。这是因为根节点可以在此函数中修改，并且这些更改应该对 tree 变量本身进行。