c - 我似乎无法删除 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 时，我仍然会得到我上面发布的顺序打印。如果我从 if(!currPtr->left && !currPtr->right) block 中删除 currPtr = NULL，我将按顺序获得以下内容打印: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;
}