中順走査（Inorder）と前順走査（Preorder）から後順走査（Postorder）を出力するCプログラム

二分木の中順走査（inorder traversal）と前順走査（preorder traversal）が与えられたとき、それらをもとに後順走査（postorder traversal）を求めて出力するプログラムを作成します。

入力と出力の例

入力:
Inorder traversal in[] = {4, 2, 5, 1, 3, 6}
Preorder traversal pre[] = {1, 2, 4, 5, 3, 6}

出力:
Postorder traversal post[] = {4, 5, 2, 6, 3, 1}

アルゴリズムの考え方

この問題を解く鍵となるのは、各走査の次のような性質です。

• 前順走査（preorder）：最初の要素が必ず木の根（ルート）になる
• 中順走査（inorder）：根の値より左側が左部分木、右側が右部分木に対応する

したがって、前順走査の先頭要素を中順走査内で検索して根の位置を特定すれば、配列を左右の部分木に分割できます。これを再帰的に繰り返し、「左部分木 → 右部分木 → 根」の順で出力することで、後順走査が得られます。

アルゴリズム

開始
ステップ1 → 関数 find_value(int p, int in_order[], int n) を宣言する
    i=0 から i<n の間、i を増やしながら繰り返す
        もし in_order[i] == p ならば
            i を返す
        終了
    終了
ステップ2 → 関数 postorder(int pre_order[], int in_order[], int n) を宣言する
    整数変数 root = find_value(pre_order[0], in_order, n) を宣言する
    もし root != 0 ならば
        postorder(pre_order+1, in_order, root) を呼び出す（左部分木）
    終了
    もし root != n-1 ならば
        postorder(pre_order+root+1, in_order+root+1, n-root-1) を呼び出す（右部分木）
    終了
    pre_order[0] を出力する（根）
終了
ステップ3 → main() へ移動する
    int pre_order[] = {1, 2, 4, 5, 3, 6} を宣言する
    int in_order[] = {4, 2, 5, 1, 3, 6} を宣言する
    int size = sizeof(pre_order)/sizeof(pre_order[0]) を宣言する
    postorder(pre_order, in_order, size) を呼び出す
停止

C言語による実装例

#include <stdio.h>

int find_value(int p, int in_order[], int n) {
    for (int i = 0; i < n; ++i) {
        if (in_order[i] == p) {
            return i;
        }
    }
    return -1;
}

int postorder(int pre_order[], int in_order[], int n) {
    int root = find_value(pre_order[0], in_order, n);
    if (root != 0)
        postorder(pre_order + 1, in_order, root);
    if (root != n - 1)
        postorder(pre_order + root + 1, in_order + root + 1, n - root - 1);
    printf("%d ", pre_order[0]);
}

int main(int argc, char const *argv[]) {
    int pre_order[] = {1, 2, 4, 5, 3, 6};
    int in_order[] = {4, 2, 5, 1, 3, 6};
    int size = sizeof(pre_order) / sizeof(pre_order[0]);
    postorder(pre_order, in_order, size);
    return 0;
}

コードの解説

• find_value()：中順走査の配列から指定された値（根）のインデックスを線形探索で見つけます。このインデックスが部分木の境界になります。
• postorder()：まず根の位置を特定し、左部分木と右部分木に対して再帰的に自分自身を呼び出します。すべての子ノードの処理が完了した後に根の値を出力するため、自然と「左 → 右 → 根」の後順走査の順序になります。
• main()：サンプルデータを用意し、配列サイズを計算してから postorder() を呼び出します。

出力結果

上記のプログラムを実行すると、次の出力が生成されます。

4 5 2 6 3 1

この結果は、期待される後順走査 {4, 5, 2, 6, 3, 1} と一致しており、正しく動作していることが確認できます。