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