Độ sâu của cây N-Ary trong C ++?

Trước tiên, chúng ta hãy xác định cấu trúc đại diện cho một nút cây có chứa khóa ký tự và vectơ của Node *.

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

Tiếp theo, chúng ta tạo hàm createNode (int key) lấy giá trị khóa int và gán nó cho thành viên chính của nút. Hàm trả về con trỏ đến nút cấu trúc đã tạo.

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

Hàm deepOfTree (struct Node * root) của chúng tôi lấy nút gốc làm tham số. Nếu gốc là NULL thì độ sâu được trả về là 0.

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

Sau đó, chúng tôi xác định biến maxDepth và gán giá trị của nó bằng 0. Sau đó, chúng tôi lặp lại trên tất cả các con của cây và tăng maxDepth trên mỗi lần đệ quy. Khi điều kiện cơ bản được đáp ứng và quá trình đệ quy kết thúc, chúng tôi trả về 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;
}

Ví dụ

Chúng ta hãy xem cách triển khai sau để tìm độ sâu của cây 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;
}

Đầu ra

Đoạn mã trên sẽ tạo ra kết quả sau -

The depth of the n-ary tree is 2