C语言 如何使用双指针释放树结构?

Question

我必须释放一棵树并使用特定函数将其根设置为 NULL。我尝试使用一种回溯方法。但是如果我编译，我会收到一些关于"不兼容的指针类型"的警告，我无法解决它。这是结构：

typedef struct node {
int key; 
struct node *left, *mid, *right;
} node_t;

这里是函数。无法更改第一行：

void free_tree (node_t ** root){
if(root != NULL){
free_tree((*root)->left);
free_tree((*root)->mid);
free_tree((*root)->right);
free(*root);
}
return;
}

任何帮助将不胜感激

Answer 1

您的函数需要一个指向节点的指针。你在递归调用中三次给它一个指向节点的指针。此外，您不会验证指针到指针及其指向的指针是否为非 null;你只是在验证前者。

简而言之，您的函数应如下所示：

void free_tree (node_t ** root)
{
if(root && *root)
{
free_tree(&(*root)->left);
free_tree(&(*root)->mid);
free_tree(&(*root)->right);
free(*root);
*root = NULL;
}
}

最后一个功能行是可选的，但坦率地说，除非你无论如何都要这样做，否则使用指针到指针执行此操作是没有意义的，因为它在擦除树后将调用方的指针设置为 NULL。给定正确构建的树，调用方应在销毁整个树时提供树根的地址，如下所示：

node_t *root = NULL;
// ... build tree ...
free_tree(&root);
// root is now NULL; tree is destroyed

Answer 2

你的问题不能回答得很清楚，但至少我可以告诉你为什么你对incompatible pointer type有这个警告：

您的函数原型是

void free_tree (node_t ** root);

它的论点是一个node_t **.

您的结构是

typedef struct node {
int key; 
struct node *left, *mid, *right;
} node_t;

所以在你的函数中：

void free_tree (node_t ** root)
{
if(root != NULL)
{
free_tree((*root)->left);   <<< '(*root)->left' is of type 'node_t *'
free_tree((*root)->mid);    <<< '(*root)->mid' is of type 'node_t *'
free_tree((*root)->right);  <<< '(*root)->right' is of type 'node_t *'
free(*root);
}
return;
}

你调用函数，给出一个node_t *作为参数，而你的函数需要一个node_t **