c - 如何删除根节点作为完整树删除的一部分

Question

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

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

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;

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

Answer 1

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

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

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

简化固定代码:

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;
}