C++でレベル順走査の結果から二分探索木（BST）を構築する方法

レベル順走査（レベル順序トラバーサル）の結果が与えられたとします。この走査結果をもとに、二分探索木（BST：Binary Search Tree）を構築する必要があります。例えば、走査結果が [7, 4, 12, 3, 6, 8, 1, 5, 10] の場合、構築される木は以下の図のようになります。

この問題を解くには、再帰的なアプローチを使用します。レベル順走査の性質上、最初の要素がルートとなり、その後の要素はBSTの条件（左の子は親以下、右の子は親より大きい）に従って順番に挿入されていきます。具体的には、以下の手順で構築を進めます。

• まず、配列の最初の要素を取り出し、これを木のルートとします。
• 次に2番目の要素を取り出します。その値がルート以下であれば左の子に、大きければ右の子として配置します。
• 以降の要素についても同様に、手順2の処理を再帰的に繰り返し適用することで、BST全体を構築します。

アルゴリズムのポイント

各要素を挿入する際には、ルートから出発して値の大小を比較しながら適切な位置まで降りていきます。この操作は木の高さに比例した時間で行えるため、バランスの取れた木であれば平均的に効率的な構築が可能です。

実装例（C++）

#include <iostream>
using namespace std;
class Node {
    public:
    int data;
    Node *left, *right;
};
Node* getNode(int data) {
    Node *newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
Node *lvlOrd(Node *root , int data) {
    if(root==NULL){
        root = getNode(data);
        return root;
    }
    if(data <= root->data)
        root->left = lvlOrd(root->left, data);
    else
        root->right = lvlOrd(root->right, data);
    return root;
}
Node* makeTree(int arr[], int n) {
    if(n==0)
        return NULL;
    Node *root= NULL;
    for(int i=0;i<n;i++)
    root = lvlOrd(root , arr[i]);
    return root;
}
void inord(Node* root) {
    if (!root)
        return;
    inord(root->left);
    cout << root->data << " ";
    inord(root->right);
}
int main() {
    int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    Node *root = makeTree(arr, n);
    cout << "Inorder Traversal: ";
    inord(root);
}

このコードの構成は以下の通りです。

• Node クラス：木の各ノードを表し、データと左右の子ポインタを持ちます。
• getNode 関数：新しいノードを生成して初期化します。
• lvlOrd 関数：BSTのルールに従って、指定された値を適切な位置に再帰的に挿入します。
• makeTree 関数：配列の各要素を順に lvlOrd 関数へ渡し、木全体を構築します。
• inord 関数：中順走査（Inorder Traversal）を行い、結果が昇順にソートされていれば正しくBSTが構築されたことを確認できます。

出力結果

Inorder Traversal: 1 3 4 5 6 7 8 10 12

出力が昇順に並んでいることから、レベル順走査の配列から正しく二分探索木が構築されたことが確認できます。中順走査はBSTを走査すると必ず昇順の結果を得られるため、構築の正しさを検証するのに便利です。