सी ++ में इनऑर्डर और पोस्टऑर्डर ट्रैवर्सल से प्रीऑर्डर करें

इस समस्या में, हमें एक बाइनरी ट्री का इनऑर्डर और पोस्टऑर्डर ट्रैवर्सल दिया जाता है। हमारा काम पेड़ के पोस्टऑर्डर ट्रैवर्सल को प्रिंट करना है।

आइए समस्या को समझने के लिए एक उदाहरण लेते हैं

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