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数组即为输入二叉树的后序遍历序列。

按先序序列构造一棵二叉链表表示的二叉树T； (2)对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列； (3)求二叉树的深度/结点数目/叶结点数目； (4)将二叉树每个结点的左右子树交换位置。

要根据先序遍历序列构造二叉树，首先需要了解先序遍历的顺序是根节点 -> 左子树 -> 右子树。我们可以使用递归的方式来构建二叉树。

1. **构造二叉链表表示的二叉树（先序遍历）**：
- 先创建一个空的链表头节点 `null`。
- 遍历给定的先序遍历序列：
- 如果序列为空或当前元素为 `null`，返回 `null`。
- 否则，找到第一个未被访问的元素并将其设置为新节点，然后将其父节点设置为当前节点。
- 将当前节点的左子节点设为剩余先序遍历中的元素构成的子树（调用相同过程）。
- 将当前节点的右子节点设为剩余先序遍历中的元素构成的子树（可能为空）。

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public TreeNode buildTree(String[] preorder) {
    if (preorder.length == 0) return null;

    TreeNode root = new TreeNode(preorder[0]);
    int index = 1;

    for (TreeNode node : inorderTraversal(root)) {
        if (index < preorder.length && !node.val.equals(preorder[index])) {
            throw new IllegalArgumentException("Invalid preorder sequence");
        }

        node.left = index < preorder.length ? buildTree(Arrays.copyOfRange(preorder, index + 1, preorder.indexOf(node.val) + 1)) : null;
        node.right = index + 1 < preorder.length ? buildTree(Arrays.copyOfRange(preorder, preorder.indexOf(node.val) + 2, preorder.length)) : null;
        index++;
    }

    return root;
}

其中 `inorderTraversal` 是中序遍历的辅助方法，用于生成中序遍历序列供后续操作使用。

2. **遍历二叉树**：
- 先序遍历：已实现上述 `buildTree` 方法，可以用 `preorder` 输出结果。
- 中序遍历：递归方式，从根开始，左 -> 根 -> 右。
- 后序遍历：递归方式，左 -> 右 -> 根。
- 层次遍历：广度优先搜索(BFS)，使用队列实现。

3. **计算二叉树信息**：
- 深度：使用递归或迭代的方式，从根节点开始，记录每一层的最大深度。
- 结点数目：直接遍历整个二叉树统计。
- 叶结点数目：同样遍历，遇到叶子节点计数加一。

4. **交换子树位置**：
- 使用递归，对于每一个节点，交换其左右子节点。

public void swapSubtrees(TreeNode node) {
    if (node != null) {
        TreeNode tempLeft = node.left, tempRight = node.right;
        node.left = swapSubtrees(tempRight);
        node.right = swapSubtrees(tempLeft);
    }
    return node;
}

完成以上步骤后，你可以根据需要执行相应的遍历和计算操作，然后打印出所需的序列。如果你还没有中序遍历序列，可以根据构建的先序遍历重新生成。如果你需要具体的代码片段或者有更多的疑问，请告诉我。