C++ में इसके प्रीऑर्डर ट्रैवर्सल से पूर्ण k-ary ट्री का निर्माण करें

हमें एक ऐरे arr[] दिया गया है जिसमें क्रम में k-ary ट्री का प्रीऑर्डर ट्रैवर्सल है। लक्ष्य उसी से उसी k-ary ट्री का निर्माण करना है और उसके पोस्टऑर्डर ट्रैवर्सल को प्रिंट करना है। एक पूर्ण k−ary ट्री वह होता है जिसमें रूट नोड में 0 या k बच्चे होते हैं यानी अधिकतम k बच्चा।

उदाहरण के लिए

इनपुट

int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 2

आउटपुट

पूर्ण k−ary ट्री जिसका निर्माण पूर्व-आदेश ट्रैवर्सल से दो बच्चों के साथ किया जाएगा, नीचे दिया गया है -

स्पष्टीकरण

हमें पूर्णांक मानों की एक सरणी या k बच्चों के साथ एट्री के प्रीऑर्डर ट्रैवर्सल के साथ दिया जाता है। तो, गठित पेड़ में पोस्टऑर्डर ट्रैवर्सल 3 6 1 2 1 7 5 2 होगा जो कि नियम के अनुसार बनाया गया है जो कहता है सभी LEFT सबट्री नोड्स पर जाएँ, फिर सभी राइट सबट्री नोड्स पर जाएँ और फिर सभी ROOT नोड्स पर जाएँ।

इनपुट

int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 3

आउटपुट

पूर्ण k−ary पेड़ जो तीन बच्चों के साथ पूर्व-आदेश ट्रैवर्सल से बनाया जाएगा, नीचे दिया गया है -

स्पष्टीकरण

हमें के बच्चों के साथ पूर्णांक मानों की एक सरणी या एट्री के प्रीऑर्डर ट्रैवर्सल के साथ दिया जाता है। इसलिए, गठित पेड़ में पोस्टऑर्डर ट्रैवर्सल 3 6 1 2 1 7 5 2 होगा जो कि नियम के अनुसार बनाया गया है जो कहता है सभी LEFT सबट्री नोड्स पर जाएँ, फिर सभी राइट सबट्री नोड्स पर जाएँ और फिर सभी ROOT नोड्स पर जाएँ।

नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -

इस दृष्टिकोण में हम पहले दिए गए सरणी से पहले तत्व को रूट नोड के रूप में लेते हुए k-ary ट्री का निर्माण करेंगे। यदि बायां उपट्री खाली है तो दायां उपट्री भी खाली होगा। बाएँ और दाएँ सबट्री के लिए रिकर्सिवली कॉल करें और उन्हें लिंक करें। पोस्टऑर्डर ट्रैवर्सल के लिए हम लेफ्ट सबट्री लेते हैं, फिर राइट सबट्री और फिर नोड के वेट को प्रिंट करते हैं।

• कॉल पोस्टऑर्डर(रूट−>बाएं)

• कॉल पोस्टऑर्डर(रूट−>दाएं)

• प्रिंट रूट−>डेटा

• arr[] को एक इनपुट ऐरे के रूप में लें जिसमें प्रीऑर्डर ट्रैवर्सल हो।

• k को चर बच्चों के रूप में लें।

• शुरुआती इंडेक्स को गिनती =0 के रूप में लें।

• Tree_Node* नोड =create_tree (गिरफ्तारी, आकार, बच्चे, गिनती) का उपयोग करके पेड़ का निर्माण करें।

• फ़ंक्शन new_Node(int data) पेड़ का एक नया नोड उत्पन्न करता है।

• फंक्शन create_tree(int arr[], int N, int k, int height, int&count) एरे arr[] से कैरी ट्री जनरेट करता है।

• यदि नोड्स की संख्या <=0 है, तो NULL लौटाएं, कोई पेड़ नहीं बनाया जा सकता है।

• newNode =new_Node (गिरफ्तारी [गिनती]) प्रारंभ करें, गिरफ्तारी का पहला तत्व []।

• यदि (newNode ==NULL) परिणाम सत्य है तो कोई पेड़ संभव नहीं है।

• ट्रैवर्स एआर [] लूप के लिए i=0 से i . का उपयोग करते हुए

• अगर (गिनती 1) तो अगली अनुक्रमणिका के लिए गिनती बढ़ाएं और newNode−>root.push_back(create_tree(arr, N, k, ऊंचाई -1, गिनती)) का उपयोग करके इस नोड को ट्री में जोड़ें।

• अन्यथा newNode−>root.push_back(NULL);

  . का उपयोग करके NULL को पुश करके ट्री को समाप्त करें

• अंत में पॉइंटर को नोड पर लौटा दें।

• फ़ंक्शन create_tree(int* arr, int N, int k, int count) पेड़ की ऊंचाई लौटाता है।

• ऊंचाई की गणना करें =(इंट) छत (लॉग ((डबल) एन * (के -1) + 1) / लॉग ((डबल) के));

• ऊपर परिकलित ऊंचाई पर पेड़ के लिए रिटर्न स्टेटमेंट में create_tree(arr, N, k, height, count) पर कॉल करें।

• फ़ंक्शन postorder_traversal(Tree_Node* node, int k) नोड पर निहित k−ary ट्री के प्रीऑर्डरट्रैवर्सल को प्रिंट करता है।

• यदि नोड NULL है तो कुछ भी वापस न करें।

• लूप के लिए i=0 से iroot[i], k);

• लूप के अंत में नोड-> पता प्रिंट करें।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
struct Tree_Node{
   int address;
   vector<Tree_Node*> root;
};
Tree_Node* new_Node(int data){
   Tree_Node* newNode = new Tree_Node;
   newNode−>address = data;
   return newNode;
}
Tree_Node* create_tree(int arr[], int N, int k, int height, int& count){
   if(N <= 0){
      return NULL;
   }
   Tree_Node* newNode = new_Node(arr[count]);
   if (newNode == NULL){
      cout<<"Code Dumped";
      return NULL;
   }
   for(int i = 0; i < k; i++){
      if (count < N − 1 && height > 1){
         count++;
         newNode−>root.push_back(create_tree(arr, N, k, height − 1, count));
      }else{
         newNode−>root.push_back(NULL);
      }
   }
   return newNode;
}
Tree_Node* create_tree(int* arr, int N, int k, int count){
   int height = (int)ceil(log((double)N * (k − 1) + 1) / log((double)k));
   return create_tree(arr, N, k, height, count);
}
void preorder_traversal(Tree_Node* node, int k){
   if (node == NULL){
      return;
   }
   for(int i = 0; i < k; i++){
      preorder_traversal(node−>root[i], k);
   }
   cout<<node−>address<< " ";
}
int main(){
   int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 };
   int size = 8;
   int children = 2;
   int count = 0;
   Tree_Node* node = create_tree(arr, size, children, count);
   cout<<"Construct the full k−ary tree from its preorder traversal are: ";
   preorder_traversal(node, children);
   return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -

Construct the full k-ary tree from its preorder traversal are: 3 6 1 2 1 7 5 2