C++でN分木における特定ノードの兄弟の数を求める方法

この記事では、N分木(N-ary tree)において、指定されたノードの兄弟ノードの数を求める方法について詳しく解説します。ユーザーから与えられたキーの値を持つノードの兄弟を探し、該当するノードが存在しない場合は -1 を出力します。利用できるアプローチは以下の一つです。

シンプルなアプローチ

このアプローチでは、すべてのノードを順番に走査し、その子ノードの中にユーザーが指定した値と同じ値を持つものが存在するかどうかを確認します。存在する場合は、「その親が持つ子ノードの総数 − 1(指定されたノード自身)」を答えとして返します。

コード例

#include <bits/stdc++.h>
using namespace std;
class Node {  // 木のノード構造体
public:
    int key;
    vector<Node*> child;
    Node(int data){
        key = data;
    }
};
int main(){
   //     木の構築
    Node* Base = new Node(50);
    (Base->child).push_back(new Node(2));
    (Base->child).push_back(new Node(30));
    (Base->child).push_back(new Node(14));
    (Base->child).push_back(new Node(60));
    (Base->child[0]->child).push_back(new Node(15));
    (Base->child[0]->child).push_back(new Node(25));
    (Base->child[0]->child[1]->child).push_back(new Node(70));
    (Base->child[0]->child[1]->child).push_back(new Node(100));
    (Base->child[1]->child).push_back(new Node(6));
    (Base->child[1]->child).push_back(new Node(1));
    (Base->child[2]->child).push_back(new Node(7));
    (Base->child[2]->child[0]->child).push_back(new Node(17));
    (Base->child[2]->child[0]->child).push_back(new Node(99));
    (Base->child[2]->child[0]->child).push_back(new Node(27));
    (Base->child[3]->child).push_back(new Node(16));
    int x = 30;
    queue<Node*> q;
    q.push(Base);
    bool flag = 0;
    int answer = -1;
    if(Base -> key != x){
        while(!q.empty()){
            auto parent = q.front();
            q.pop();
            for(int i = 0; i < parent -> child.size(); i++){
                if(parent -> child[i] -> key == x){
                    answer = parent -> child.size() - 1;
                    flag = 1;
                    break;
                }
                q.push(parent -> child[i]);
            }
            if(flag)
                break;
        }
        cout << answer << "\n";
    }
    else
        cout << "0\n";
    return 0;
}

出力

3

プログラムの解説

このプログラムでは、未訪問のノードを保持するためのキュー(queue)を使用しています。訪問済みのノードはキューから取り出されます。ノードを探索する際には、その子ノードもあわせて確認し、子ノードの値が x と一致した場合にはフラグを立て、answer 変数に child.size() - 1 の値を代入した上で for ループを抜けます。その後、フラグが立っているかどうかを判定し、立っていれば while ループを抜けて結果を出力します。

もし指定された値を持つノードが木の中に存在しない場合、answer 変数は初期値のまま変更されないため、出力は -1 になります。また、根(root)の値が指定された値と一致する場合は兄弟が存在しないため、冒頭の if 文によるチェックによって 0 を出力するようになっています。

計算量

このアルゴリズムは幅優先探索(BFS)をベースとしており、各ノードを一度ずつ訪問するため、時間計算量は O(N) となります。ここで N は木に含まれるノードの総数です。

まとめ

この記事では、N分木における特定ノードの兄弟の数を求める問題を O(N) の時間計算量で解く方法を紹介しました。C++での実装例とともに、問題を解決するための完全なアプローチについても学びました。同じロジックは、C、Java、Python などの他のプログラミング言語でも同様に実装することができます。