C++ で書かれており、N 分ツリー内の特定のノードの兄弟の数を見つけます。

この記事では、n 分ツリー内の特定のノードの兄弟の数を決定するための完全な情報を提供します。ユーザーが指定したキー値を使用して、このノードの兄弟ノードを見つける必要があります。見つからない場合は、-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 ステートメントがあります。

結論

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

以上がC++ で書かれており、N 分ツリー内の特定のノードの兄弟の数を見つけます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。