二叉树的构建和遍历操作 实验目的：掌握二叉树的构建及遍历操作。 实验内容：按先序遍历的顺序构建一棵基于二叉链表存储结构的二叉树（如图所示），并对构建的二叉树实现先序、中序和后序遍历，并输出对应的遍历序列。 实验要求： 1、构建一个二叉链表存储结构的二叉树。 2、基于上述构建的二叉树进行先序、中序和后序遍历操作。用Java实现

以下是Java实现的代码：

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;

    TreeNode(char x) {
        val = x;
        left = null;
        right = null;
    }
}

public class BinaryTree {
    public static void main(String[] args) {
        // 先序遍历序列
        String preOrder = "ABDECFG";
        // 中序遍历序列
        String inOrder = "DBEAFCG";

        // 构建二叉树
        TreeNode root = buildTree(preOrder, inOrder);

        // 先序遍历
        System.out.print("先序遍历：");
        preOrderTraversal(root);
        System.out.println();

        // 中序遍历
        System.out.print("中序遍历：");
        inOrderTraversal(root);
        System.out.println();

        // 后序遍历
        System.out.print("后序遍历：");
        postOrderTraversal(root);
        System.out.println();
    }

    // 构建二叉树
    public static TreeNode buildTree(String preOrder, String inOrder) {
        if (preOrder.length() == 0 || inOrder.length() == 0) {
            return null;
        }

        TreeNode root = new TreeNode(preOrder.charAt(0));

        int index = inOrder.indexOf(root.val);

        root.left = buildTree(preOrder.substring(1, index + 1), inOrder.substring(0, index));
        root.right = buildTree(preOrder.substring(index + 1), inOrder.substring(index + 1));

        return root;
    }

    // 先序遍历
    public static void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.print(root.val);
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

    // 中序遍历
    public static void inOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        inOrderTraversal(root.left);
        System.out.print(root.val);
        inOrderTraversal(root.right);
    }

    // 后序遍历
    public static void postOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val);
    }
}

输出结果为：

先序遍历：ABDECFG
中序遍历：DBEAFCG
后序遍历：DEBFGCA