C++에서 N-Ary 트리의 깊이?

먼저 문자 키와 Node *의 벡터를 포함하는 트리 노드를 나타내는 구조체를 정의하겠습니다.

struct Node{
   char key;
   vector<Node *> children;
};

다음으로 int 키 값을 받아 노드의 키 멤버에 할당하는 createNode(int key) 함수를 만듭니다. 함수는 생성된 구조체 노드에 대한 포인터를 반환합니다.

Node *createNode(int key){
   Node *node = new Node;
   node->key = key;
   return node;
}

우리의 depthOfTree(struct Node* root) 함수는 루트 노드를 매개변수로 사용합니다. 루트가 NULL이면 깊이는 0으로 반환됩니다.

int depthOfTree(struct Node *root){
   if (root==NULL)
      return 0;

그런 다음 maxDepth 변수를 정의하고 그 값을 0으로 할당합니다. 그런 다음 트리의 모든 자식을 반복하고 각 재귀에서 maxDepth를 증가시킵니다. 기본 조건이 충족되고 재귀가 끝나면 maxDepth를 반환합니다.

int depthOfTree(struct Node *root){
   if (root==NULL)
      return 0;
      int maxDepth = 0;
   for(auto i: root->children){
      maxDepth = depthOfTree(i) + 1;
   }
   return maxDepth;
}

예

N-Ary 트리의 깊이를 찾기 위해 다음 구현을 살펴보겠습니다. −

#include <iostream>
#include <vector>
using namespace std;
struct Node{
   char key;
   vector<Node *> children;
};
Node *createNode(int key){
   Node *node = new Node;
   node->key = key;
   return node;
}
int depthOfTree(struct Node *root){
   if (root==NULL)
      return 0;
   int maxDepth = 0;
   for(auto i: root->children){
      maxDepth = depthOfTree(i) + 1;
   }
   return maxDepth;
}
int main(){
   Node *root = createNode('S');
   (root->children).push_back(createNode('O'));
   (root->children).push_back(createNode('A'));
   (root->children).push_back(createNode('D'));
   (root->children).push_back(createNode('N'));
   (root->children[0]->children).push_back(createNode('L'));
   (root->children[0]->children).push_back(createNode('I'));
   (root->children[2]->children).push_back(createNode('R'));
   (root->children[3]->children).push_back(createNode('C'));
   (root->children[3]->children).push_back(createNode('H'));
   (root->children[3]->children).push_back(createNode('I'));
   cout <<"The depth of the n-ary tree is "<< depthOfTree(root) << endl;
   return 0;
}

출력

위의 코드는 다음 출력을 생성합니다 -

The depth of the n-ary tree is 2