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 %sn", node->data.word);
free(node);
--allocationCount; // Whatever for. Statistics maybe?
return 0;
}

Answer 2

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

记住，树是一个递归结构，每个子树都有自己的根节点。因此，应该删除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);
}