0

我正在制作一个二叉搜索树，它具有删除树中所有节点的功能。稍后调用时，似乎所有节点都被删除，但根节点除外。在将条件添加到下面的代码之前，还有其他节点没有被删除。此时已修复，但根节点并未被删除。想知道应该添加哪些条件，或者我是否对根删除不了解。

我尝试了一个不使用条件的更简单的解决方案。程序运行良好，但在最后再次调用遍历后，似乎并非所有内容都被删除了。

TreeNodePtr deleteTree(TreeNodePtr node)
{


    if(node -> left)
    {
        deleteTree(node -> left);
        printf("Deleting node %s \n", node -> left -> data.word);
        free(node -> left);
        node -> left = NULL;
    }

    if(node -> right)
    {
        deleteTree(node -> right);
        printf("Deleting node %s \n", node -> right -> data.word);
        free(node -> right);
        node -> right = NULL;
    }


    if(allocation_count == 1)
    {
        printf("Deleting node %s \n", node -> data.word);
        free(node);
        node = NULL;
    }


    //whenever a node is deleted this decreases by one, when at one  
    //attempt to delete root node
    allocation_count--;

    return node;

}

所有的删除实例都被打印出来，但根实际上并没有从树中删除。在删除过程之后调用遍历时，会保留一个节点值并打印出来。

4

2 回答 2

2

您显示的代码不必要地令人费解，隐藏了微妙的问题。
无论如何，它不能修改传递的参数，因为在 C 中所有参数都是按值传递的。
考虑到您返回 a TreeNode*，调用者可能负责将其分配给根指针。

此外，除非您最多只有一棵树，否则使用全局 forallocationCount是错误的，并且会导致错误。

最后，如果你的树是空的怎么办？

简化的固定代码：

TreeNode* deleteTree(TreeNode* node) {
    if (!node)
        return 0;
    deleteTree(node->left);
    deleteTree(node->right);
    printf("Deleting node %s\n", node->data.word);
    free(node);
    --allocationCount; // Whatever for. Statistics maybe?
    return 0;
}
于 2019-10-27T12:54:54.947 回答
1

您的算法立即从删除左右子树开始，并且不删除根节点。

请记住，树是递归结构，每个子树都有自己的根节点。因此，您应该删除node然后递归调用左右子树。deleteTree

这应该有效：

void deleteTree(TreeNodePtr node)
{
    if(node -> left)
    {
        deleteTree(node -> left);
        node -> left = NULL;
    }

    if(node -> right)
    {
        deleteTree(node -> right);
        node -> right = NULL;
    }

    free(node);
}
于 2019-10-27T12:54:14.300 回答