C++로 작성되어 N-ary 트리에서 주어진 노드의 형제 수를 찾습니다.

이 기사에서는 n-ary 트리에서 특정 노드의 형제 수를 결정하는 완전한 정보를 제공합니다. 사용자가 제공한 키 값을 사용하여 이 노드의 형제 노드를 찾아야 합니다. 그렇지 않은 경우 출력은 -1입니다. 우리가 사용할 수 있는 방법은 단 하나입니다.

간단한 방법

이 방법에서는 모든 노드를 반복하고 하위 노드가 사용자와 동일한 값을 갖는지 확인합니다. 존재하는 경우 하위 노드 수 - 1(주어진 값)로 응답합니다.

Example

#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;
}

Output

3

위 프로그램에 대한 설명

이 프로그램에서는 방문하지 않은 노드가 포함된 대기열을 유지하고 방문한 노드를 표시합니다. 이제 노드를 탐색할 때 그 자식을 탐색하고 자식 값이 x와 일치하면 플래그가 트리거되고 응답 변수에 child.size() - 1 값이 할당된 다음 for 루프에서 빠져 나옵니다. 이제 플래그가 트리거되었는지 확인합니다. 실행되면 while 루프를 종료합니다. 그 후, 주어진 값을 가진 노드가 없으면 이제 답을 인쇄하므로 답 변수는 변경되지 않고 출력은 -1이 됩니다. 루트 값이 주어진 값과 동일하면 값을 확인하고 프로그램을 실행하는 if 문이 있습니다.

결론

이 글에서는 시간 복잡도가 O(N)인 n진 트리에서 주어진 노드의 형제 수를 구하는 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하는 완전한 방법을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.

위 내용은 C++로 작성되어 N-ary 트리에서 주어진 노드의 형제 수를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!