আমরা একটি বাইনারি গাছ দেওয়া হয়. লক্ষ্য হল প্রদত্ত গাছের সর্বাধিক দৈর্ঘ্য চক্র খুঁজে বের করা। আমরা রুটনোড থেকে বাম সাবট্রি এবং ডান সাবট্রির সর্বোচ্চ উচ্চতা খুঁজে বের করে এটি করব এবং দীর্ঘতম চক্র পেতে এই সর্বাধিক দৈর্ঘ্যের পাথগুলিতে যোগ দেব৷
উপরের গাছের জন্য সর্বাধিক দৈর্ঘ্য চক্র হল 1-2-3-4-7-6 বা 1-6-7-4-3-2-1। দৈর্ঘ্য 6.
ইনপুট - গাছ
আউটপুট − সর্বাধিক দৈর্ঘ্য চক্র হল −5
ব্যাখ্যা − বাম সাবট্রির সর্বোচ্চ উচ্চতা 3 এবং ডান সাবট্রির 1। চক্রের দৈর্ঘ্য 3+1+1=5 হয়ে যায়। সাইকেল হল 1-2-3-4-6 বা 1-6-4-3-2
ইনপুট - গাছ
আউটপুট − সর্বাধিক দৈর্ঘ্য চক্র হল −7
ব্যাখ্যা − বাম উপবৃক্ষের সর্বোচ্চ উচ্চতা 3 এবং ডান উপবৃক্ষের 3। চক্রের দৈর্ঘ্য 3+3+1=7 হয়। সাইকেল হল 5-4-2-1-8-7-6 বা 5-6-7-8-1-2-4-5
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
একটি ক্লাস ট্রিনোড তৈরি করুন যাতে পাবলিক ডেটা মেম্বার থাকে - নোডের ওজনের জন্য int ডেটা, বাম এবং ডান ট্রিনোড পয়েন্টারগুলি এই ধরনের অন্যান্য নোডগুলিতে নির্দেশ করতে৷
-
ফাংশন newNode(int data) একটি প্যারামিটার হিসাবে ডেটা নেয় এবং NULL হিসাবে বাম এবং ডান পয়েন্টার সহ একটি নোড তৈরি করে৷
-
newnode() ফাংশন কল করে একটি ট্রি তৈরি করুন।
-
ফাংশন maxheight(treenode* root) গাছের একটি শিকড় নেয় এবং মূলে থাকা গাছের সর্বোচ্চ উচ্চতা প্রদান করে।
-
এই ফাংশনটি চেক করে যে রুটটি NULL, মানে উচ্চতা 0, রিটার্ন 0।
-
lheight এবং rheight নোড রুটের বাম এবং ডান সাবট্রির উচ্চতা গণনা করে, সর্বোচ্চ উচ্চতায় (রুট->বাম) রিকার্সিভ কল করে। এবং সর্বোচ্চ উচ্চতা(রুট->ডান);
-
উচ্চতা এবং উচ্চতা তুলনা করে প্রাপ্ত সর্বোচ্চ মান ফেরত দিন।
-
মূলের ভিতরে আমরা ট্রিনোডের বাম সাবট্রি এবং ডান সাবট্রির সর্বোচ্চ উচ্চতার মান সঞ্চয় করি।
-
এখন সর্বাধিক দৈর্ঘ্য চক্র হল রুট নিজেই সহ maxlheight +maxrheight+1 উভয়ের সমষ্টি।
-
ফলে চক্রের দৈর্ঘ্য প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
//class for tree
class treenode{
public:
int data;
treenode* left;
treenode* right;
};
//find maximum height between left and right subtree of current root
int maxheight(treenode* root){
if (root == NULL)
return 0;
else{
int lheight = maxheight(root->left);
int rheight = maxheight(root->right);
//find maximum height
if (lheight > rheight)
return(lheight + 1);
else
return(rheight + 1);
}
}
//creating a node of tree
treenode* newNode(int data){
treenode* Node = new treenode();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int main(){
treenode *root = newNode(6);
root->left = newNode(8);
root->right = newNode(9);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->right = newNode(7);
root->left->right->right->left = newNode(2);
int maxlheight=maxheight(root->left);
int maxrheight=maxheight(root->right);
int maxlheight=maxDepth(root->left);
int maxrheight=maxDepth(root->right);
cout << "Maximum length cycle: " << maxlheight+maxrheight+1;
return 0;
} আউটপুট
Maximum length cycle: 6
