Đặt hàng trước từ trình duyệt Inorder và Postorder trong C ++

Trong bài toán này, chúng ta được cung cấp cho phép duyệt thứ tự không và thứ tự sau của một cây nhị phân. Nhiệm vụ của chúng ta là in đường truyền theo thứ tự của cây.

Hãy lấy một ví dụ để hiểu vấn đề

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 :

Để giải quyết vấn đề này, một giải pháp đơn giản có thể là tạo một cây bằng cách sử dụng các đường truyền đã cho và sau đó tìm đường đi ngang của cây được đặt hàng trước. Nhưng phương pháp này sẽ phức tạp hơn đối với hệ thống.

Một giải pháp hiệu quả hơn để giải quyết vấn đề là sử dụng cấu trúc dữ liệu ngăn xếp. Hãy xem từng nút của cây. Gốc của cây là mục cuối cùng trong quá trình duyệt theo thứ tự bưu điện. Bây giờ chúng ta phải tách cây con bên trái và bên phải của cây nhị phân. Kể từ khi chúng ta biết nút gốc của cây. Trong trình duyệt thứ tự sau, tất cả các phần tử trước nút gốc là cây con bên trái và sau nút gốc là cây con bên phải.

Như vậy, chúng tôi sẽ tìm tất cả các phần tử và lưu trữ các nút trong ngăn xếp và các phần tử in của ngăn xếp cung cấp cho việc truyền tải đặt hàng trước.

Việc triển khai giải pháp của chúng tôi trong Java

Ví dụ

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);
   }
}

Đầu ra

Preorder Traversal of the tree is:
25 15 10 4 12 22 18 24 50 35 31 44 70 66 90