Duyệt tiền tố từ trung tố và hậu tố trong C++

Trong bài toán này, chúng ta được cho duyệt trung tố và hậu tố của một cây nhị phân. Nhiệm vụ của chúng ta là in duyệt tiền tố của cây.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào:
trung tố: 16 7 21 12 1 5 9
hậu tố: 16 21 7 1 9 5 12
Đầu ra: tiền tố: 12 7 16 21 5 1 9
Giải thích: cây nhị phân là :

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

Một giải pháp hiệu quả hơn để giải quyết bài toán là sử dụng cấu trúc dữ liệu stack. 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 duyệt hậu tố. Bây giờ chúng ta phải tách cây con trái và phải của cây nhị phân. Vì chúng ta biết nút gốc của cây. Trong duyệt hậu tố, tất cả các phần tử trước nút gốc thuộc cây con trái và sau gốc thuộc cây con phải.

Như vậy, chúng ta sẽ tìm tất cả các phần tử và lưu các nút trong stack và in các phần tử của stack cho duyệt tiền tố.

Triển khai giải pháp của chúng ta 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("Duyệt tiền tố của cây là: ");
        tree.printPreOrderTraversal(in, post);
    }
}

Kết quả

Duyệt tiền tố của cây là: 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90