我似乎无法删除C中二进制搜索树上最简单的情况

Question

我去年发布了这个,因为一些大学项目,现在我必须再做一次(我从来没有完成我去年必须做的事情).我已经看过我以前的代码,你们所有人都回答了这些问题,但是,我似乎无法理解这一点.

我不打算把所有问题放在一篇长篇文章中,它只是让一切变得更加混乱,我需要一劳永逸地理解这一点.

我正在使用最简单的BST(只是元素的整数),我正在尝试从树中删除一个节点,它是最简单的演员,删除一个叶子.

我正在测试的树元素按以下顺序插入: 7 3 10 2 5 1 6 9 4 8

当然,顺序打印的输出是: 1 2 3 4 5 6 7 8 9 10

这是我的树结构:

typedef int TreeElement;

typedef struct sTree {
   TreeElement item;

   struct sTree *left;
   struct sTree *right;
} Tree;

这是我的删除功能:

int delete(Tree **tree, TreeElement item) {
    if(!*tree) return 1;

    Tree *currPtr = *tree;
    Tree *prevPtr = NULL;

    while(currPtr) {
        if(item < currPtr->item) {
            prevPtr = currPtr;
            currPtr = currPtr->left;
        } else if(item > currPtr->item) {
            prevPtr = currPtr;
            currPtr = currPtr->right;
        } else {            
            if(!currPtr->left && !currPtr->right) {
                currPtr = NULL;
            }

            free(currPtr);

            return 0;
        }
    }

    return 1;
}

我无法理解为什么但这不起作用...据我所知,我正在寻找正确删除的元素.当我找到它时,通过检查左右子项是否为"空"来检查该节点是否为叶子.它们适用于我的测试用例(尝试删除节点1).

当尝试使用上面的代码删除节点1时,我仍然会按照上面发布的顺序打印.如果我currPtr = NULL从if(!currPtr->left && !currPtr->right)块中删除,我会得到以下顺序打印:0 2 3 4 5 6 7 8 9 10.

我不明白这一点......

我在上面的代码中缺少什么,所以我可以正确删除一个叶子的节点？这是删除BST中节点的最简单的情况,然而,我在做这件事时遇到了很多麻烦,这让我发疯了.

Answer 1

在这种情况下,您将更改保存当前指针的值,而不是指向该节点的节点中的值.你真正想要的是什么

int delete(Tree **tree, TreeElement item) {
if(!*tree) return 1;

Tree *currPtr = *tree;
Tree *prevPtr = NULL;
bool fromLeft = false;

while(currPtr) {
    if(item < currPtr->item) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
        fromLeft = true;
    } else if(item > currPtr->item) {
        prevPtr = currPtr;
        currPtr = currPtr->right;
        fromLeft = false;
    } else {            
        if(!currPtr->left && !currPtr->right) {
            if( fromLeft )
               prevPtr->left = NULL;
            else
               prevPtr->right = NULL;
        }

        free(currPtr);

        return 0;
    }
}

return 1;
}