C ++を使用して、N-aryツリー内の特定のノードの兄弟の数を検索します

この記事では、n-aryツリー内の特定のノードの兄弟の数を決定するための完全な情報を提供します。ユーザーが指定したkeyの値でノードの兄弟を見つける必要があります。そうでない場合は、-1として出力します。使用できるアプローチは1つだけです-

シンプルなアプローチ

このアプローチでは、すべてのノードを調べて、子がユーザーと同じ値を持っているかどうかを確認します。存在する場合は、1（指定された値）の子の数に答えます。

例

#include <bits/stdc++.h>
using namespace std;
class Node {  // structure of nodes of our tree.
public:
    int key;
    vector<Node*> child;
    Node(int data){
        key = data;
    }
};
int main(){
   //     Building The Tree
    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

上記プログラムの説明

このプログラムでは、訪問されていないノードを内部に持つキューを維持し、訪問されたノードがポップされます。ここで、ノードを探索するとき、その子を探索します。子の値がxと一致すると、フラグがトリガーされ、回答変数にchild.size（）-1の値が割り当てられます。次に、forループを突破し、フラグがトリガーされているかどうかを確認します。トリガーされると、whileループから抜け出します。その後、指定された値のノードが存在しない場合は、回答を出力します。そのため、回答変数は変更されず、出力は-1になります。ルート値が指定された値と同じである場合、それをチェックしてプログラムを実行するifステートメントがあります。

結論

この記事では、問題を解決して、n-aryツリー内の特定のノードの兄弟の数を見つけます。 O（N）時間計算量。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチについても学びました。同じプログラムをC、Java、Python、その他の言語などの他の言語で作成できます。