सी ++ में एन-आरी पेड़ की गहराई?

आइए पहले उस संरचना को परिभाषित करें जो एक ट्री नोड का प्रतिनिधित्व करेगी जिसमें एक वर्ण कुंजी और नोड * का एक वेक्टर होता है।

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

इसके बाद हम अपना createNode(int key) फंक्शन बनाते हैं जो एक इंट की वैल्यू लेता है और इसे नोड के प्रमुख सदस्य को असाइन करता है। फ़ंक्शन पॉइंटर को बनाए गए स्ट्रक्चर नोड में लौटाता है।

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

हमारा डेप्थऑफट्री (स्ट्रक्चर नोड * रूट) फंक्शन रूट नोड को पैरामीटर के रूप में लेता है। यदि रूट NULL है तो गहराई 0 के रूप में वापस आ जाती है।

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

फिर हम maxDepth वेरिएबल को परिभाषित करते हैं और इसके मान को 0 पर असाइन करते हैं। फिर हम ट्री के सभी बच्चों पर पुनरावृति करते हैं और प्रत्येक रिकर्सन पर 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;
}

उदाहरण

आइए एन-आरी पेड़ की गहराई का पता लगाने के लिए निम्नलिखित कार्यान्वयन को देखें -

#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