ধরুন আমাদের একটি বিশেষ বাইনারি গাছ আছে, যার পাতার নোডগুলি সংযুক্ত করে একটি বৃত্তাকার দ্বিগুণ লিঙ্কযুক্ত তালিকা তৈরি করে। আমাদের এর উচ্চতা খুঁজে বের করতে হবে। তাই বাম দিকের সর্বাধিক পাতার বাম পয়েন্টারটি বৃত্তাকার দ্বিগুণ লিঙ্কযুক্ত তালিকার পূর্ববর্তী পয়েন্টার হিসাবে কাজ করবে এবং এর ডান পয়েন্টারটি লিঙ্কযুক্ত তালিকার পরবর্তী পয়েন্টার হিসাবে কাজ করবে।
এই ক্ষেত্রে উচ্চতা খোঁজার কৌশলটি সাধারণ বাইনারি অনুসন্ধান গাছের মতো। আমরা পুনরাবৃত্তিমূলকভাবে একটি নোডের বাম এবং ডান উপবৃক্ষের উচ্চতা গণনা করি এবং নোডের উচ্চতা নির্ধারণ করি দুটি সন্তানের সর্বাধিক + 1। তবে এখানে পাতাগুলি বৃত্তাকার দ্বিগুণ লিঙ্কযুক্ত তালিকার উপাদান। সুতরাং একটি নোডকে লিফ নোড হওয়ার জন্য আমরা পরীক্ষা করি যে বামদিকের নোডটি নোডের দিকে নির্দেশ করছে এবং তার ডানের বামটি নোডের দিকে নির্দেশ করছে কিনা৷
উদাহরণ
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
bool isLeafNode(Node* node) {
return node->left && node->left->right == node && node->right && node->right->left == node;
}
int findHeight(Node* node) {
if (node == NULL)
return 0;
if (isLeafNode(node))
return 1;
return 1 + max(findHeight(node->left), findHeight(node->right));
}
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->left->left->left = getNode(6);
Node *L1 = root->left->left->left;
Node *L2 = root->left->right;
Node *L3 = root->right;
L1->right = L2, L2->right = L3, L3->right = L1;
L3->left = L2, L2->left = L1, L1->left = L3;
cout << "Height of tree is: " << findHeight(root);
} আউটপুট
Height of tree is: 4
