মান লোয়া একটি প্রি-অর্ডার ট্রাভার্সাল। এই ট্রাভার্সাল থেকে আমাদের ট্রি তৈরি করতে হবে। যদি ট্রাভার্সাল [10, 5, 1, 7, 40, 50] হয়, তবে ট্রি হবে নিচের মতো −
এটি সমাধানের জন্য আমরা নিচের ধাপগুলো অনুসরণ করব −
খালি একটি স্ট্যাক তৈরি করুন
প্রথম ভ্যালুকে রুট বানান, এবং স্ট্যাকে পুশ করুন।
এখন স্ট্যাক খালি না হয়া পর্যন্ত পপ করুন এবং পরবর্তী ভ্যালু স্ট্যাক টপ এলিমেন্টের চেয়ে বড় হলে, সেটিকে লাস্ট পপ করা নোডের রাইট চাইল্ড বানান। এখন নতুন নোডটি স্ট্যাকে পুশ করুন।
যখন পরবর্তী ভ্যালু টপ এলিমেন্টের চেয়ে ছোট হয়, তবে সেটিকে স্ট্যাক টপ এলিমেন্টের লেফ্ট চাইল্ড বানান। এখন নতুন নোডটি স্ট্যাকে পুশ করুন।
ধাপ ২ এবং ৩ রিপিট করুন যতক্ষণ না প্রি-অর্ডার লিস্টের সকল এলিমেন্ট চেক করা হয়।
উদাহরণ
#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
