इस समस्या में, हमें बाइनरी ट्री का इनऑर्डर और पोस्टऑर्डर ट्रैवर्सल दिया गया है। हमारा कार्य ट्री का पोस्टऑर्डर ट्रैवर्सल प्रिंट करना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं
Input:inorder: 16 7 21 12 1 5 9 postorder: 16 21 7 1 9 5 12 Output: preorder: 12 7 16 21 5 1 9 Explanation: the binary tree is :
इस समस्या को हल करने के लिए, एक सरल समाधान दिए गए ट्रैवर्सल का उपयोग करके ट्री बनाना और फिर ट्री का प्रीऑर्डर ट्रैवर्सल ढूंढना हो सकता है। लेकिन यह विधि सिस्टम के लिए अधिक जटिल होगी।
समस्या को हल करने का एक अधिक प्रभावी समाधान स्टैक डेटा संरचना का उपयोग करना है। आइए ट्री के प्रत्येक नोड को देखें। ट्री का रूट पोस्टऑर्डर ट्रैवर्सल में अंतिम आइटम है। अब हमें बाइनरी ट्री के लेफ्ट और राइट सबट्री को अलग करना होगा। चूंकि हम ट्री के रूट नोड को जानते हैं। पोस्टऑर्डर ट्रैवर्सल में, रूट नोड से पहले के सभी एलिमेंट्स लेफ्ट सबट्री के हैं और रूट के बाद के राइट सबट्री के हैं।
इसी तरह, हम सभी एलिमेंट्स ढूंढेंगे और नोड्स को स्टैक में संग्रहीत करेंगे और फिर स्टैक के एलिमेंट्स प्रिंट करेंगे जो प्रीऑर्डर ट्रैवर्सल देता है।
हमारे समाधान का जावा में कार्यान्वयन
उदाहरण
import java.util.Stack; public class Main { static int postIndex; void preOrder(int[] in, int[] post, int inStrt, int inEnd, Stack<Integer> preorder) { if (inStrt > inEnd) return; int val = post[postIndex]; int inIndex = searchValue(in, val); postIndex--; preOrder(in, post, inIndex + 1, inEnd, preorder); preOrder(in, post, inStrt, inIndex - 1, preorder); preorder.push(val); } void printPreOrderTraversal(int[] in, int[] post) { int len = in.length; postIndex = len - 1; Stack<Integer> preorder = new Stack<Integer>(); preOrder(in, post, 0, len - 1, preorder); while (preorder.empty() == false) System.out.print(preorder.pop()+" "); } int searchValue(int[] in, int data){ int i = 0; for (i = 0; i < in.length; i++) if (in[i] == data) return i; return i; } public static void main(String ars[]){ int in[] = { 4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90 }; int post[] = { 4, 12, 10, 18, 24, 22, 15, 31, 44, 35, 66, 90, 70, 50, 25 }; Main tree = new Main(); System.out.println("Preorder Traversal of the tree is: "); tree.printPreOrderTraversal(in, post); } }आउटपुट
Preorder Traversal of the tree is: 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90
