Как освободить древовидную структуру, используя двойной указатель?

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

Ваша функция ожидала указатель на указатель на узел. Вы даете ему указатель на узел три раза в своих рекурсивных вызовах. Кроме того, вы не проверяете, что указатель на указатель и указатель, на который он указывает, не равны нулю; вы проверяете только первое.

Короче говоря, ваша функция должна выглядеть так:

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 **