इस समस्या में, हमें एक बाइनरी ट्री और एक नोड मान दिया जाता है। हमारा काम नोड के प्रीऑर्डर सक्सेसर को प्रिंट करना है।
बाइनरी ट्री एक विशेष प्रकार का पेड़ है जिसमें प्रत्येक रूट नोड में अधिकतम 2 चाइल्ड नोड हो सकते हैं।
ट्रैवर्सल अग्रिम-आदेश पेड़ के नोड्स को पार करने का एक तरीका है। इसमें हम पहले रूट नोड, फिर लेफ्ट चाइल्ड और फिर राइट चाइल्ड को ट्रेस करेंगे।
प्रीऑर्डर उत्तराधिकारी नोड वह नोड है जो नोड के प्रीऑर्डर ट्रैवर्सल में नोड के बगल में आता है।
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं
Input: 9 Output 0 Explanation: the preorder traversal of the tree is: 5 9 0 1 2 5. So the preorder successor of 9 is 0.
इस समस्या को हल करने के लिए, बाइनरी ट्री के प्रीऑर्डर ट्रैवर्सल को खोजने के लिए एक नौसेना दृष्टिकोण होगा और फिर दिए गए नंबर के बाद आने वाले तत्व को प्रिंट करें।
एक अधिक प्रभावी समाधान में दी गई संख्या की स्थिति की जांच करना और फिर पदों के आधार पर उसके उत्तराधिकारी की खोज करना शामिल होगा। इसलिए, यदि स्थिति में एक बायां बच्चा है, तो प्रीऑर्डर उत्तराधिकारी बचा हुआ बच्चा है। यदि यह एक लीफ नोड है लेकिन बच्चा छोड़ दिया गया है तो इसका सिबलिंग नोड प्रीऑर्डर उत्तराधिकारी है। यदि यह एक लीफ नोड है और इसमें कोई बच्चा नहीं है तो हमें इसके पूर्वज नोड्स तक जाना होगा, जिनके चाइल्ड नोड्स प्रीऑर्डर उत्तराधिकारी होंगे।
कार्यक्रम समाधान को और स्पष्ट करेगा
उदाहरण
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int key;
};
Node* insertNode(int key){
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->key = key;
return temp;
}
Node* preOrderSuccessorNode(Node* root, Node* n){
if (n->left)
return n->left;
Node *curr = n, *parent = curr->parent;
while (parent != NULL && parent->right == curr) {
curr = curr->parent;
parent = parent->parent;
}
if (parent == NULL)
return NULL;
return parent->right;
}
int main(){
Node* root = insertNode(99);
root->parent = NULL;
root->left = insertNode(4);
root->left->parent = root;
root->left->left = insertNode(18);
root->left->left->parent = root->left;
root->left->right = insertNode(50);
root->left->right->parent = root->left;
root->right = insertNode(26);
root->right->parent = root;
root->right->left = insertNode(5);
root->right->left->parent = root->right;
root->right->right = insertNode(10);
root->right->right->parent = root->right;
Node* preOrder = preOrderSuccessorNode(root, root->left->right);
if (preOrder) {
cout<<"Preorder successor of "<<root->left->right->key<<" is "<<preOrder->key;
} else {
cout<<"Preorder successor of "<<root->left->right->key<<" is NULL";
}
return 0;
} आउटपुट
Preorder successor of 50 is 26