ในปัญหานี้ เราได้รับการส่งผ่านแบบ inorder และ postorder ของไบนารีทรี งานของเราคือการพิมพ์การข้ามผ่านของลำดับหลังของต้นไม้
มาดูตัวอย่างทำความเข้าใจปัญหากัน
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
