এই সমস্যায়, আমাদের একটি গাছ দেওয়া হয়। গঠন পরবর্তী একটি পয়েন্টার রয়েছে. আমাদের কাজ হল এই পয়েন্টারটিকে ইনঅর্ডার উত্তরাধিকারী দিয়ে তৈরি করা নোডের।
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
