हमें एक सरणी arr[] दी गई है जिसमें k-एरी ट्री का प्रीऑर्डर ट्रैवर्सल क्रम में है। लक्ष्य उसी k-एरी ट्री को उससे बनाना और उसका पोस्टऑर्डर ट्रैवर्सल प्रिंट करना है। एक फुल k-एरी ट्री वह है जिसमें रूट नोड के 0 या k चाइल्ड होते हैं यानी अधिकतम k चाइल्ड।
उदाहरण के लिए
इनपुट
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 2 आउटपुट
प्रीऑर्डर ट्रैवर्सल से दो चाइल्ड वाले फुल k-एरी ट्री को नीचे दिखाया गया है:

व्याख्या
हमें पूर्णांक मानों की एक सरणी या 2 चाइल्ड वाले ट्री का प्रीऑर्डर ट्रैवर्सल दिया गया है। तो बने ट्री का पोस्टऑर्डर ट्रैवर्सल 3 6 1 2 1 7 5 2 होगा जो नियम के अनुसार बनाया गया है कि सभी लेफ्ट सबट्री नोड्स पर जाएं फिर सभी राइट सबट्री नोड्स पर जाएं और फिर सभी रूट नोड्स पर जाएं।
इनपुट
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 3 आउटपुट
प्रीऑर्डर ट्रैवर्सल से तीन चाइल्ड वाले फुल k-एरी ट्री को नीचे दिखाया गया है:

व्याख्या
हमें पूर्णांक मानों की एक सरणी या 3 चाइल्ड वाले ट्री का प्रीऑर्डर ट्रैवर्सल दिया गया है। तो बने ट्री का पोस्टऑर्डर ट्रैवर्सल 3 6 1 2 1 7 5 2 होगा जो नियम के अनुसार बनाया गया है कि सभी लेफ्ट सबट्री नोड्स पर जाएं फिर सभी राइट सबट्री नोड्स पर जाएं और फिर सभी रूट नोड्स पर जाएं।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:
इस दृष्टिकोण में हम पहले दिए गए सरणी से k-एरी ट्री बनाएंगे जिसमें पहले एलिमेंट को रूट नोड के रूप में लेंगे। यदि लेफ्ट सबट्री खाली है तो राइट भी खाली होगी। लेफ्ट और राइट सबट्री के लिए रिकर्सिवली कॉल करें और उन्हें लिंक करें। पोस्टऑर्डर ट्रैवर्सल के लिए हम लेफ्ट सबट्री लेते हैं, फिर राइट सबट्री और फिर नोड का वजन प्रिंट करते हैं।
postorder(root->left) कॉल करें
postorder(root->right) कॉल करें
root->data प्रिंट करें
इनपुट सरणी के रूप में arr[] लें जिसमें प्रीऑर्डर ट्रैवर्सल है।
k को वेरिएबल चाइल्ड के रूप में लें।
शुरुआती इंडेक्स को count=0 के रूप में लें।
Tree_Node* node = create_tree(arr, size, children, count) का उपयोग करके ट्री बनाएं।
फ़ंक्शन new_Node(int data) ट्री का नया नोड उत्पन्न करता है।
फ़ंक्शन create_tree(int arr[], int N, int k, int height, int& count) सरणी arr[] से k-एरी ट्री उत्पन्न करता है।
यदि नोड्स की संख्या <=0 है तो NULL लौटाएं, कोई ट्री नहीं बनाया जा सकता।
newNode = new_Node(arr[count]) इनिशियलाइज़ करें, arr[] का पहला एलिमेंट।
यदि (newNode == NULL) ट्रू है तो कोई ट्री संभव नहीं।
i=0 से i
यदि (count < N - 1 && height > 1) तो अगले इंडेक्स के लिए count बढ़ाएं और इस नोड को ट्री में जोड़ें newNode->root.push_back(create_tree(arr, N, k, height - 1, count)) का उपयोग करके।
अन्यथा newNode->root.push_back(NULL) का उपयोग करके NULL को पुश करके ट्री को समाप्त करें।
अंत में नोड का पॉइंटर लौटाएं।
फ़ंक्शन create_tree(int* arr, int N, int k, int count) ट्री की ऊंचाई लौटाता है।
height= (int)ceil(log((double)N * (k - 1) + 1) / log((double)k)) की गणना करें।
ऊपर गणना की गई ऊंचाई पर ट्री के लिए रिटर्न स्टेटमेंट में create_tree(arr, N, k, height, count) कॉल करें।
फ़ंक्शन postorder_traversal(Tree_Node* node, int k) नोड पर रूटेड k-एरी ट्री का प्रीऑर्डर ट्रैवर्सल प्रिंट करता है।
यदि नोड NULL है तो कुछ भी नहीं लौटाएं।
i=0 से i
root[i], k) कॉल करें। फॉर लूप के अंत में node->address प्रिंट करें।
उदाहरण
#include <bits/stdc++.h> using namespace std; struct Tree_Node{ int address; vector 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