इस समस्या में, हमें एक बाइनरी ट्री और एक नोड दिया गया है। हमारा कार्य बाइनरी ट्री में उस नोड का पोस्टऑर्डर सक्सेसर प्रिंट करना है।
बाइनरी ट्री एक विशेष प्रकार का ट्री है जिसमें प्रत्येक नोड में अधिकतम 2 चाइल्ड नोड हो सकते हैं।
पोस्टऑर्डर ट्रैवर्सल एक ट्री ट्रैवर्सल तकनीक है, जिसमें पहले बाएं सबट्री को पार किया जाता है, फिर दाएं सबट्री को और अंत में रूट को पार किया जाता है।
उपरोक्त ट्री का पोस्टऑर्डर ट्रैवर्सल: 8 4 2 7 9 6
आइए एक उदाहरण से समझते हैं।
इनपुट - उपरोक्त उदाहरण में बाइनरी ट्री, नोड = 7
आउटपुट - 9
व्याख्या - हम इसे बाइनरी ट्री के पोस्टऑर्डर ट्रैवर्सल में देख सकते हैं।
इस समस्या को हल करने का एक सरल, आसान और नौसिखिया समाधान होगा केवल पोस्टऑर्डर ट्रैवर्सल ढूंढना और फिर ट्रैवर्सल में उसके आगे की संख्या प्रिंट करना।
लेकिन हमें एक अधिक प्रभावी समाधान सीखने की आवश्यकता है,
एक प्रभावी समाधान में पोस्टऑर्डर ट्रैवर्सल पर कुछ सामान्य अवलोकनों का उपयोग शामिल होगा।
चूंकि रूट पोस्टऑर्डर ट्रैवर्सल में अंतिम नोड होता है, इसका सक्सेसर NULL होता है।
वर्तमान नोड के दाएं चाइल्ड होने की स्थिति में, पैरेंट नोड सक्सेसर होता है।
वर्तमान नोड के बाएं चाइल्ड होने की स्थिति में,
यदि दायां सिबलिंग अनुपस्थित है, तो सक्सेसर पैरेंट नोड होता है
यदि दायां सिबलिंग मौजूद है तो या तो वह नोड या उसका सबसे बायां चाइल्ड सक्सेसर होता है।
यह विधि प्रभावी है, समय जटिलता O(h) है, जहां h ट्री की ऊंचाई है।
उदाहरण
हमारे समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम,
#include <iostream> using namespace std; struct Node { struct Node *left, *right, *parent; int value; }; struct Node* insertNode(int value) { Node* temp = new Node; temp->left = temp->right = temp->parent = NULL; temp->value = value; return temp; } Node* findPostorderSuccessor(Node* root, Node* n) { if (n == root) return NULL; Node* parent = n->parent; if (parent->right == NULL || parent->right == n) return parent; Node* curr = parent->right; while (curr->left != NULL) curr = curr->left; return curr; } int main(){ struct Node* root = insertNode(6); root->parent = NULL; root->left = insertNode(2); root->left->parent = root; root->left->left = insertNode(8); root->left->left->parent = root->left; root->left->right = insertNode(4); root->left->right->parent = root->left; root->right = insertNode(9); root->right->parent = root; root->right->left = insertNode(7); root->right->left->parent = root->right; root->left->right->left = insertNode(14); struct Node* successorNode = findPostorderSuccessor(root, root->left->right); if (successorNode) cout<<"पोस्टऑर्डर सक्सेसर ऑफ "<<root->left->right->value<<" is "<<successorNode->value; else cout<<"पोस्टऑर्डर सक्सेसर ऑफ "<<root->left->right->value<<" is NULL"; return 0; }आउटपुट
पोस्टऑर्डर सक्सेसर ऑफ 4 is 2
