前順走行（プレオーダー）から二分探索木（BST）を構築する方法 ― C++実装解説

二分探索木（BST）の前順走行（プレオーダートラバーサル）の結果が与えられたとします。この走行結果をもとに、元の木を復元する必要があります。例えば、前順走行が [10, 5, 1, 7, 40, 50] の場合、構築される木は次のようになります。

アルゴリズムの考え方

この問題は、スタックを1つ利用することで線形時間で解くことができます。BSTの性質と前順走行の特徴を組み合わせるのがポイントです。具体的な手順は以下のとおりです。

• 空のスタックを作成します。
• 最初の値を根（ルート）ノードとし、スタックにプッシュします。
• スタックが空でなく、かつ次の値がスタックのトップ要素より大きい間はポップを続けます。最後にポップしたノードの右の子として新しいノードを接続し、その新しいノードをスタックにプッシュします。
• 次の値がスタックのトップ要素より小さい場合は、トップ要素の左の子として新しいノードを接続し、スタックにプッシュします。
• 前順走行リストのすべての要素を処理し終えるまで、上記の手順を繰り返します。

各ノードはスタックに対して高々1回のプッシュと1回のポップしか行われないため、このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) となります。単純な挿入を繰り返す O(n²) の方法と比べて効率的です。

サンプルコード（C++）

#include <iostream>
#include <stack>
using namespace std;
class node {
    public:
    int data;
    node *left;
    node *right;
};
node* getNode (int data) {
    node* temp = new node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
node* constructTree ( int pre[], int size ) {
    stack<node*> stk;
    node* root = getNode( pre[0] );
    stk.push(root);
    int i;
    node* temp;
    for ( i = 1; i < size; ++i ) {
        temp = NULL;
        while ( !stk.empty() && pre[i] > stk.top()->data ) {
            temp = stk.top();
            stk.pop();
        }
        if ( temp != NULL) {
            temp->right = getNode( pre[i] );
            stk.push(temp->right);
        } else {
            node* peek_node = stk.top();
            peek_node->left = getNode( pre[i] );
            stk.push(stk.top()->left);
        }
    }
    return root;
}
void inord (node* node) {
    if (node == NULL)
        return;
    inord(node->left);
    cout << node->data << " ";
    inord(node->right);
}
int main () {
    int pre[] = {10, 5, 1, 7, 40, 50};
    int size = sizeof( pre ) / sizeof( pre[0] );
    node *root = constructTree(pre, size);
    cout << "Inorder traversal: ";
    inord(root);
}

実行結果

Inorder traversal: 1 5 7 10 40 50

出力された中順走行（インオーダートラバーサル）の結果が昇順に並んでいることから、BSTが正しく構築されたことが確認できます。