আমাদের একটি অ্যারে arr[] দেওয়া আছে যেটি একটি বাইনারি ট্রির ইনঅর্ডার ট্রভারসাল ধারণ করে। লক্ষ্য হলো সেটি থেকে একটি স্পেশাল বাইনারি ট্রি নির্মাণ করা। স্পেশাল বাইনারি ট্রি বলতে একে বুঝায় যেটির রুট নোডের ওজন এর লেফট ও রাইট দুটি চাইল্ডের ওজনদ্বয় থেকে বড়।
ইনপুট
int arr[] = {10, 20, 28, 40, 32, 31, 30}
আউটপুট
দেওয়া ইনঅর্ডার ট্রভারসাল থেকে নির্মিত স্পেশাল বাইনারি ট্রি নিচে দেওয়া আছে:
ব্যাখ্যা
আমাদের ইন্টিজার ভ্যালুর একটি অ্যারে বা একটি ট্রির ইনঅর্ডার ট্রভারসাল দেওয়া আছে। সুতরাং তৈরি স্পেশাল ট্রি হলো: 10, 20, 28, 40, 32, 31, 30
ইনপুট
int arr[] = {10, 20, 25, 28, 40, 32, 31, 30, 35}
আউটপুট
The special binary tree which will be constructed with the given inorder traversal is given below −
ব্যাখ্যা
আমাদের ইন্টিজার ভ্যালুর একটি অ্যারে বা একটি ট্রির ইনঅর্ডার ট্রভারসাল দেওয়া আছে। সুতরাং তৈরি স্পেশাল ট্রি হলো: 10, 20, 25, 28, 40, 32, 31, 30, 35।
প্রোগ্রামে ব্যবহৃত পদ্ধতি:
এই পদ্ধতিতে আমরা দেয়া অ্যারে থেকে সর্বোচ্চ এলিমেন্টকে রুট নোড হিসেবে নিই। সেটির বাম পাশের এলিমেন্টগুলো লেফট সাবট্রির অংশ হবে এবং ডান পাশের এলিমেন্টগুলো রাইট সাবট্রির অংশ। এই প্রক্রিয়া রিকারসিভলি চলিয়ে ট্রি নির্মাণ করা হয়।
- ইনপুট অ্যারে হিসেবে
arr[]নেওয়া হয়। new_node(int data)ফাংশন লেফট ও রাইট চাইল্ড NULL দিয়ে একটি নোড তৈরি করে।total(int arr[], int first, int last)ফাংশন সর্বোচ্চ এলিমেন্টের ইনডেক্স রিটার্ন করে।- সর্বোচ্চ =
arr[first]এবং ইনডেক্স =firstধরা হয়। first+1থেকেlastপর্যন্ত ট্রভারস করে যদিarr[i]সর্বোচ্চ থেকে বড় পাওয়া যায় তবে ইনডেক্স এবং সর্বোচ্চ আপডেট করা হয়।- লুপ শেষে ইনডেক্সটি সর্বোচ্চ এলিমেন্টের ইনডেক্স ধারণ করবে।
create_tree(int arr[], int first, int last)ফাংশন রিকারসিভলি স্পেশাল বাইনারি ট্রি তৈরি করে।first > lastহলে NULL রিটার্ন করা হয়।temp = total(arr, first, last)দিয়ে অ্যারের সর্বোচ্চ মান বের করা হয়।tempডেটা দিয়ে একটি নোড তৈরি করে পয়েন্টারparentসেট করা হয়।first == lastহলে শুধু একটি নোড থাকে,parentরিটার্ন করা হয়।- রিকারসিভলি
parent->left = create_tree(arr, first, temp-1)এবংparent->right = create_tree(arr, temp+1, last)। - শেষে
parentরিটার্ন করা হয়। Inorder_traversal(tree_node* node)ফাংশন জেনারেট করা ট্রির ইনঅর্ডার ট্রভারসাল প্রিন্ট করে।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int total(int arr[], int first, int last);
class tree_node {
public:
int data;
tree_node* left;
tree_node* right;
};
tree_node* new_node(int data);
tree_node* create_tree(int arr[], int first, int last) {
if (first > last) {
return NULL;
}
int temp = total(arr, first, last);
tree_node* parent = new_node(arr[temp]);
if (first == last) {
return parent;
}
parent->left = create_tree(arr, first, temp - 1);
parent->right = create_tree(arr, temp + 1, last);
return parent;
}
int total(int arr[], int first, int last) {
int highest = arr[first];
int lowest = first;
for (int i = first + 1; i <= last; i++) {
if (arr[i] > highest) {
highest = arr[i];
lowest = i;
}
}
return lowest;
}
tree_node* new_node(int data) {
tree_node* newNode = new tree_node();
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void Inorder_traversal(tree_node* node) {
if (node == NULL) {
return;
}
Inorder_traversal(node->left);
cout << node->data << " ";
Inorder_traversal(node->right);
}
int main() {
int arr[] = {10, 20, 28, 40, 32, 31, 30};
int size = sizeof(arr) / sizeof(arr[0]);
tree_node* root = create_tree(arr, 0, size - 1);
cout << "Construct Special Binary Tree from given Inorder traversal are: " << "\n";
Inorder_traversal(root);
return 0;
}
আউটপুট
Construct Special Binary Tree from given Inorder traversal are: 10 20 28 40 32 31 30
