मान लीजिए कि हमारे पास एक विशेष बाइनरी ट्री है, जिसके लीफ नोड्स एक गोलाकार डबल लिंक्ड लिस्ट बनाने के लिए जुड़े हुए हैं। हमें इसकी ऊंचाई का पता लगाना है। तो सबसे बाईं ओर के पत्ते का बायां सूचक गोलाकार डबल लिंक्ड सूची के पिछले सूचक के रूप में कार्य करेगा, और इसका दायां सूचक लिंक की गई सूची के अगले सूचक के रूप में कार्य करेगा।
इस मामले में ऊंचाई खोजने की रणनीति सामान्य बाइनरी सर्च ट्री के समान है। हम एक नोड के बाएँ और दाएँ उपप्रकारों की ऊँचाई की पुनरावर्ती गणना करते हैं और नोड को ऊँचाई प्रदान करते हैं जो दो बच्चों की अधिकतम है + 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