使用 C++ 在 N-ary 树中查找给定节点的兄弟节点数

在本文中，我们将提供完整的信息来确定 n 叉树中给定节点的兄弟节点的数量。我们需要用用户给定的key值找到节点的兄弟节点；如果不是，则输出为-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

以上程序说明

在这个程序中，我们维护一个队列，里面有未访问的节点，访问的节点将被弹出。现在，当我们探索一个节点时，我们探索它的孩子，如果孩子的值与x匹配，那么我们的标志被触发，我们的答案变量已经被赋值为-1，然后我们突破了对于一个循环，现在我们检查标志是否被触发。如果它被触发，那么我们就会退出 while 循环。之后，如果不存在具有给定值的节点，我们现在打印答案，那么我们的答案变量将不会改变，输出将为 -1。如果根值与给定的值相同，则有一个 if 语句来检查并运行我们的程序。child.size()

结论

在这篇文章中，我们解决了一个问题，在时间复杂度上找到n 叉树中给定节点的兄弟节点的数量O(N)。我们还学习了针对此问题的 C++ 程序以及解决此问题的完整方法。我们可以用其他语言编写相同的程序，例如 C、java、python 和其他语言。