Namaran

Code daily. Without assist.

2026-09-13

free_tree.c

#include <stdlib.h>

struct node {
    int value;
    struct node *left;
    struct node *right;
};

void free_tree(struct node *t) {
    // write this: free every node of the tree rooted at t
    // (t may be NULL, meaning an empty tree)
}

すべてのノードがmallocで確保された二分木を、1つ残らずfreeするfree_treeを再帰で実装してください。

Reference 
void free_tree(struct node *t) {
    if (t == NULL)
        return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

空の木(NULL)を基底にし、左の部分木、右の部分木を片付けてから最後に自分をfreeします(後行順)。順番が本質で、先にfree(t)してしまうと、その後のt->leftは解放済みメモリの読み出しになります。ループで書こうとすると「まだ片付けていない子」を覚えておく自前のスタックが必要ですが、再帰なら呼び出しスタックがそれを持ってくれるので、木の定義(「空」か「値と2つの部分木」)をそのまま4行に写すだけで済みます。なおfree(NULL)は何もしないと規定されているので、NULLチェックを子の側で行う書き方もありえます。これは参考実装であり、唯一の正解ではありません。