এই সমস্যাতে, একটি ট্রি দেওয়া আছে। স্ট্রাকচারে একটি next পয়েন্টার আছে। আমাদের কাজ হলো এই পয়েন্টারকে নোডের ইনঅর্ডার সাক্সেসর দিয়ে পপুলেট করা।
struct node {
int value;
struct node* left;
struct node* right;
struct node* next;
} সব 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
সমাধানের জন্য, আমরা ট্রি ট্রাভার্স করব কিন্তু রিভার্স ইনঅর্ডার ফর্মে। তারপর ভিজিট করা শেষ এলিমেন্টকে নম্বারের next-এ রাখব।
উদাহরণ
সমাধানের প্রোগ্রাম:
#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;
} আউটপুট
Populating the Tree by adding inorder successor to the next
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
