JAVA先序和中序建立二叉树_通过树的中序和先序遍历生成二叉树

好的，让我来回答你的问题。对于给定的一棵二叉树，我们可以通过它的先序遍历和中序遍历来构建它。具体的步骤如下：

1. 首先，我们需要将这棵二叉树的先序遍历和中序遍历存储到两个数组中。

2. 然后，我们从先序遍历的第一个节点开始，将其作为根节点，并在中序遍历中找到对应的位置。根据中序遍历的性质，根节点将中序遍历分成了左子树和右子树两部分。

3. 接下来，我们可以递归地构建左子树和右子树。具体地，对于左子树，我们在先序遍历中找到根节点后面的第一个节点作为左子树的根节点，在中序遍历中找到根节点的位置前面的节点都属于左子树；对于右子树，我们在先序遍历中找到左子树的最后一个节点后面的第一个节点作为右子树的根节点，在中序遍历中找到根节点的位置后面的节点都属于右子树。

4. 最后，我们将左子树和右子树分别作为根节点的左子树和右子树。

通过这样的过程，我们就可以通过先序和中序遍历构建一棵二叉树。需要注意的是，如果先序遍历和中序遍历中有重复的节点，那么这些节点在构建二叉树时只能被算作一次。

相关问题

用JAVA编写如下，输入一颗根为r和子树为T1和T2的二叉树的先序遍历序列和中序遍历序列，试着找出它的后序遍历序列。输入格式：输入包含几个测试用例，每个测试用例的第一行包含一个整数n（1≤n≤1000），即二叉树的结点数，后面跟着两行，分别表示先序遍历序列和中序遍历序列，可以假设他们唯一构造一个二叉树。 输出格式：对于每个测试用例，打印一行指定相应是后序遍历序列。

以下是使用JAVA实现输入一颗二叉树的先序遍历序列和中序遍历序列，输出后序遍历序列的代码：

import java.util.Scanner;

public class Main {
    static int n;
    static int[] preorder, inorder, postorder;
    static int index = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            n = scanner.nextInt();
            preorder = new int[n];
            inorder = new int[n];
            postorder = new int[n];
            for (int i = 0; i < n; i++) {
                preorder[i] = scanner.nextInt();
            }
            for (int i = 0; i < n; i++) {
                inorder[i] = scanner.nextInt();
            }
            index = n - 1;
            buildTree(0, n - 1, 0, n - 1);
            for (int i = 0; i < n; i++) {
                System.out.print(postorder[i] + " ");
            }
            System.out.println();
        }
    }

    private static void buildTree(int preL, int preR, int inL, int inR) {
        if (preL > preR || inL > inR) {
            return;
        }
        int root = preorder[preL];
        int k = 0;
        for (int i = inL; i <= inR; i++) {
            if (inorder[i] == root) {
                k = i;
                break;
            }
        }
        postorder[index--] = root;
        buildTree(preL + 1, preL + k - inL, inL, k - 1);
        buildTree(preL + k - inL + 1, preR, k + 1, inR);
    }
}

其中，buildTree方法使用递归实现了二叉树的构建，并且在构建过程中实现了后序遍历序列的生成。在构建过程中，我们首先找到preorder[preL]在inorder数组中的位置k，然后将其插入到postorder数组的倒数第index个位置，同时将index减1，最后递归构建左子树和右子树。最终得到的postorder数组即为输入二叉树的后序遍历序列。