C++で二分木のすべてのノードのレベルを出力する方法

二分木（バイナリツリー）が与えられたとき、各ノードに格納されたすべてのキーについて、そのノードが属するレベル（根をレベル1として数える）を出力するのが本記事の目的です。

上記の木では、ノードは次のように配置されています。

10 はレベル 1
3 と 211 はレベル 2
140、162、100、146 はレベル 3

特定のキーが与えられた場合、プログラムはそのキーが属するレベルを出力できなければなりません。

入出力例

入力: 10 3 211 140 162 100 146
出力:
    10 のレベルは 1
    3 のレベルは 2
    211 のレベルは 2
    140 のレベルは 3
    162 のレベルは 3
    100 のレベルは 3
    146 のレベルは 3

アプローチのポイント

この問題は、幅優先探索（BFS／レベル順走査）を利用することで効率的に解けます。キューには「ノードへのポインタ」と「そのノードのレベル」をペアで格納し、ノードを取り出すたびに子ノードへは現在のレベル+1を設定して追加していきます。こうすることで、すべてのノードのレベルを一度の走査で求められます。計算量はノード数を n とすると O(n) です。

アルゴリズム

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 levels(Node* root)
        IF root == NULL
        Return
    End
    STL の queue<pair<struct Node*, int> > que を作成
    que.push({root, 1})
    STL の pair<struct Node*, int> par を作成
    Loop While !que.empty()
        par = que.front()
        que.pop()
        par.first->data と par.second を出力
        IF par.first->left
            que.push({ par.first->left, par.second + 1 })
        END
        IF par.first->right
            que.push({ par.first->right, par.second + 1 })
        End
    End
STOP

C++による実装例

#include <bits/stdc++.h>
using namespace std;
// ノードの構造体
struct Node{
    int data;
    struct Node *left, *right;
};
// 木の各ノードのレベルを出力する関数
void levels(Node* root){
    if (root==NULL)
        return;
    queue<pair<struct Node*, int> >que;
    que.push({root, 1});
    pair<struct Node*, int> par;
    while (!que.empty()) {
        par = que.front();
        que.pop();
        cout << "Level of " << par.first->data << " is " << par.second << "\n";
        if (par.first->left)
            que.push({ par.first->left, par.second + 1 });
        if (par.first->right)
            que.push({ par.first->right, par.second + 1 });
    }
}
// ノードを生成して木を組み立てる関数
Node* newnode(int data){
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
int main(){
    Node* root = NULL;
    // ノードを作成する
    root = newnode(34);
    root->left = newnode(12);
    root->right = newnode(50);
    root->left->left = newnode(11);
    root->left->right = newnode(54);
    levels(root);
    return 0;
}

出力

上記のプログラムを実行すると、次のような出力が得られます。

Level of 34 is 1
Level of 12 is 2
Level of 50 is 2
Level of 11 is 3
Level of 54 is 3