এই টিউটোরিয়ালে আমরা শিখব কিভাবে N-এরি ট্রির গভীরতা বের করা যায়।
একটি N-এরি ট্রি হলো এমন একটি ট্রি যাতে ট্রির প্রতিটি নোডের সর্বোচ্চ N সংখ্যক চাইল্ড নোড থাকে।
আমাদের N-এরি ট্রির গভীরতা বের করতে হবে। আমরা প্রতিটি নোডের চাইল্ডগুলো স্টোর করার জন্য ভেক্টর ব্যবহার করব।
সমস্যা সমাধানের ধাপগুলো:
ডামি ডেটা দিয়ে ট্রি ইনিশিয়ালাইজ করুন।
N-এরি ট্রির গভীরতা বের করার জন্য একটি রিকারসিভ ফাংশন লিখুন।
ট্রির সর্বোচ্চ গভীরতা স্টোর করার জন্য একটি ভেরিয়েবল ইনিশিয়ালাইজ করুন।
প্রতিটি নোডের চাইল্ডগুলোর ওপর ইটারেট করুন।
সর্বোচ্চ গভীরতা হবে বর্তমান সর্বোচ্চ গভীরতা এবং নোডের চাইল্ডের গভীরতার মধ্যে সর্বোচ্চ মান।
যদি আমরা ধরি সর্বোচ্চ গভীরতা ভেরিয়েবলটি maxDepth এবং maxDepth = max(maxDepth, findDepthOfTree(*children) হলো ট্রির গভীরতা বের করার রিকারসিভ স্টেটমেন্ট।
ট্রির চূড়ান্ত সর্বোচ্চ গভীরতা হবে maxDepth + 1।
ট্রির সর্বোচ্চ গভীরতা প্রিন্ট করুন।
উদাহরণ
নিচে কোডটি দেওয়া হলো:
#include <bits/stdc++.h> using namespace std; struct Node { int data; vector<Node *> child; }; Node *newNode(int data) { Node *temp = new Node; temp->data = data; return temp; } int findDepthOfTree(struct Node *node) { if (node == NULL) { return 0; } int maxDepth = 0; for (vector<Node*>::iterator it = node->child.begin(); it != node->child.end(); it++) { maxDepth = max(maxDepth, findDepthOfTree(*it)); } return maxDepth + 1; } int main() { Node *root = newNode(1); root->child.push_back(newNode(2)); root->child.push_back(newNode(3)); root->child.push_back(newNode(4)); root->child[2]->child.push_back(newNode(1)); root->child[2]->child.push_back(newNode(2)); root->child[2]->child.push_back(newNode(3)); root->child[2]->child.push_back(newNode(4)); cout << findDepthOfTree(root) << endl; return 0; }আউটপুট
উপরের কোডটি রান করলে নিচের ফলাফল পাওয়া যাবে:
3
উপসংহার
টিউটোরিয়াল সম্পর্কে কোনো প্রশ্ন থাকলে কমেন্ট সেকশনে জানান।
