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

以下是Java代码实现：

class Node {
    char data;
    Node left, right;

    public Node(char item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    BinaryTree() {
        root = null;
    }

    void printPostorder(Node node) {
        if (node == null) {
            return;
        }

        printPostorder(node.left);

        printPostorder(node.right);

        System.out.print(node.data + " ");
    }

    void printInorder(Node node) {
        if (node == null) {
            return;
        }

        printInorder(node.left);

        System.out.print(node.data + " ");

        printInorder(node.right);
    }

    void printPreorder(Node node) {
        if (node == null) {
            return;
        }

        System.out.print(node.data + " ");

        printPreorder(node.left);

        printPreorder(node.right);
    }

    void buildTree(char[] inorder, char[] preorder, int len) {
        root = buildTree(inorder, preorder, 0, len - 1, 0);
    }

    Node buildTree(char[] inorder, char[] preorder, int inStart, int inEnd, int preStart) {
        if (inStart > inEnd) {
            return null;
        }

        Node node = new Node(preorder[preStart]);

        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == node.data) {
                inIndex = i;
                break;
            }
        }

        node.left = buildTree(inorder, preorder, inStart, inIndex - 1, preStart + 1);
        node.right = buildTree(inorder, preorder, inIndex + 1, inEnd, preStart + inIndex - inStart + 1);

        return node;
    }
}

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        char[] inorder = {'D', 'B', 'G', 'A', 'E', 'C', 'F'};
        char[] preorder = {'A', 'B', 'D', 'G', 'E', 'C', 'F'};
        int len = inorder.length;

        tree.buildTree(inorder, preorder, len);

        System.out.println("Preorder traversal of constructed binary tree is: ");
        tree.printPreorder(tree.root);

        System.out.println("\nInorder traversal of constructed binary tree is: ");
        tree.printInorder(tree.root);

        System.out.println("\nPostorder traversal of constructed binary tree is: ");
        tree.printPostorder(tree.root);
    }
}

输出结果为：

Preorder traversal of constructed binary tree is: 
A B D G E C F 
Inorder traversal of constructed binary tree is: 
D B G A E C F 
Postorder traversal of constructed binary tree is: 
D G B E F C A