हमें एक सरणी arr[] दी गई है जिसमें बाइनरी ट्री का इनऑर्डर ट्रैवर्सल है। लक्ष्य उस सरणी से एक विशेष बाइनरी ट्री बनाना है। एक विशेष बाइनरी ट्री वह होता है जिसका रूट नोड का वजन उसके बाएं और दाएं दोनों बच्चों के वजन से अधिक होता है।
उदाहरण के लिए
इनपुट
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.
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम दिए गए सरणी से अधिकतम तत्व को रूट नोड के रूप में लेते हुए विशेष बाइनरी ट्री का निर्माण करेंगे। उस के बाएँ तत्व बाएँ सबट्री का हिस्सा बनेंगे और उसके दाएँ तत्व राइट सबट्री का हिस्सा बनेंगे। यह प्रक्रिया ट्री के निर्माण के लिए पुनरावर्ती रूप से की जाती है।
-
arr[] को इनऑर्डर ट्रैवर्सल वाले इनपुट ऐरे के रूप में लें।
-
फ़ंक्शन new_node (इंट डेटा) बाएं और दाएं बच्चों के साथ NULL के रूप में एक नोड बनाता है।
-
फंक्शन टोटल(int arr[], int first, int last) उस एलिमेंट का इंडेक्स लौटाता है।
-
उच्चतम =एआर [प्रथम] और निम्नतम =प्रथम लें।
-
प्रथम+1 अनुक्रमणिका से अंतिम तक ट्रैवर्स और यदि कोई तत्व arr[i] उच्चतम से अधिक पाया जाता है तो उसके सूचकांक को निम्नतम में संग्रहीत करें और उच्चतम अद्यतन करें।
-
लूप के अंत में निम्नतम में उच्चतम तत्व का सूचकांक होगा।
-
फ़ंक्शन create_tree (int arr[], int first, int last) विशेष बाइनरी ट्री को arr[] से पुनरावर्ती रूप से बनाता है।
-
अगर पहले>आखिरी है तो NULL लौटाएं क्योंकि ट्री संभव नहीं होगा।
-
अस्थायी =कुल (गिरफ्तारी, पहले, अंतिम) का उपयोग करके सरणी के अधिकतम मान के रूप में अस्थायी लें।
-
डेटा के रूप में अस्थायी के साथ एक नोड बनाएं और पेड़ के रूटनोड के लिए एक पॉइंटर पैरेंट पॉइंट बनाएं।
-
अगर पहला ==आखिरी है तो पेड़ में केवल एक नोड होगा। माता-पिता को लौटें।
-
माता-पिता की पुनरावर्ती गणना करें-> बाएं =create_tree (गिरफ्तारी, पहले, अस्थायी -1);
-
और पैरेंट−>राइट =create_tree(arr, temp + 1, last).
-
अंत में माता-पिता को लौटा दें।
-
फ़ंक्शन Inorder_traversal(tree_node* node) ऊपर जेनरेट किए गए ट्री के इनऑर्डर ट्रैवर्सल को प्रिंट करता है।
-
यदि नोड NULL है तो कुछ भी वापस न करें। बाकी सबट्री पहले इनऑर्डर_ट्रैवर्सल(नोड−>बाएं) का उपयोग करके प्रिंट करें।
-
फिर वर्तमान नोड को प्रिंट करें।
-
फिर Inorder_traversal (नोड−>दाएं) का उपयोग करके सही सबट्री प्रिंट करें।
उदाहरण
#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