C++でのインオーダーおよびポストオーダートラバーサルからのプレオーダー

この問題では、二分木のインオーダートラバーサルとポストオーダートラバーサルが与えられます。私たちのタスクは、ツリーのポストオーダートラバーサルを印刷することです。

問題を理解するために例を見てみましょう

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 :

この問題を解決するための簡単な解決策は、指定されたトラバーサルを使用してツリーを作成し、ツリーのプレオーダートラバーサルを見つけることです。ただし、この方法はシステムにとってより複雑になります。

この問題を解決するためのより効果的な解決策は、スタックデータ構造を使用することです。ツリーの各ノードを見てみましょう。ツリーのルートは、ポストオーダートラバーサルの最後のアイテムです。次に、二分木の左右のサブツリーを分離する必要があります。ツリーのルートノードがわかっているので。ポストオーダートラバーサルでは、ルートノードの前のすべての要素は左のサブツリーにあり、ルートの後のすべての要素は右のサブツリーにあります。

このように、すべての要素を見つけて、スタック内のノードと、プレオーダートラバーサルを提供するスタックの印刷要素を格納します。

Javaでのソリューションの実装

例

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