C++で学ぶ二分木のレベル順トラバーサル（幅優先探索）の実装方法

二分木が与えられたとき、それをレベル順トラバーサル（Level Order Traversal）、いわゆる幅優先探索（BFS）の手法で走査することを考えます。

例えば、次のような二分木があるとします。

この木に対してレベル順トラバーサルを行うと、ノードは上の階層から左から右へと順番に訪問され、結果は以下のようになります。

[10, 5, 16, 8, 15, 20, 23]

アルゴリズムの手順

この問題を解くためには、キュー（queue）を利用します。手順は以下の通りです。

• ノードを格納するためのキュー que を定義します
• ルートノードをキューに挿入します
• キューが空になるまで、以下の処理を繰り返します
  • キューの先頭にある要素を取り出します
  • その要素の値を出力します
  • 左の子が存在する場合は、左の子をキューに挿入します
  • 右の子が存在する場合は、右の子をキューに挿入します
  • キューの先頭要素を削除します

キューを使うことで、同じ階層のノードを左から右の順序で処理でき、これがまさにレベル順トラバーサルの動作となります。

C++での実装例

それでは、実際のC++コードを見てみましょう。

#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);
}

入力

[10,5,16,null,8,15,20,null,null,null,null,null,null,null,23]

出力

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

まとめ

レベル順トラバーサルは、再帰ではなくキューというデータ構造を活用する点が特徴的です。深さ優先探索（DFS）がスタックや再帰を用いるのに対し、幅優先探索では各階層を順番に処理できるため、木の最小の深さを求める問題や、階層ごとの処理が必要な場面で特に有効です。計算量はノード数を N とすると O(N)、必要なメモリは最悪の場合 O(N) となります。