【データ構造】二分探索木のレベル順走査（Level-Order Traversal）をC++で実装して理解しよう

本記事では、二分探索木（Binary Search Tree）におけるレベル順走査（Level-Order Traversal）の手法について詳しく解説します。レベル順走査は、木の根（ルート）から出発し、上の階層から下の階層へ、同じ深さのノードは左から右の順に訪問していく方法です。この走査は幅優先探索（BFS：Breadth-First Search）とも呼ばれ、木やグラフの探索において非常に重要な基本概念となっています。

例として、次のような二分探索木を考えてみましょう。

この木に対してレベル順走査を実行すると、ノードは次の順序で訪問されます。

10 → 5 → 16 → 8 → 15 → 20 → 23

アルゴリズム

レベル順走査を実現するには、キュー（Queue）というデータ構造を利用します。キューはFIFO（First-In First-Out：先入れ先出し）の性質を持つため、「訪問したノードの子を順番にキューの後ろへ追加する」という操作を繰り返すだけで、自然にレベルごとの処理が行えます。

具体的な手順は、以下の擬似コードの通りです。

levelOrderTraverse(root):
開始
　　ノードを格納するキュー que を定義する
　　根（root）を que に挿入する
　　que が空でない限り、以下を繰り返す
　　　　item := que の先頭にある要素
　　　　item の値を出力する
　　　　もし item の左の子が NULL でなければ
　　　　　　item の左の子を que に挿入する
　　　　もし item の右の子が NULL でなければ
　　　　　　item の右の子を que に挿入する
　　　　que から先頭の要素を削除する
終了

C++による実装例

続いて、C++の標準ライブラリ <queue> を使用した実際のコードを見てみましょう。まず insert_node() 関数で二分探索木を構築し、その後 levelorder_traversal() 関数によってレベル順走査を実行します。

#include<iostream>
#include<queue>
using namespace std;
class node{
   public:
      int h_left, h_right, bf, value;
      node *left, *right;
};
class tree{
   private:
      node *get_node(int key);
   public:
      node *root;
      tree(){
         root = NULL; //最初は根をNULLに設定しておく
      }
      void levelorder_traversal(node *r);
      node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
   node *new_node;
   new_node = new node; //新しいノードを動的に生成
   new_node->h_left = 0; new_node->h_right = 0;
   new_node->bf = 0;
   new_node->value = key; //渡されたキーの値を格納
   new_node->left = NULL; new_node->right = NULL;
   return new_node;
}
void tree::levelorder_traversal(node *root){
   queue <node*> que;
   node *item;
   que.push(root); //まず根をキューに挿入
   while(!que.empty()){
      item = que.front(); //キューの先頭から要素を取得
      cout << item->value << " ";
      if(item->left != NULL) //左の子が存在する場合はキューへ挿入
         que.push(item->left);
      if(item->right != NULL) //右の子が存在する場合はキューへ挿入
         que.push(item->right);
      que.pop(); //処理済みの要素をキューから削除
   }
}
node *tree::insert_node(node *root, int key){
   if(root == NULL){
      return (get_node(key)); //木が空の場合、新規ノードを根として作成
   }
   if(key < root->value){ //キーが根の値より小さい場合は左部分木へ
      root->left = insert_node(root->left, key);
   } else if(key > root->value) { //キーが根の値より大きい場合は右部分木へ
      root->right = insert_node(root->right, key);
   }
   return root; //キーが既に存在する場合は重複して挿入しない
}
main(){
   node *root;
   tree my_tree;
   //木にいくつかのキーを挿入する
   my_tree.root = my_tree.insert_node(my_tree.root, 10);
   my_tree.root = my_tree.insert_node(my_tree.root, 5);
   my_tree.root = my_tree.insert_node(my_tree.root, 16);
   my_tree.root = my_tree.insert_node(my_tree.root, 20);
   my_tree.root = my_tree.insert_node(my_tree.root, 15);
   my_tree.root = my_tree.insert_node(my_tree.root, 8);
   my_tree.root = my_tree.insert_node(my_tree.root, 23);
   cout << "Level-Order Traversal: ";
   my_tree.levelorder_traversal(my_tree.root);
}

出力結果

このプログラムを実行すると、ノードの値がレベル順（上の階層から順に）で出力されます。

Level-Order Traversal: 10 5 16 8 15 20 23

計算量について

レベル順走査の計算量は以下の通りです。

• 時間計算量：O(n) ― 木に含まれる各ノードをちょうど1回ずつ訪問するためです。
• 空間計算量：O(n) ― 最悪の場合（完全二分木など）、最下層のノード数に比例したキュー領域が必要になるためです。

このように、レベル順走査はキューを組み合わせることで、シンプルかつ効率的に実装できる基本的ながら非常に有用な木の走査手法です。深さ優先探索（DFS）との違いも意識しながら、ぜひ実際にコードを書いて動作を確認してみてください。