हमें एक सरणी 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) उस एलिमेंट का इंडेक्स लौटाता है।
highest = arr[first] और lowest = first लें।
first+1 इंडेक्स से last तक ट्रैवर्स करें और यदि कोई एलिमेंट arr[i] highest से अधिक पाया जाता है तो उसका इंडेक्स lowest में स्टोर करें और highest को अपडेट करें।
फॉर लूप के अंत में lowest में उच्चतम एलिमेंट का इंडेक्स होगा।
फ़ंक्शन create_tree(int arr[], int first, int last) arr[] से रिकर्सिवली स्पेशल बाइनरी ट्री बनाता है।
यदि first > last तो NULL लौटाएं क्योंकि ट्री संभव नहीं है।
temp को सरणी के अधिकतम मान के रूप में लें: temp = total(arr, first, last)।
temp को डेटा के साथ एक नोड बनाएं और रूट नोड के लिए इस पर पॉइंट करने वाला पैरेंट पॉइंटर बनाएं।
यदि first == last तो ट्री में केवल एक नोड होगा। पैरेंट लौटाएं।
रिकर्सिवली पैरेंट->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
