ধরুন আমাদের ওয়ান লেভেল অর্ডার ট্রাভার্সাল আছে। এই ট্রাভার্সাল থেকে. আমাদের গাছ তৈরি করতে হবে তাই যদি ট্রাভার্সাল হয় [7, 4, 12, 3, 6, 8, 1, 5, 10], তাহলে গাছটি হবে −
এটি সমাধান করার জন্য, আমরা পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করব। প্রথম উপাদান রুট হবে. দ্বিতীয় উপাদানটি হবে বাম শিশু, এবং তৃতীয় উপাদানটি হবে ডান শিশু (যদি BST-এর শর্ত সন্তুষ্ট হয়), এই সম্পত্তিটি সমস্ত উপাদানের জন্য সন্তুষ্ট হবে৷ তাই আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
প্রথমে আমাদের অ্যারের প্রথম উপাদানটি নিতে হবে এবং এটিকে রুট হিসাবে তৈরি করতে হবে।
-
তারপর দ্বিতীয় উপাদান নিন। যদি এটি মূলের চেয়ে ছোট হয়, তবে এটিকে বাম শিশু অন্যথায় ডান শিশু করুন
-
তারপর BST করার জন্য ধাপ 2 কে বারবার কল করুন।
উদাহরণ
#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
