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