【C++】二分木の指定した2つのレベル間にあるノードをすべて出力する方法

はじめに

この記事では、二分木（バイナリツリー）において、指定された2つのレベル番号の間に存在するノードをすべて出力するC++プログラムを解説します。

具体的には、二分木と出力範囲となる下限レベル（low）・上限レベル（high）が与えられたとき、その範囲に含まれるすべてのノードの値を表示します。ここでは、ルートノードをレベル1として扱います。

アルゴリズムの考え方

この問題は、キューを用いたレベル順走査（幅優先探索：BFS）で効率よく解くことができます。ポイントは、各レベルの末尾に「マーカーノード」を配置し、レベルの境界を検知できるようにすることです。

• ルートノードとマーカーノードをキューに追加します。
• キューから取り出したノードがマーカーであれば、それはレベルの区切りを意味するため改行し、レベル数を1つ増やします。
• 通常のノードであれば、現在のレベルが出力範囲内の場合にその値を出力し、左右の子ノードをキューに追加します。
• キューが空になるか、レベルが上限（high）を超えた時点で処理を終了します。

サンプルツリー

            20          ← レベル1
           /  \
          8    22       ← レベル2
         / \
        4    12        ← レベル3
            /  \
          10    14      ← レベル4

このツリーに対して low=2、high=3 を指定すると、レベル2とレベル3に属するノードが出力されます。

C++での実装例

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

struct Node{
    int data;
    struct Node* left, *right;
};

// 指定レベル間のノードを出力する関数
void print_nodes(Node* root, int low, int high){
    queue<Node*> Q;
    // レベルの終端を示すマーカーノードを作成
    Node* marker = new Node;
    int level = 1;
    Q.push(root);
    Q.push(marker);
    while (Q.empty() == false){
        Node* n = Q.front();
        Q.pop();
        // レベルの終端かどうかをチェック
        if (n == marker){
            cout << endl;
            level++;
            if (Q.empty() == true || level > high)
                break;
            Q.push(marker);
            continue;
        }
        // 現在のレベルが出力範囲内なら値を表示
        if (level >= low)
            cout << n->data << " ";
        if (n->left != NULL) Q.push(n->left);
        if (n->right != NULL) Q.push(n->right);
    }
}

Node* create_node(int data){
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return (temp);
}

int main(){
    struct Node* root = create_node(20);
    root->left = create_node(8);
    root->right = create_node(22);
    root->left->left = create_node(4);
    root->left->right = create_node(12);
    root->left->right->left = create_node(10);
    root->left->right->right = create_node(14);
    cout << "指定レベル間のノードは以下の通りです:";
    print_nodes(root, 2, 3);
    return 0;
}

実行結果

指定レベル間のノードは以下の通りです:
8 22
4 12

計算量について

このアルゴリズムでは、各ノードを最大1回ずつ処理するため、時間計算量はO(N)（Nはノード総数）です。また、最悪の場合、キューには最下層のノード数に比例した要素が格納されるため、空間計算量もO(N)となります。

まとめ

マーカーノードを活用したレベル順走査を使えば、指定したレベル範囲に含まれるノードだけをシンプルに出力できます。レベル単位の処理が必要なさまざまな場面で応用できるテクニックなので、ぜひマスターしておきましょう。