আমাদের একটি অ্যারে দেওয়া হয়েছে [] যাতে একটি বাইনারি গাছের ইনঅর্ডার ট্রাভার্সাল থাকে। লক্ষ্য হল সেই অ্যারে থেকে একটি বিশেষ বাইনারি গাছ তৈরি করা। একটি বিশেষ বাইনারি গাছ হল যেটির রুট নোডের ওজন তার বাম এবং ডান উভয় সন্তানের ওজনের চেয়ে বেশি।
উদাহরণস্বরূপ
ইনপুট
int arr[] = {10, 20, 28, 40, 32, 31, 30} আউটপুট
বিশেষ বাইনারি ট্রি যা প্রদত্ত ইনঅর্ডারট্রাভার্সাল দিয়ে তৈরি করা হবে তা নীচে দেওয়া হল −
ব্যাখ্যা
we are given with an array of integer values or the inorder traversal of a tree. So, the special tree formed is 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 −
ব্যাখ্যা
we are given with an array of integer values or the inorder traversal of a tree. So, the special tree formed is 10, 20, 25, 28, 40, 32, 31, 30, 35.
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
এই পদ্ধতিতে আমরা রুট নোড হিসাবে সর্বাধিক উপাদান নিয়ে প্রদত্ত অ্যারে থেকে বিশেষ বাইনারি ট্রি তৈরি করব। এর বাম উপাদানগুলি বাম সাবট্রির অংশে পরিণত হবে এবং এটির ডান উপাদানগুলি ডান সাবট্রির অংশে পরিণত হবে৷ এই প্রক্রিয়াটি পুনরাবৃত্তভাবে গাছ তৈরির জন্য করা হয়৷
-
inorder traversal ধারণকারী একটি ইনপুট অ্যারে হিসাবে arr[] নিন।
-
ফাংশন new_node (int data) বাম এবং ডান শিশুদের NULL হিসাবে একটি নোড তৈরি করে৷
-
ফাংশন মোট (int arr[], int first, int last) সেই উপাদানটির সূচী প্রদান করে।
-
সর্বোচ্চ =arr[প্রথম] এবং সর্বনিম্ন =প্রথম।
নিন -
প্রথম+1 সূচক থেকে শেষ পর্যন্ত ট্র্যাভার্স করুন এবং যদি কোনো উপাদান arr[i] সর্বোচ্চ থেকে বেশি পাওয়া যায় তাহলে তার সূচক সর্বনিম্নে সংরক্ষণ করুন এবং সর্বোচ্চ আপডেট করুন।
-
সর্বনিম্ন লুপের শেষে সর্বোচ্চ উপাদানের সূচক থাকবে।
-
ফাংশন create_tree (int arr[], int first, int last) arr[] থেকে বিশেষ বাইনারি ট্রি তৈরি করে।
-
যদি প্রথমে>শেষ হয় তাহলে NULL দিন কারণ ট্রি সম্ভব হবে না।
-
temp =total(arr, first, last) ব্যবহার করে অ্যারের সর্বোচ্চ মান হিসাবে temp নিন।
-
ডেটা হিসাবে টেম্প সহ একটি নোড তৈরি করুন এবং গাছের রুটনোডের জন্য একটি পয়েন্টার প্যারেন্ট পয়েন্ট তৈরি করুন৷
-
যদি প্রথম==শেষ হয় তাহলে গাছের শুধুমাত্র একটি নোড থাকবে। রিটার্ন প্যারেন্ট।
-
পুনরাবৃত্তভাবে অভিভাবক->left =create_tree(arr, first, temp −1);
গণনা করুন -
এবং পিতামাতা−>right =create_tree(arr, temp + 1, last).
-
শেষে অভিভাবককে ফিরিয়ে দিন।
-
ফাংশন Inorder_traversal(tree_node* node) উপরে উত্পন্ন ট্রির ইনঅর্ডার ট্রাভার্সাল প্রিন্ট করে।
-
যদি নোডটি NULL হয় তবে কিছুই ফেরত দেয় না। অন্যথায় প্রথমে Inorder_traversal(node−>left) ব্যবহার করে বাম সাবট্রি প্রিন্ট করুন।
-
তারপর বর্তমান নোড প্রিন্ট করুন।
-
তারপর Inorder_traversal (node−>right)
ব্যবহার করে ডান সাবট্রি প্রিন্ট করুন
উদাহরণ
#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
