Java代码实现构造一颗三叉链表表示的二叉树，实现采用先根、中根、后根、层次算法遍历二叉树，输出二叉树字符

以下是Java代码实现构造一颗三叉链表表示的二叉树，以及四种遍历方式的实现：

public class TriLinkedBinaryTree {
    private TriLinkedBinaryTreeNode root;  // 二叉树的根节点

    // 三叉链表表示的二叉树节点类
    private class TriLinkedBinaryTreeNode {
        private char data;  // 节点数据
        private TriLinkedBinaryTreeNode parent;  // 父节点指针
        private TriLinkedBinaryTreeNode leftChild;  // 左孩子节点指针
        private TriLinkedBinaryTreeNode rightChild;  // 右孩子节点指针

        public TriLinkedBinaryTreeNode(char data) {
            this.data = data;
        }
    }

    // 构造函数，通过先序遍历序列和中序遍历序列构造二叉树
    public TriLinkedBinaryTree(String preorder, String inorder) {
        int length = preorder.length();
        if (length == 0) {
            root = null;
            return;
        }
        root = new TriLinkedBinaryTreeNode(preorder.charAt(0));  // 先序遍历的第一个节点为根节点
        int rootIndex = inorder.indexOf(root.data);  // 在中序遍历序列中找到根节点的位置
        String leftInorder = inorder.substring(0, rootIndex);  // 左子树的中序遍历序列
        String rightInorder = inorder.substring(rootIndex + 1);  // 右子树的中序遍历序列
        String leftPreorder = preorder.substring(1, 1 + leftInorder.length());  // 左子树的先序遍历序列
        String rightPreorder = preorder.substring(1 + leftInorder.length());  // 右子树的先序遍历序列
        root.leftChild = build(leftPreorder, leftInorder, root);
        root.rightChild = build(rightPreorder, rightInorder, root);
    }

    // 递归函数，根据先序遍历序列和中序遍历序列构造一颗二叉树
    private TriLinkedBinaryTreeNode build(String preorder, String inorder, TriLinkedBinaryTreeNode parent) {
        int length = preorder.length();
        if (length == 0) {
            return null;
        }
        TriLinkedBinaryTreeNode node = new TriLinkedBinaryTreeNode(preorder.charAt(0));
        node.parent = parent;
        int rootIndex = inorder.indexOf(node.data);  // 在中序遍历序列中找到当前节点的位置
        String leftInorder = inorder.substring(0, rootIndex);  // 左子树的中序遍历序列
        String rightInorder = inorder.substring(rootIndex + 1);  // 右子树的中序遍历序列
        String leftPreorder = preorder.substring(1, 1 + leftInorder.length());  // 左子树的先序遍历序列
        String rightPreorder = preorder.substring(1 + leftInorder.length());  // 右子树的先序遍历序列
        node.leftChild = build(leftPreorder, leftInorder, node);
        node.rightChild = build(rightPreorder, rightInorder, node);
        return node;
    }

    // 先序遍历
    public void preorderTraversal() {
        System.out.print("先序遍历结果：");
        preorderTraversal(root);
        System.out.println();
    }

    // 递归函数，先序遍历以node为根节点的子树
    private void preorderTraversal(TriLinkedBinaryTreeNode node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preorderTraversal(node.leftChild);
            preorderTraversal(node.rightChild);
        }
    }

    // 中序遍历
    public void inorderTraversal() {
        System.out.print("中序遍历结果：");
        inorderTraversal(root);
        System.out.println();
    }

    // 递归函数，中序遍历以node为根节点的子树
    private void inorderTraversal(TriLinkedBinaryTreeNode node) {
        if (node != null) {
            inorderTraversal(node.leftChild);
            System.out.print(node.data + " ");
            inorderTraversal(node.rightChild);
        }
    }

    // 后序遍历
    public void postorderTraversal() {
        System.out.print("后序遍历结果：");
        postorderTraversal(root);
        System.out.println();
    }

    // 递归函数，后序遍历以node为根节点的子树
    private void postorderTraversal(TriLinkedBinaryTreeNode node) {
        if (node != null) {
            postorderTraversal(node.leftChild);
            postorderTraversal(node.rightChild);
            System.out.print(node.data + " ");
        }
    }

    // 层次遍历
    public void levelTraversal() {
        System.out.print("层次遍历结果：");
        Queue<TriLinkedBinaryTreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            TriLinkedBinaryTreeNode node = queue.poll();
            System.out.print(node.data + " ");
            if (node.leftChild != null) {
                queue.offer(node.leftChild);
            }
            if (node.rightChild != null) {
                queue.offer(node.rightChild);
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        String preorder = "ABDCEFG";
        String inorder = "DBAECFG";
        TriLinkedBinaryTree tree = new TriLinkedBinaryTree(preorder, inorder);
        tree.preorderTraversal();
        tree.inorderTraversal();
        tree.postorderTraversal();
        tree.levelTraversal();
    }
}

输出结果为：

先序遍历结果：A B D C E F G 
中序遍历结果：D B A E C F G 
后序遍历结果：D B E G F C A 
层次遍历结果：A B C D E F G