इस समस्या में, हमें एक बाइनरी ट्री और एक नोड मान दिया गया है। हमारा कार्य नोड का प्रीऑर्डर प्रीडिसेसर प्रिंट करना है।
बाइनरी ट्री एक विशेष प्रकार का ट्री है जिसमें प्रत्येक रूट नोड में अधिकतम 2 चाइल्ड नोड्स हो सकते हैं।
प्रीऑर्डर ट्रैवर्सल ट्री के नोड्स को पार करने का एक तरीका है। इसमें हम पहले रूट नोड को पार करते हैं फिर लेफ्ट चाइल्ड और फिर राइट चाइल्ड।
प्रीऑर्डर प्रीडिसेसर नोड वह नोड है जो प्रीऑर्डर ट्रैवर्सल में नोड से पहले आता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं
Input: 1 Output: 9
इस समस्या को हल करने के लिए, एक साधारण दृष्टिकोण बाइनरी ट्री का प्रीऑर्डर ट्रैवर्सल ढूंढना और फिर दिए गए नंबर के बाद आने वाले एलिमेंट को प्रिंट करना होगा।
एक अधिक प्रभावी समाधान में दिए गए नंबर की स्थिति की जांच करना और फिर स्थितियों के आधार पर उसके प्रीडिसेसर को खोजना शामिल होगा। यदि नोड रूट नोड है, तो NULL लौटाएं, कोई प्रीडिसेसर नहीं। यदि नोड राइट चाइल्ड है, तो लेफ्ट चाइल्ड प्रीडिसेसर होगा।
समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम
उदाहरण
#include <iostream> using namespace std; struct Node { struct Node *left, *right, *parent; int key; }; struct Node* insertNode(int key){ Node* temp = new Node; temp->left = temp->right = temp->parent = NULL; temp->key = key; return temp; } Node* preOrderPredecessorNode(Node* root, Node* n){ if (n == root) return NULL; Node* parent = n->parent; if (parent->left == NULL || parent->left == n) return parent; Node* curr = parent->left; while (curr->right != NULL) curr = curr->right; return curr; } 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* preOrderPredecessor = preOrderPredecessorNode(root, root->left->right); if (preOrderPredecessor) cout<<"Preorder Predecessor of "<<root->left->right->key<<" is "<<preOrderPredecessor->key; else cout<<"Preorder Predecessor of "<<root->left->right->key<<" is NULL"; return 0; }आउटपुट
Preorder Predecessor of 50 is 18
