इस समस्या में, हमें एक ट्री दिया गया है। संरचना में एक पॉइंटर next होता है। हमारा कार्य इस पॉइंटर को नोड के इनऑर्डर सक्सेसर के साथ भरना है।
struct node {
int value;
struct node* left;
struct node* right;
struct node* next;
}
सभी नेक्स्ट पॉइंटर्स NULL पर सेट हैं और हमें पॉइंटर को नोड के इनऑर्डर सक्सेसर पर सेट करना है।
इनऑर्डर ट्रैवर्सल - यह निम्न रूप में ट्रैवर्स करता है,
बायां नोड -> रूट नोड -> दायां नोड।
इनऑर्डर सक्सेसर - इनऑर्डर सक्सेसर वह नोड है जो ट्री के इनऑर्डर ट्रैवर्सल में वर्तमान नोड के बाद आता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,

इन-ऑर्डर ट्रैवर्सल है 7 8 3 5 9 1
प्रत्येक नोड को भरना:
5 का नेक्स्ट 9 है 8 का नेक्स्ट 3 है 7 का नेक्स्ट 8 है 3 का नेक्स्ट 5 है 9 का नेक्स्ट 1 है
इस समस्या को हल करने के लिए, हम ट्री को ट्रैवर्स करेंगे लेकिन रिवर्स इनऑर्डर फॉर्म में। फिर हम अंतिम विज़िट किए गए एलिमेंट को नंबर के नेक्स्ट में डालेंगे।
उदाहरण
हमारे समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम,
#include <iostream>
using namespace std;
struct node {
int data;
node *left;
node *right;
node *next;
};
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
Node->next = NULL;
return(Node);
}
void populateTree(node* pop) {
static node *next = NULL;
if (pop) {
populateTree(pop->right);
pop->next = next;
next = pop;
populateTree(pop->left);
}
}
void printNext(node * root) {
node *ptr = root->left->left;
while(ptr) {
cout << "Next of " << ptr->data << " is ";
cout << (ptr->next ? ptr->next->data : -1) << endl;
ptr = ptr->next;
}
}
int main() {
node *root = insertNode(15);
root->left = insertNode(99);
root->right = insertNode(1);
root->left->left = insertNode(76);
root->left->right = insertNode(31);
cout << "इनऑर्डर सक्सेसर को नेक्स्ट में जोड़कर ट्री भर रहे हैं\n";
populateTree(root);
printNext(root);
return 0;
}
आउटपुट
इनऑर्डर सक्सेसर को नेक्स्ट में जोड़कर ट्री भर रहे हैं
76 का नेक्स्ट 99 है 99 का नेक्स्ट 31 है 31 का नेक्स्ट 15 है 15 का नेक्स्ट 1 है 1 का नेक्स्ट -1 है