树的遍历(已知前序遍历中序遍历求后序遍历,或者已知后序中序求先序)

时间:2021-04-29 12:39:04

假设是1000个结点以内,

输入前序  4 1 3 2 6 5 7

       中序  1 2 3 4 5 6 7 

得到后续  2 3 1 5 7 6 4

关于已知中序后序遍历求先序遍历的代码可以看我的另一篇博客点击打开链接

import java.io.BufferedInputStream;
import java.util.Scanner;

class Node {
    int data;
    Node left, right;
}

public class Main {
    public static int[] pre = new int[1001];
    public static int[] in = new int[1001];

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt();
        for (int i = 0; i < n; ++i) {
            pre[i] = cin.nextInt();
        }
        for (int i = 0; i < n; ++i) {
            in[i] = cin.nextInt();
        }
        cin.close();
        Node head = createTree(pre, 0, in, 0, n);
        postTraverse(head);
    }

    public static void postTraverse(Node node) {
        if (node == null)
            return;
        postTraverse(node.left);
        postTraverse(node.right);
        System.out.print(node.data + " ");
    }
    // 已知先序中序,建树
    public static Node createTree(int[] pre, int lo, int[] in, int ini, int n) {
        if (n <= 0) {
            return null;
        }
        Node node = new Node();
        node.data = pre[lo];
        int i;
        for (i = 0; i < n; ++i) {
            if (pre[lo] == in[ini + i])
                break;
        }
        node.left = createTree(pre, lo + 1, in, ini, i);
        node.right = createTree(pre, lo + i + 1, in, ini + i + 1, n - i - 1);// 最后一个参数是相对于起点的相对下标位置,也是子树个数
        return node;
    }
}
=============================我是一个反应迟钝的程序员==========================