이 기사에서 우리는 n-ary 트리에서 주어진 노드의 형제 수를 결정하기 위한 완전한 정보를 제공할 것입니다. 사용자가 제공한 키 값으로 노드의 형제를 찾아야 합니다. 그렇지 않으면 -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 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.