C++で二分探索木（BST）を最小ヒープに変換する方法

はじめに

このチュートリアルでは、二分探索木（BST：Binary Search Tree）を最小ヒープ（Min Heap）へ変換するプログラムの実装方法を解説します。

入力として与えられるのは二分探索木です。私たちのタスクは、このBSTを「BST同士で比較した場合の条件」を満たす形で最小ヒープへ変換することです。つまり、元の木の構造（ノードの配置）はそのまま維持しつつ、各ノードに格納する値だけを入れ替えます。

アルゴリズムの考え方

変換は以下の2段階で行います。

1. 中順走査（Inorder Traversal）でBSTの全ノードの値を取得し、配列に格納します。BSTの中順走査は必ず昇順にソートされた結果を返すという性質を利用しています。
2. 次に前順走査（Preorder Traversal）の順序で、配列内の値を各ノードへ書き戻します。

前順走査では「親 → 左の子 → 右の子」の順に訪問するため、ソート済みの値をこの順序で書き込むと、親ノードの値は常に子ノードの値以下になります。これにより、木の構造を保ったまま最小ヒープの条件（親 ≤ 子）を満たすことができます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
// BSTのノード構造体
struct Node {
   int data;
   Node *left, *right;
};
// ノード生成
struct Node* getNode(int data) {
   struct Node *newNode = new Node;
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}
// 前順走査のプロトタイプ宣言
void preorderTraversal(Node*);
// 中順走査で値を昇順に格納する
void inorderTraversal(Node *root, vector<int>& arr) {
   if (root == NULL)
      return;
   inorderTraversal(root->left, arr);
   arr.push_back(root->data);
   inorderTraversal(root->right, arr);
}
// BSTを最小ヒープへ変換
void convert_BSPheap(Node *root, vector<int> arr, int *i) {
   if (root == NULL)
      return;
   root->data = arr[++*i];
   convert_BSPheap(root->left, arr, i);
   convert_BSPheap(root->right, arr, i);
}
// 最小ヒープへの変換処理
void convert_minheap(Node *root) {
   // ノードの値を格納するvector
   vector<int> arr;
   int i = -1;
   // 中順走査を実行
   inorderTraversal(root, arr);
   convert_BSPheap(root, arr, &i);
}
// 前順走査で結果を出力
void preorderTraversal(Node *root) {
   if (!root)
    return;
   cout << root->data << " ";
   preorderTraversal(root->left);
   preorderTraversal(root->right);
}
int main() {
   struct Node *root = getNode(4);
   root->left = getNode(2);
   root->right = getNode(6);
   root->left->left = getNode(1);
   root->left->right = getNode(3);
   root->right->left = getNode(5);
   root->right->right = getNode(7);
   convert_minheap(root);
   cout << "Preorder Traversal:" << endl;
   preorderTraversal(root);
   return 0;
}

実行結果

Preorder Traversal:
1 2 3 4 5 6 7

出力の解説

元のBSTは値1〜7を持つ完全二分木です。まず中順走査によって [1, 2, 3, 4, 5, 6, 7] という昇順の配列が得られます。その後、前順走査の順序（根 → 左部分木 → 右部分木）でこの値を書き戻すため、根には最小値の1が入り、以降も親の値が子の値より小さくなります。

前順走査の出力が 1 2 3 4 5 6 7 となっていることから、すべての親ノードが子ノード以下の値を持つ、正しい最小ヒープへ変換されたことが確認できます。

計算量

• 時間計算量： 中順走査・前順走査ともに各ノードを1回ずつ訪問するため、O(N) です（Nはノード数）。
• 空間計算量： ソート済みの値を保持する配列に O(N)、再帰呼び出しのスタックに最大 O(H)（Hは木の高さ）を使用します。