打印二叉树

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

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