C++で中順・後順走査から前順走査を求める方法

問題の概要

この問題では、ある二分木の中順走査(通りがけ順)と後順走査(帰りがけ順)の結果が与えられます。目的は、これらの情報をもとに木を実際に構築することなく、前順走査(行きがけ順)の結果を求めて出力することです。

問題例

入力:
中順走査: 16 7 21 12 1 5 9
後順走査: 16 21 7 1 9 5 12

出力:
前順走査: 12 7 16 21 5 1 9

この入力から復元される二分木は次のような構造になります。

          12
         /  \
       7      5
      / \    / \
    16   21 1   9

単純なアプローチとその課題

与えられた2つの走査結果から二分木を再構築し、改めて前順走査を実行する方法が考えられます。しかし、この方法では木の構築のために追加のデータ構造と処理が必要になり、計算量・メモリの両面で非効率です。

スタックを使った効率的な解法

より効率的なのが、スタック(stack)データ構造を活用する方法です。ポイントは次の2つの性質です。

• 後順走査の最後の要素は、必ずその木(部分木)の根(root)である。
• 中順走査において、根より前に現れる要素はすべて左部分木に、根より後に現れる要素はすべて右部分木に属する。

これらの性質を利用し、「右部分木 → 左部分木 → 根」の順に再帰的に処理しながらノードの値をスタックに積んでいきます。前順走査は「根 → 左部分木 → 右部分木」の順に訪問するため、スタックのLIFO(後入れ先出し)の性質によって、最後にスタックから要素を取り出すと前順走査の順序どおりに結果が得られます。

アルゴリズムの手順

1. 後順走査の末尾の要素を取り出し、現在の部分木の根とする。
2. その値を中順走査配列内で探索し、位置を特定する。
3. その位置より右側の範囲(右部分木)に対して再帰的に同じ処理を行う。
4. その位置より左側の範囲(左部分木)に対して再帰的に同じ処理を行う。
5. 根の値をスタックにプッシュする。
6. すべてのノードの処理が終わったら、スタックから順にポップして出力する。

C++による実装

#include <iostream>
#include <stack>
using namespace std;

int postIndex;

// 中順走査配列から値の位置を探す
int searchValue(int in[], int data, int n) {
    for (int i = 0; i < n; i++) {
        if (in[i] == data)
            return i;
    }
    return -1;
}

// 後順走査をもとに前順走査を構築する再帰関数
void preOrder(int in[], int post[], int inStart, int inEnd, int n, stack<int>& preorder) {
    if (inStart > inEnd)
        return;

    // 後順走査の末尾の要素が現在の部分木の根
    int val = post[postIndex];
    int inIndex = searchValue(in, val, n);
    postIndex--;

    // 右部分木 → 左部分木 の順に処理
    preOrder(in, post, inIndex + 1, inEnd, n, preorder);
    preOrder(in, post, inStart, inIndex - 1, n, preorder);

    // 根をスタックに積む
    preorder.push(val);
}

void printPreOrderTraversal(int in[], int post[], int n) {
    postIndex = n - 1;
    stack<int> preorder;
    preOrder(in, post, 0, n - 1, n, preorder);

    // スタックから取り出して表示
    while (!preorder.empty()) {
        cout << preorder.top() << " ";
        preorder.pop();
    }
}

int main() {
    int in[]   = { 4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90 };
    int post[] = { 4, 12, 10, 18, 24, 22, 15, 31, 44, 35, 66, 90, 70, 50, 25 };
    int n = sizeof(in) / sizeof(in[0]);

    cout << "木の前順走査の結果:" << endl;
    printPreOrderTraversal(in, post, n);
    return 0;
}

出力結果

木の前順走査の結果:
25 15 10 4 12 22 18 24 50 35 31 44 70 66 90

計算量

• 時間計算量: O(n²) — ノードごとに中順走査配列内の線形探索(O(n))を行うため。
• 空間計算量: O(n) — 結果を保持するスタックと再帰呼び出しのメモリが必要なため。

なお、unordered_map を使って「値 → 中順走査内のインデックス」の対応を事前に構築しておけば探索が O(1) になり、全体の時間計算量を O(n) まで改善できます。