C++ এ N-Ary গাছের গভীরতা?

আসুন প্রথমে স্ট্রাকটটি সংজ্ঞায়িত করি যা একটি ট্রি নোডকে প্রতিনিধিত্ব করবে যাতে একটি অক্ষর কী এবং নোড * এর একটি ভেক্টর রয়েছে৷

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

এরপরে আমরা আমাদের createNode(int কী) ফাংশন তৈরি করি যা একটি int কী মান নেয় এবং এটি নোডের মূল সদস্যকে বরাদ্দ করি। ফাংশনটি তৈরি করা স্ট্রাকট নোডে পয়েন্টার ফিরিয়ে দেয়।

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