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

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