先行順走査（プレオーダー）の結果から二分探索木（BST）を構築する ― C++による実装

ある先行順（プレオーダー）走査の結果が与えられているとします。この走査結果をもとに、元の二分探索木（BST）を復元することを考えましょう。例えば、走査結果が [10, 5, 1, 7, 40, 50] である場合、構築される木は次の図のようになります。

解法のアプローチ：範囲制約を利用する

この問題を効率的に解く鍵となるのは、各ノードに対して「取り得る値の範囲 {min … max}」を設定することです。具体的な手順は以下の通りです。

• まず、範囲を {INT_MIN … INT_MAX} として初期化します。
• 最初の要素は必ずこの範囲内に収まるため、その値でルートノードを作成します。
• 左部分木を構築するときは、範囲を {INT_MIN … ルートの値} に更新します。この範囲に収まる値はすべて左部分木に属します。
• 右部分木を構築するときは、範囲を {ルートの値 … INT_MAX} に更新します。

この手法では、配列の各要素を一度だけ処理すればよいため、全体の計算量は O(n) となり、単純に先頭から挿入を繰り返す方法（最悪 O(n²)）よりも大幅に効率的です。

C++での実装例

#include <iostream>
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* makeTreeUtil( int pre[], int* preord_index, int key, int min, int max, int size ) {
    if( *preord_index >= size )
    return NULL;
    node* root = NULL;
    if( key > min && key < max ){
        root = getNode( key );
        *preord_index += 1;
        if (*preord_index < size){
            root->left = makeTreeUtil( pre, preord_index, pre[*preord_index], min, key, size );
            root->right = makeTreeUtil( pre, preord_index, pre[*preord_index],key, max, size );
        }
    }
    return root;
}
node *makeTree (int pre[], int size) {
    int preord_index = 0;
    return makeTreeUtil( pre, &preord_index, pre[0], INT_MIN, INT_MAX, size );
}
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 = makeTree(pre, size);
    cout << "Inorder traversal: ";
    inord(root);
}

出力

Inorder traversal: 1 5 7 10 40 50

出力を見ると、構築した木に対して中間順（インオーダー）走査を行うと、値が昇順に並んで表示されています。これは木が正しく二分探索木として復元できたことを示しています。中間順走査が常にソート済みの順序を返すことは、BSTの重要な性質の一つであり、構築結果の検証手段としても活用できます。