इस समस्या में, हमें एक बाइनरी ट्री और नोड दिया जाता है। हमारा काम बाइनरी ट्री में नोड के पोस्टऑर्डर उत्तराधिकारी को प्रिंट करना है।
बाइनरी पेड़ एक विशेष प्रकार का पेड़ है जिसमें प्रत्येक नोड में अधिकतम 2 चाइल्ड नोड हो सकते हैं।
पोस्टऑर्डर ट्रैवर्सल एक ट्री ट्रैवर्सल तकनीक है, जिसमें पहले बाएँ सबट्री को राइट सबट्री की तुलना में ट्रेस किया जाता है और अंत में रूट को ट्रैवर्स किया जाता है।
उपरोक्त पेड़ का पोस्टऑर्डर ट्रैवर्सल:8 4 2 7 9 6
समस्या को समझने के लिए एक उदाहरण लेते हैं।
इनपुट - ऊपर के उदाहरण में बाइनरी ट्री, नोड =7
आउटपुट - 9
स्पष्टीकरण - हम इसे बाइनरी ट्री के पोस्ट-ऑर्डर ट्रैवर्सल में देख सकते हैं।
इस समस्या को हल करने के लिए, एक सरल, आसान और नोब का समाधान बस पोस्टऑर्डर ट्रैवर्सल ढूंढना होगा और फिर ट्रैवर्सल में उसके आगे की संख्या को प्रिंट करना होगा।
लेकिन हमें एक अधिक प्रभावी समाधान सीखने की जरूरत है,
एक प्रभावी समाधान में पोस्टऑर्डर ट्रैवर्सल पर कुछ सामान्य अवलोकन का उपयोग करना शामिल होगा।
-
चूंकि रूट पोस्टऑर्डर ट्रैवर्सल में अंतिम नोड है, इसलिए इसका उत्तराधिकारी NULL है।
-
वर्तमान नोड के सही बच्चे होने की स्थिति में, पैरेंट नोड उत्तराधिकारी होता है।
-
वर्तमान नोड के बच्चे छोड़े जाने की स्थिति में, तब
-
अगर सही भाई-बहन अनुपस्थित है, तो उत्तराधिकारी पैरेंट नोड होता है
-
यदि दायां भाई मौजूद है तो या तो नोड या उसका सबसे बायां बच्चा उत्तराधिकारी है।
-
यह विधि प्रभावी है, समय जटिलता O(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<<"Postorder successor of "<<root->left->right->value<<" is "<<successorNode->value;
else
cout<<"Postorder successor of "<<root->left->right->value<<" is NULL";
return 0;
} आउटपुट
Postorder successor of 4 is 2