ความลึกของต้นไม้ N-Ary ใน C ++?

ให้เรากำหนดโครงสร้างที่จะเป็นตัวแทนของโหนดต้นไม้ที่มีคีย์อักขระและเวกเตอร์ของโหนด *.

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

ต่อไป เราสร้างฟังก์ชัน createNode(int key) ที่ใช้ค่าคีย์ int และกำหนดให้กับสมาชิกคีย์ของโหนด ฟังก์ชันจะส่งกลับตัวชี้ไปยังโหนดโครงสร้างที่สร้างขึ้น

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

ฟังก์ชัน deepOfTree(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