Preorder จาก Inorder และ Postorder Traversals ใน C++

ในปัญหานี้ เราได้รับ inorder และ postorder traversal ของต้นไม้ไบนารี งานของเราคือพิมพ์ postorder traversal ของต้นไม้

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา

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 :

ในการแก้ปัญหานี้ วิธีแก้ปัญหาง่ายๆ อาจเป็นการสร้างต้นไม้โดยใช้ traversal ที่กำหนดแล้วหา preorder traversal ของต้นไม้ แต่วิธีนี้จะซับซ้อนมากกว่าสำหรับระบบ

วิธีแก้ปัญหาที่มีประสิทธิภาพมากกว่าสำหรับการแก้ปัญหาคือการใช้โครงสร้างข้อมูล Stack มาดูแต่ละโหนดของต้นไม้ รากของต้นไม้คือรายการสุดท้ายใน postorder traversal ตอนนี้เราต้องแยก left และ right subtree ของต้นไม้ไบนารี เนื่องจากเรารู้โหนดรากของต้นไม้ ใน postorder traversal องค์ประกอบทั้งหมดก่อนโหนดรากเป็นของ left subtree และหลังรากเป็นของ right subtree

แบบนี้ เราจะหาองค์ประกอบทั้งหมดและเก็บโหนดใน stack และพิมพ์องค์ประกอบของ stack ซึ่งให้ preorder traversal

การนำวิธีแก้ปัญหาของเราไปใช้ใน 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