C言語で木構造（ツリー）を削除する方法｜後順走査を使った実装例

木構造を削除するには？

木（ツリー）を完全に削除するには、木を走査して各ノードにアクセスし、それらを一つずつ解放していく必要があります。すべてのノードを削除し終えると、木は空の状態になります。

このとき重要なのは、必ず子ノードを先に削除してから親ノードを削除するという点です。親ノードを先に解放してしまうと、子ノードへの参照が失われ、メモリリークなどの問題が発生します。そこで、木を「下から上へ」という順序で走査できる手法が必要になります。

後順走査（ポストオーダー走査）が最適な理由

この条件に最も適しているのが後順走査（postorder traversal）です。後順走査は、左右の子部分木をすべて処理した後に根ノードを訪問するため、葉に近いノードから順に安全かつ効率的に削除できます。その結果、余計な複雑さが生じず、プログラム全体を最適な状態に保つことができます。

後順走査におけるノードの訪問順序は次の通りです。

• ① 左の子ノード（左部分木）を走査する
• ② 右の子ノード（右部分木）を走査する
• ③ 最後に根ノードを処理する

例として、次のような二分木を考えてみましょう。この木を後順走査すると、ノードは以下の順序で訪問されます。

2 - 6 - 4 - 12 - 17 - 15 - 9

C言語による実装例

以下は、後順走査を利用して二分木を削除するC言語のサンプルプログラムです。

#include<stdio.h>
#include<stdlib.h>
struct node {
    int data;
    struct node* left;
    struct node* right;
};
struct node* addnode(int data) {
    struct node* node = (struct node*)
        malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return(node);
}
void nodedel(struct node* node) {
    if (node == NULL) return;
    nodedel(node->left);
    nodedel(node->right);
    printf("\n Node deleted, value is %d", node->data);
    free(node);
}
int main() {
    struct node *root = addnode(9);
    root->left = addnode(4);
    root->right = addnode(15);
    root->left->left = addnode(2);
    root->left->right = addnode(6);
    root->right->left = addnode(12);
    root->right->right = addnode(17);
    nodedel(root);
    root = NULL;
    printf("\n Tree deleted ");
    return 0;
}

コードのポイント

• addnode関数： malloc()で新しいノードのメモリを確保し、データを格納したうえで、左右の子ポインタをNULLで初期化します。
• nodedel関数： 再帰的に呼び出され、まず左部分木、続いて右部分木を削除し、最後に自分自身をfree()で解放します。引数がNULLの場合は何もせずに即座にreturnします。
• main関数： サンプル用の二分木を構築し、nodedel(root)を呼び出して全ノードを解放した後、root = NULL を代入して木が空になったことを明示しています。

実行結果

Node deleted, value is 2
Node deleted, value is 6
Node deleted, value is 4
Node deleted, value is 12
Node deleted, value is 17
Node deleted, value is 15
Node deleted, value is 9
Tree deleted

このように、葉に近いノード（2や6など）から順に削除され、最後に根ノード（9）が解放されることがわかります。これはまさに後順走査の特徴であり、子ノードより先に親を消してしまう危険を回避できるため、木の削除には最適な手法といえます。