মান লোয়া একটি লেভেল অর্ডার ট্রাভার্সাল। এই ট্রাভার্সাল থেকে আমাদের ট্রি তৈরি করতে হবে। যদি ট্রাভার্সাল [7, 4, 12, 3, 6, 8, 1, 5, 10] হয়, তবে ট্রি হবে নিচের মতো −
এটি সমাধানের জন্য আমরা রিকার্সিভ পদ্ধতি ব্যবহার করব। প্রথম এলিমেন্ট হবে রুট। দ্বিতীয় এলিমেন্ট হবে লেফ্ট চাইল্ড, এবং তৃতীয় এলিমেন্ট হবে রাইট চাইল্ড (যদি BST-এর শর্ত পূরণ হয়), এই প্রপার্টি সকল এলিমেন্টের জন্য সত্য থাকবে। তাই আমরা নিচের ধাপগুলো অনুসরণ করব −
প্রথমে অ্যারের প্রথম এলিমেন্ট নিতে হবে, এবং এটিকে রুট বানাতে হবে।
তারপর দ্বিতীয় এলিমেন্ট নিন। যদি সেটি রুটের চেয়ে ছোট হয়, তবে লেফ্ট চাইল্ড বানান অন্যথায় রাইট চাইল্ড
তারপর ধাপ ২ রিকার্সিভলি কল করে BST বানান।
উদাহরণ
#include <iostream> using namespace std; class Node { public: int data; Node *left, *right; }; Node* getNode(int data) { Node *newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } Node *lvlOrd(Node *root , int data) { if(root==NULL){ root = getNode(data); return root; } if(data <= root->data) root->left = lvlOrd(root->left, data); else root->right = lvlOrd(root->right, data); return root; } Node* makeTree(int arr[], int n) { if(n==0) return NULL; Node *root= NULL; for(int i=0;i<n;i++) root = lvlOrd(root , arr[i]); return root; } void inord(Node* root) { if (!root) return; inord(root->left); cout << root->data << " "; inord(root->right); } int main() { int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10}; int n = sizeof(arr) / sizeof(arr[0]); Node *root = makeTree(arr, n); cout << "Inorder Traversal: "; inord(root); }আউটপুট
Inorder Traversal: 1 3 4 5 6 7 8 10 12
