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

この問題では、二分木と、木の中の2つのレベル(上位レベルと下位レベル)が与えられ、その2つのレベル間に存在するすべてのノードを出力することが求められます。

二分木とは、各ノードが最大2つの子ノード(0個・1個・2個)を持つ特殊な木構造のことです。

問題の例

具体例を使って問題を理解しましょう。

上位レベル(upper):3
下位レベル(lower):1

出力結果:

6
3 9
7 4 8 10

解決アプローチ

方法1:再帰関数を使う方法

この問題を解くには、指定されたレベルのノードを出力する必要があります。upperからlowerまでのレベルをループで回しながら、再帰関数を呼び出すことで実現できます。

このアルゴリズムはシンプルですが、計算量はO(n²)となり、やや非効率です。

方法2:キューを使った幅優先探索(BFS)

より効率的な解決策は、キューを使用して幅優先探索(BFS)を行う方法です。マーカーノードを活用してレベルの境界を検出し、指定された上位レベルと下位レベルの範囲内にあるノードだけを出力します。

具体的には以下の手順で動作します:

• ルートノードとマーカーをキューに追加し、現在のレベルを1として初期化します。
• キューからノードを取り出し、それがマーカーであれば改行してレベルを1つ増やします。レベルが上限を超えたら処理を終了します。
• 現在のレベルが下限以上であれば、そのノードの値を出力します。
• 子ノードが存在すれば、それらをキューに追加していきます。

C++での実装例

#include <iostream>
#include <queue>
using namespace std;
struct Node{
    int key;
    struct Node* left, *right;
};
void printNodesAtLevel(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->key<<" ";
        if (n->left != NULL) Q.push(n->left);
        if (n->right != NULL) Q.push(n->right);
    }
}
Node* insertNode(int key){
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
int main() {
    struct Node *root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(9);
    root->left->left = insertNode(7);
    root->left->right = insertNode(4);
    root->left->right->left = insertNode(8);
    root->left->right->right = insertNode(10);
    root->left->right->right->left = insertNode(5);
    root->left->right->right->right = insertNode(1);
    root->left->right->left->left = insertNode(14);
    root->left->right->left->right = insertNode(26);
    int upper = 3;
    int lower = 1;
    cout << "Level wise Nodes between level "<<lower<<" and "<<upper<<" are \n";
    printNodesAtLevel(root, lower, upper);
    return 0;
}

実行結果

Level wise Nodes between level 1 and 3 are
6
3 9
7 4

このように、キューを活用したBFSによるアプローチでは、各レベルのノードを効率的に走査しながら、指定されたレベル範囲内のノードのみをレベルごとに出力できます。計算量はO(n)程度に抑えられるため、再帰的な方法と比べて大規模な二分木に対しても有効です。