C++のSTL setを使って二分木を二分探索木（BST）へ変換する方法

与えられた二分木を、元の木の構造をそのまま保ったまま二分探索木（BST：Binary Search Tree）へ変換する方法を解説します。

この解法では、配列を使う従来の手法の代わりに、C++ STL（Standard Template Library）の set コンテナを活用します。

変換例

例1

入力

      11
    /    \
   3      8
 /         \
9           5

出力

      9
    /   \
   5     11
 /         \
3           8

例2

入力

       11
      /   \
    31     16
   /         \
 21           6

出力

       16
      /   \
    11     21
   /         \
  6           31

解法のポイント

• 二分木を中順走査（inorder traversal）しながら、各ノードの値を set に格納します。この処理には O(n log n) の時間がかかります。なお、C++ STL の set は赤黒木や AVL 木といった自己平衡化二分探索木で実装されています。

• set は常に自動的にソートされた状態を保つため、別途ソート処理は不要です。挿入・検索・削除などの各操作もすべて O(log n) で完了します。

• 次に、再び木を中順走査しながら、set の先頭から要素を1つずつ木へ書き戻します。各要素を木にコピーした直後に set から削除することで、常に最小値から順に正しく配置できます。

• 中順走査で昇順に値を埋め込むことで、構造を変えずに BST の性質（左の子 ≤ 親 ≤ 右の子）が自然に満たされます。配列ベースの変換手法と比べても、この方法はシンプルで実装しやすいのが特徴です。

実装コード

以下は、set を使って二分木を二分探索木（BST）へ変換する C++ プログラムです。

/* setコンテナを使って二分木をBSTへ変換するC++プログラム */
#include <bits/stdc++.h>
using namespace std;

struct Node1 {
    int data;
    struct Node1 *left, *right;
};

// 中順走査しながらノードの値をsetへ格納する関数
void storeinorderInSet(Node1* root1, set<int>& s){
    if (!root1)
        return;
    // まず左部分木を訪問
    storeinorderInSet(root1->left, s);
    // setへの挿入はO(logn)
    s.insert(root1->data);
    // 次に右部分木を訪問
    storeinorderInSet(root1->right, s);
} // 計算量 = O(nlogn)

// 中順走査しながらsetの要素を1つずつ木へコピーする関数
void setToBST(set<int>& s, Node1* root1){
    // ベースケース
    if (!root1) return;
    // 先に左部分木へ移動して要素を更新
    setToBST(s, root1->left);
    // setの先頭を指すイテレータ
    auto it = s.begin();
    // ソート済みsetの先頭要素を木へコピー
    root1->data = *it;
    // setから先頭要素を削除
    s.erase(it);
    // 右部分木へ移動して要素を更新
    setToBST(s, root1->right);
}
// 計算量 T(n) = O(nlogn)

// 二分木をBSTへ変換する関数
void binaryTreeToBST(Node1* root1){
    set<int> s;
    // 木の中順走査結果でsetを埋める
    storeinorderInSet(root1, s);
    // setは自己平衡化BSTで実装されているため、
    // デフォルトでソート済みの状態になっている
    // 中順走査しながらsetから木へコピーするとBSTが完成する
    setToBST(s, root1);
}
// 計算量 = O(nlogn)、補助記憶域 = O(n)（set分）

// ノード生成用のヘルパー関数
Node1* newNode(int data){
    // 動的にメモリを確保
    Node1* temp = new Node1();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

// 中順走査を行う関数
void inorder(Node1* root1){
    if (!root1)
        return;
    inorder(root1->left);
    cout<< root1->data << " ";
    inorder(root1->right);
}

int main(){
    Node1* root1 = newNode(6);
    root1->left = newNode(8);
    root1->right = newNode(10);
    root1->right->left = newNode(11);
    root1->left->left = newNode(2);
    root1->left->right = newNode(7);
    root1->right->right = newNode(12);
    /* 以下の図のような木を構築
       6
       / \
       8  10
       /\ / \
       2 7 11 12 */
    // 上記の二分木をBSTへ変換
    binaryTreeToBST(root1);
    cout<< "Inorder traversal of BST is: " << endl;
    inorder(root1);
    return 0;
}

実行結果

Inorder traversal of BST is:
2 6 7 8 10 11 12

BST の中順走査は必ず昇順の並びになるため、上記の出力は変換が正しく行われたことを示しています。

計算量

• 時間計算量： O(n log n)

• 補助記憶域： O(n)（set の格納分）