C++ 프로그램에서 N-Ary 트리의 깊이

이 튜토리얼에서는 n-ary 트리의 깊이를 찾는 방법을 배울 것입니다.

n-ary 트리는 트리의 각 노드가 n개 이하인 트리입니다. 자식 노드.

n-ary 트리의 깊이를 찾아야 합니다. 벡터를 사용하여 트리에 있는 각 노드의 자식을 저장합니다.

문제를 해결하는 단계를 살펴보겠습니다.

• 더미 데이터로 트리를 초기화합니다.

• n-ary 트리의 깊이를 찾는 재귀 함수를 작성하십시오.

  • 트리의 최대 깊이를 저장할 변수를 초기화합니다.

  • 각 노드의 자식을 반복합니다.

    • 최대 깊이는 현재 최대 깊이와 노드 자식의 깊이의 최대값입니다.

    • 최대 깊이 변수가 maxDepth라고 가정하면 및 maxDepth =max(maxDepth, findDepthOfTree(*children) 트리의 깊이를 찾는 재귀 문입니다.

  • 트리의 최종 최대 깊이는 maxDepth + 1입니다. .

• 트리의 최대 깊이를 인쇄합니다.

예시

코드를 봅시다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   vector<Node *> child;
};
Node *newNode(int data) {
   Node *temp = new Node;
   temp->data = data;
   return temp;
}
int findDepthOfTree(struct Node *node) {
   if (node == NULL) {
      return 0;
   }
   int maxDepth = 0;
   for (vector<Node*>::iterator it = node->child.begin(); it != node->child.end(); it++) {
      maxDepth = max(maxDepth, findDepthOfTree(*it));
   }
   return maxDepth + 1;
}
int main() {
   Node *root = newNode(1);
   root->child.push_back(newNode(2));
   root->child.push_back(newNode(3));
   root->child.push_back(newNode(4));
   root->child[2]->child.push_back(newNode(1));
   root->child[2]->child.push_back(newNode(2));
   root->child[2]->child.push_back(newNode(3));
   root->child[2]->child.push_back(newNode(4));
   cout << findDepthOfTree(root) << endl;
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

3

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.