ধরুন আমাদের একটি প্রি অর্ডার ট্রাভার্সাল আছে। এই ট্রাভার্সাল থেকে. আমাদের গাছ তৈরি করতে হবে তাই যদি ট্রাভার্সাল হয় [10, 5, 1, 7, 40, 50], তাহলে গাছটি হবে −
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
খালি স্ট্যাক তৈরি করুন
-
প্রথম মানটিকে রুট হিসাবে তৈরি করুন এবং এটিকে স্ট্যাকের মধ্যে পুশ করুন।
-
স্ট্যাক খালি না থাকা অবস্থায় এখন পপিং করতে থাকুন এবং পরবর্তী মানটি স্ট্যাকের টপ এলিমেন্টের চেয়ে বেশি, এটিকে শেষ পপড নোডের রাইট চাইল্ড হিসাবে করুন। এখন নতুন নোডটিকে স্ট্যাকের দিকে ঠেলে দিন।
-
পরবর্তী মান শীর্ষ উপাদান থেকে কম হলে, এটি স্ট্যাক শীর্ষ উপাদানের বাম সন্তান হিসাবে করুন. এখন নতুন নোডটিকে স্ট্যাকের মধ্যে চাপুন।
-
যতক্ষণ না আমরা প্রি-অর্ডার তালিকার সমস্ত উপাদান চেক না করি ততক্ষণ ধাপ 2 এবং 3 পুনরাবৃত্তি করুন।
উদাহরণ
#include <iostream>
#include <stack>
using namespace std;
class node {
public:
int data;
node *left;
node *right;
};
node* getNode (int data) {
node* temp = new node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
node* constructTree ( int pre[], int size ) {
stack<node*> stk;
node* root = getNode( pre[0] );
stk.push(root);
int i;
node* temp;
for ( i = 1; i < size; ++i ) {
temp = NULL;
while ( !stk.empty() && pre[i] > stk.top()->data ) {
temp = stk.top();
stk.pop();
}
if ( temp != NULL) {
temp->right = getNode( pre[i] );
stk.push(temp->right);
} else {
node* peek_node = stk.top();
peek_node->left = getNode( pre[i] );
stk.push(stk.top()->left);
}
}
return root;
}
void inord (node* node) {
if (node == NULL)
return;
inord(node->left);
cout << node->data << " ";
inord(node->right);
}
int main () {
int pre[] = {10, 5, 1, 7, 40, 50};
int size = sizeof( pre ) / sizeof( pre[0] );
node *root = constructTree(pre, size);
cout << "Inorder traversal: ";
inord(root);
} আউটপুট
Inorder traversal: 1 5 7 10 40 50
