> 백엔드 개발 > C++ > 본문

使用C++编写,找到N叉树中给定节点的兄弟节点数量

WBOY
풀어 주다: 2023-08-26 20:33:06
앞으로
1102명이 탐색했습니다.

使用C++编写,找到N叉树中给定节点的兄弟节点数量

在本文中,我们将提供完整的信息来确定 n 叉树中给定节点的兄弟节点数量。我们需要使用用户给定的 key 值找到该节点的兄弟节点;如果不是,则输出-1。我们只能使用一种方法 -

简单方法

在这种方法中,我们将遍历所有节点并检查子节点是否与用户具有相同的值。如果存在,我们回答子节点的数量 - 1(给定值)。

示例

#include 
using namespace std;
class Node {  // structure of nodes of our tree.
public:
    int key;
    vector 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 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 叉树中给定节点的兄弟节点数量,时间复杂度为 O(N)。我们还学习了解决这个问题的C++程序以及解决这个问题的完整方法。我们可以用其他语言编写相同的程序,例如C、java、python等语言。

위 내용은 使用C++编写,找到N叉树中给定节点的兄弟节点数量의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:tutorialspoint.com
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!