打印二叉树

发表于 更新于 分类于 阅读次数： 本文字数： 304 阅读时长 ≈ 1 分钟

这篇文章介绍了如何打印一棵二叉树，首先通过前序遍历序列和中序遍历序列来构建一颗二叉树，然后通过两种不同的方式来打印这棵二叉树。第一种方式是 Linux 风格，通过递归的方式来打印每个节点，并且使用特殊的符号来表示节点之间的关系，最终得到一棵类似于 Linux 目录树的形式。第二种方式是水平风格，通过递归的方式来打印每个节点，并且使用特殊的符号来表示节点之间的关系，最终得到一棵类似于水平的树形结构。这两种方式都可以很好地打印一棵二叉树，具体使用哪种方式取决于实际需求。

打印二叉树

本文将使用两种展示方式打印一颗二叉树，效果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
8
├── 12
│   ├── 14
│   │   ├── 20
│   │   │   └── 15
│   │   └── 13
│   └── 10
│       ├── 11
│       └── 9
└── 4
    ├── 6
    │   ├── 7
    │   └── 5
    └── 2
        ├── 3
        └── 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
                 /----- 20
                 |       \----- 15
         /----- 14
         |       \----- 13
 /----- 12
 |       |       /----- 11
 |       \----- 10
 |               \----- 9
8
 |               /----- 7
 |       /----- 6
 |       |       \----- 5
 \----- 4
         |       /----- 3
         \----- 2
                 \----- 1

构建二叉树

为了方便测试，我们需要构建一颗二叉树，这里使用前序遍历序列和中序遍历序列来重建二叉树。

1
2
3
4
5
6
7
8
9
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * @File    :   Tree.java
 * @Time    :   2020/03/23 17:46:15
 * @Author  :   wylu
 * @Version :   1.0
 * @Contact :   15wylu@gmail.com
 * @License :   (C)Copyright 2020, wylu-CHINA-SHENZHEN
 * @Desc    :
 */
public class Tree {
    private static TreeNode mk(int[] pre, int[] in,
                               int startPre, int endPre,
                               int startIn, int endIn) {
        if (startPre == endPre) {
            return null;
        }
        TreeNode root = new TreeNode(pre[startPre]);
        // 中序遍历序列根结点索引
        int idx = startIn;
        while (idx < endIn && in[idx] != root.val) {
            idx++;
        }

        // 左子树序列长度
        int llen = idx - startIn;
        // 左右子树序列中点（右子树序列起始点）
        int mpre = startPre + 1 + llen;
        root.left = mk(pre, in, startPre + 1, mpre, startIn, idx - 1);
        root.right = mk(pre, in, mpre, endPre, idx + 1, endIn);
        return root;
    }

    /**
     * 利用前序遍历序列和中序遍历序列构建一颗二叉树
     *
     * @param pre 前序遍历序列
     * @param in  中序遍历序列
     * @return
     */
    public static TreeNode mkTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length == 0 || pre.length != in.length) {
            return null;
        }
        return mk(pre, in, 0, pre.length, 0, in.length);
    }
}

调用示例：

1
2
3
4
5
6
public static void main(String[] args) {
    // Case 1
    int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
    int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
    TreeNode root = Tree.mkTree(pre, in);
}

二叉树打印类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/**
 * @File : TreePrinter.java
 * @Time : 2020/03/23 17:47:57
 * @Author : wylu
 * @Version : 1.0
 * @Contact : 15wylu@gmail.com
 * @License : (C)Copyright 2020, wylu-CHINA-SHENZHEN
 * @Desc :
 */
public class TreePrinter {
    private static void linuxStyle(TreeNode root, StringBuilder sb, String prefix, String childPrefix) {
        if (root == null) {
            return;
        }
        sb.append(prefix);
        sb.append(root.val);
        sb.append("\n");
        linuxStyle(root.right, sb, childPrefix + "├── ", childPrefix + "│   ");
        linuxStyle(root.left, sb, childPrefix + "└── ", childPrefix + "    ");
    }

    public static StringBuilder getLinuxStyle(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        linuxStyle(root, sb, "", "");
        return sb;
    }

    /**
     * z
     * ├── c
     * │ ├── a
     * │ └── b
     * └── d
     *
     * @param root
     */
    public static void prtLinuxStyle(TreeNode root) {
        System.out.println(getLinuxStyle(root).toString());
    }

    public static StringBuilder horizontalStyle(TreeNode root, StringBuilder sb) {
        if (root.right != null) {
            horizontalStyle(root.right, sb, true, "");
        }
        sb.append(root.val).append("\n");
        if (root.left != null) {
            horizontalStyle(root.left, sb, false, "");
        }
        return sb;
    }

    private static void horizontalStyle(TreeNode root, StringBuilder sb, boolean isRight,
            String indent) {
        if (root.right != null) {
            horizontalStyle(root.right, sb, true, indent + (isRight ? "        " : " |      "));
        }
        sb.append(indent);
        sb.append(isRight ? " /" : " \\");
        sb.append("----- ");
        sb.append(root.val).append("\n");
        if (root.left != null) {
            horizontalStyle(root.left, sb, false, indent + (isRight ? " |      " : "        "));
        }
    }

    /**
     *                 /----- 20
     *                 |       \----- 15
     *         /----- 14
     *         |       \----- 13
     * /----- 12
     * |       |       /----- 11
     * |       \----- 10
     * |               \----- 9
     * 8
     * |              /----- 7
     * |      /----- 6
     * |      |       \----- 5
     * \----- 4
     *        |       /----- 3
     *        \----- 2
     *                \----- 1
     *
     * @param root
     */
    public static void prtHorizontalStyle(TreeNode root) {
        System.out.println(horizontalStyle(root, new StringBuilder()).toString());
    }

    public static void main(String[] args) {
        // Case 1
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode root = Tree.mkTree(pre, in);
        TreePrinter.prtLinuxStyle(root);
        TreePrinter.prtHorizontalStyle(root);

        // Case 2
        pre = new int[] {8, 4, 2, 1, 3, 6, 5, 7, 12, 10, 9, 11, 14, 13, 20, 15};
        in = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20};
        root = Tree.mkTree(pre, in);
        TreePrinter.prtLinuxStyle(root);
        TreePrinter.prtHorizontalStyle(root);
    }
}

References

https://stackoverflow.com/questions/4965335/how-to-print-binary-tree-diagram