C++で二分木のレベル順走査（幅優先探索）を行ごとに出力する方法

二分木が与えられたとき、そのレベル順走査（幅優先探索）の結果を、レベル（行）ごとに表示する関数をC++で実装します。

レベル順走査とは、木の最上位（ルート）から開始し、同じ深さにあるノードを左から右へ順に訪問していく手法です。上の階層から下の階層へと処理を進め、各レベルの出力を1行として表示していきます。

問題の例

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

          3
         / \
        2   1
       / \    \
      10  20   30

この二分木に対してレベル順走査を行うと、次のような出力が得られます。

Level 0: 3
Level 1: 2 1
Level 2: 10 20 30

アルゴリズム

レベルごとに区切って出力するためのポイントは、キュー（queue）を使い、「現在のレベルに含まれるノード数」を記録しながら処理を進めることです。手順は以下の通りです。

START
Step 1 -> ノード構造体を作成する
    struct node
        struct node *left, *right
        int data
    End
Step 2 -> ノードを生成する関数
    node* newnode(int data)
    node *temp = new node
    temp->data = data
    temp->left = temp->right = NULL
    return temp
Step 3 -> レベル順走査を行う関数
    void levelorder(node *root)
    IF root == NULL
        Return
    End
    queue<node*> que
    que.push(root)
    Loop While que.empty() == false
        int count = que.size()   // 現在のレベルのノード数
        Loop While count > 0
            node *node = que.front()
            print node->data
            que.pop()
            IF node->left != NULL
                que.push(node->left)
            End
            IF node->right != NULL
                que.push(node->right)
            End
            count を 1 減らす
        End
        改行を出力（レベルの区切り）
    End
Step 4 -> main() 関数内で
    node *root = newnode(3) で木を構築
    levelorder(root) を呼び出す
STOP

アルゴリズムのポイント

• que.size() を呼び出すことで、現在処理中のレベルに含まれるノードの数を取得できます。
• 内側のループが1周し終えると、そのレベルのすべてのノードの出力が完了したことになります。ここで改行を挿入すれば、レベルごとに行を分けて表示できます。
• 子ノードは「次のレベル」の候補としてキューに追加されるため、訪問順序が自然に保たれます。

C++での実装例

#include <iostream>
#include <queue>
using namespace std;

// ノード構造体を定義
struct node {
    struct node *left;
    int data;
    struct node *right;
};

// レベル順走査を行い、レベルごとに行を分けて出力する
void levelorder(node *root) {
    if (root == NULL)
        return;
    queue<node *> que;
    que.push(root);
    while (que.empty() == false) {
        int count = que.size(); // 現在のレベルのノード数
        while (count > 0) {
            node *node = que.front();
            cout << node->data << " ";
            que.pop();
            if (node->left != NULL)
                que.push(node->left);
            if (node->right != NULL)
                que.push(node->right);
            count--;
        }
        cout << endl; // レベルの区切りで改行
    }
}

// 新しいノードを生成する
node* newnode(int data) {
    node *temp = new node;
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

int main() {
    // 二分木を構築
    node *root = newnode(3);
    root->left = newnode(2);
    root->right = newnode(1);
    root->left->left = newnode(10);
    root->left->right = newnode(20);
    root->right->right = newnode(30);
    levelorder(root);
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、各レベルのノード値が次のように1行ずつ出力されます。

3
2 1
10 20 30

計算量について

このアルゴリズムでは、各ノードをちょうど1回ずつ訪問するため、時間計算量は O(n)（n はノードの総数）です。また、最悪ケース（完全二分木など）ではキューに木の最大幅分のノードが同時に格納されるため、空間計算量も O(n) となります。