इस समस्या में, हमें एक बाइनरी ट्री और एक नोड मान दिया गया है। हमारा कार्य नोड का प्रीऑर्डर सक्सेसर प्रिंट करना है।
बाइनरी ट्री एक विशेष प्रकार का ट्री है जिसमें प्रत्येक रूट नोड में अधिकतम 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
