इस समस्या में हमें एक पेड़ दिया जाता है। संरचना में अगला सूचक होता है। हमारा काम इस पॉइंटर को इनऑर्डर सक्सेसर . के साथ पॉप्युलेट करना है नोड का।
struct node {
int value;
struct node* left;
struct node* right;
struct node* next;
} अगले सभी पॉइंटर को NULL पर सेट किया जाता है और हमें पॉइंटर को नोड के इनऑर्डर सक्सेसर पर सेट करना होता है।
इनऑर्डर ट्रैवर्सल - यह निम्नलिखित रूप में चलता है,
Left node -> root Node -> right node.
इनऑर्डर उत्तराधिकारी - इनऑर्डर उत्तराधिकारी वह नोड है जो वर्तमान नोड के बाद आता है जो पेड़ का इनऑर्डर ट्रैवर्सल है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
क्रम में ट्रैवर्सल 7 8 3 5 9 1
. हैप्रत्येक नोड को आबाद करना -
Next of 5 is 9 Next of 8 is 3 Next of 7 is 8 Next of 3 is 5 Next of 9 is 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<<"Populating the Tree by adding inorder successor to the next\n";
populateTree(root);
printNext(root);
return 0;
} आउटपुट
अगले क्रमागत उत्तराधिकारी को जोड़कर वृक्ष को आबाद करना
Next of 76 is 99 Next of 99 is 31 Next of 31 is 15 Next of 15 is 1 Next of 1 is -1