এই টিউটোরিয়ালে, আমরা শিখব কিভাবে n-ary গাছের গভীরতা বের করতে হয়।
একটি n-ary গাছ এমন একটি গাছ যেখানে গাছের প্রতিটি নোড n এর বেশি নেই চাইল্ড নোড।
আমাদের n-ary গাছের গভীরতা খুঁজে বের করতে হবে। আমরা গাছে প্রতিটি নোডের বাচ্চাদের সংরক্ষণ করতে ভেক্টর ব্যবহার করব।
আসুন সমস্যা সমাধানের পদক্ষেপগুলি দেখি৷
৷-
ডামি ডেটা দিয়ে ট্রি শুরু করুন।
-
n-ary গাছের গভীরতা খুঁজে বের করার জন্য একটি পুনরাবৃত্ত ফাংশন লিখুন।
-
গাছের সর্বোচ্চ গভীরতা সংরক্ষণ করতে একটি পরিবর্তনশীল শুরু করুন।
-
প্রতিটি নোডের শিশুদের উপর পুনরাবৃত্তি করুন।
-
সর্বাধিক গভীরতা বর্তমান সর্বাধিক গভীরতা এবং নোড শিশুদের গভীরতার সর্বোচ্চ।
-
যদি আমরা ধরে নিই সর্বোচ্চ গভীরতা পরিবর্তনশীল হল 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
উপসংহার
টিউটোরিয়ালে আপনার কোন প্রশ্ন থাকলে মন্তব্য বিভাগে উল্লেখ করুন।
