删除二叉树中的叶节点

Question

我试图从二进制搜索树中删除leaf node，它不适合我，我调试代码，我找不到问题。我可以看到流程正确，调用到达leaf node地址，然后调用free。但在那之后，当我执行pre-order遍历时，我看到价值仍在那里。

我创建的二叉树（它很简单） - ：

                           10
                         /    \
                        6      14

要删除的Leaf Node值= 14;

在删除之前Pre - order遍历结果= 10->6->14。这是打印在我的控制台上的。

删除leaf node的代码 - ：

// Delete a leaf node

void deleteNode(struct Nodes * root,int value){

    // Check if root is null

    if (root == NULL) {
        return;
    }

    // If no left and right node present, it's a leaf node. Perform delete.

    while (root->left == NULL && root->right == NULL) {

        // Check if value at leaf node is same as value to be deleted. If yes, go inside (if).

        if (root->info == value) {
            printf("Delete the leaf node \n");

            printf("delete node address is \n %p",root);

            // free the root (which is currently a leaf node)
            free(root);
            return;
        }
    }

    // keep checking if value to be deleted is on right or left, till a value is found.

    if (root->info < value) {
        // Ccheck on right
        deleteNode(root->right,value);
    }else{
        // check on left
        deleteNode(root->left,value);
    }

}

我没有得到任何errors，所以我无法猜测根本原因。

删除后Pre - order遍历结果= 10->6->14。谁能帮我吗？我知道我犯的是非常愚蠢的错误，或者我的概念仍然不是很清楚。谢谢。

如果需要任何其他信息，请告诉我。

输出图像：您可以看到我的值正确，地址相同。

Answer 1

free几乎意味着“我发誓我不再使用内存，它可能是任意的或任意重新分配”。

你违反了这个承诺。释放内存后，您还必须忘记该地址的所有引用。父节点仍然记住该节点曾经的地址，并且偶然还没有回收内存。

您有一个典型的“免费使用后”错误。如果您之间已经分配了另一个节点，那么在再次遍历之前，您会注意到内存损坏。

您可以向函数添加一个参数，该参数指向父对象中的指针。这样你就可以修改父级了。

或者将引用存储回节点中的父级。

要么有效。

Answer 2

一种方法是将指针传递给递归调用中的父节点。像这样的东西：

void deleteNode(struct Nodes *root, struct Nodes *parent, int value){

    // Check if root is null

    if (root == NULL) {
        return;
    }

    if ((root->info == value) && (root->left == NULL) && (root->right == NULL)) {
        if (parent->left->info == value) {free(parent->left); parent->left = NULL;}
        else {free(parent->right); parent->right = NULL;}
    }
    else if (root->info < value) {
        // check on right
        deleteNode(root->right,root, value);
    }else{
        // check on left
        deleteNode(root->left,root, value);
    }
}