মান লোয়া একটি প্রি-অর্ডার ট্রাভার্সাল। এই ট্রাভার্সাল থেকে আমাদের ট্রি তৈরি করতে হবে। যদি ট্রাভার্সাল [10, 5, 1, 7, 40, 50] হয়, তবে ট্রি হবে নিচের মতো −
এটি সমাধানের জন্য আমরা এই ট্রিকটি ব্যবহার করব। ট্রিকটি হলো প্রতিটি নোডের জন্য একটি রেঞ্জ {min… max} সেট করা। প্রথমে আমরা রেঞ্জটি ইনিশিয়ালাইজ করব {INT_MIN… INT_MAX} হিসেবে। প্রথম নোড নিঃসন্দেহে রেঞ্জের মধ্যে থাকবে, তাই এরপর আমরা রুট নোড তৈরি করব। বাম সাবট্রি কনস্ট্রাক্ট করতে, রেঞ্জ সেট করব {INT_MIN… root->data}। যদি কোনো মান রেঞ্জ {INT_MIN… root->data}-এর মধ্যে পড়ে, তবে সেটি বাম সাবট্রির অংশ। ডান সাবট্রি কনস্ট্রাক্ট করতে, রেঞ্জ সেট করব {root->data… max… INT_MAX}।
উদাহরণ
#include <iostream> 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* makeTreeUtil( int pre[], int* preord_index, int key, int min, int max, int size ) { if( *preord_index >= size ) return NULL; node* root = NULL; if( key > min && key < max ){ root = getNode( key ); *preord_index += 1; if (*preord_index < size){ root->left = makeTreeUtil( pre, preord_index, pre[*preord_index], min, key, size ); root->right = makeTreeUtil( pre, preord_index, pre[*preord_index],key, max, size ); } } return root; } node *makeTree (int pre[], int size) { int preord_index = 0; return makeTreeUtil( pre, &preord_index, pre[0], INT_MIN, INT_MAX, size ); } 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 = makeTree(pre, size); cout << "Inorder traversal: "; inord(root); }আউটপুট
Inorder traversal: 1 5 7 10 40 50
