在控制台输出二叉树的结构
在控制台输出二叉树的结构
因为网上没有找到很好的输出二叉树结构的工具类，于是自己写了一个，思路很简单，实现也很简单。效果还不错。
树结构的代码天然适合递归的写法。
节点适配器
因为二叉树的类型很多，有红黑树，AVL 数，有的树的节点的值类型是 int，有的是一个对象，为了同意适配，就创建了一个适配器，需要用此工具输出结构的树只需要让其节点实现此接口即可
/**
* @author xiashuo.xyz
* @date 2025-05-16 07:46
*/
public interface BTPrinterAdapter<N> {
String getNodeString();
N getLeftNode();
N getRightNode();
}
结构输出工具
package tree.avl;
import java.util.ArrayList;
import java.util.List;
/**
* @author xiashuo.xyz
* @date 2025-05-15 21:19
*/
public class BTPrinter<K extends BTPrinterAdapter<K>> {
/**
* 用递归的方式，从下往上画整个树，简单易懂
*
* @param root
* @return
*/
public static <K extends BTPrinterAdapter<K>> NodePrinter getNodePrinter(K root) {
if (root == null) {
return new NodePrinter(new ArrayList<>(), 0, 0, 0);
}
NodePrinter leftPrinter = getNodePrinter(root.getLeftNode());
NodePrinter rightPrinter = getNodePrinter(root.getRightNode());
// 开始设置这一层的 lines width rootStartIndex rootEndIndex
String valString = root.getNodeString();
int valueWidth = valString.length();
// 用来画 _ 和 |
int padding_left = 0;
int padding_right = 0;
if (root.getLeftNode() != null) {
padding_left = 2;
}
if (root.getRightNode() != null) {
padding_right = 2;
}
// 任何一个节点树的宽度都由以下几部分组成
// 左子树的宽度 + （如果左子树存在，则需要流出空间来画线） + 根节点的宽度 + （如果右子树存在，则需要流出空间来画线） + 右子树的宽度
int width = leftPrinter.width + padding_left + valueWidth + padding_right + rightPrinter.width;
// 根节点的值的字符起始的位置
int rootStartIndex = leftPrinter.width + padding_left;
// 根节点的值的字符中止的位置
int rootEndIndex = rootStartIndex + valueWidth - 1;
// 右子树的起始位置
int rightStartIndex = rootStartIndex + valueWidth + padding_right;
List<String> lines = new ArrayList<String>();
String firstLine = setString(repeat(" ", width), rootStartIndex, valString);
lines.add(firstLine);
if (root.getLeftNode() != null || root.getRightNode() != null) {
String secondLine = repeat(" ", width);
if (root.getLeftNode() != null) {
// 从左子树的根节点的值的右侧开始画线，一直到当前根节点的值的起始位置 先画 _ 最后画 |
secondLine = setChar(secondLine, leftPrinter.rootEndIndex + 1, rootStartIndex - 1, '_');
secondLine = setChar(secondLine, rootStartIndex - 1, rootStartIndex, '|');
}
if (root.getRightNode() != null) {
// 从当前根节点的值的终点位置的下一个位置开始画线，一直到右子树的根节点的值的左侧 先画 | 最后画 _
secondLine = setChar(secondLine, rootEndIndex + 1, rootEndIndex + 2, '|');
secondLine = setChar(secondLine, rootEndIndex + 2, rightStartIndex + rightPrinter.rootStartIndex, '_');
}
lines.add(secondLine);
}
int maxLines = Integer.max(leftPrinter.lines.size(), rightPrinter.lines.size());
for (int i = 0; i < maxLines; i++) {
String line = repeat(" ", width);
if (i <= leftPrinter.lines.size() - 1) {
String leftLine = leftPrinter.lines.get(i);
// 左子树从 0 开始
line = setString(line, 0, leftLine);
}
if (i <= rightPrinter.lines.size() - 1) {
String rightLine = rightPrinter.lines.get(i);
// 右子树从 rightStartIndex 开始
line = setString(line, rightStartIndex, rightLine);
}
lines.add(line);
}
return new NodePrinter(lines, width, rootStartIndex, rootEndIndex);
}
public static String setString(String source, int fromIndex, String replacement) {
StringBuilder stringBuilder = new StringBuilder(source);
String result = stringBuilder.replace(fromIndex, fromIndex + replacement.length(), replacement).toString();
return result;
}
public static String setChar(String source, int fromIndex, int toIndex, char c) {
StringBuilder stringBuilder = new StringBuilder(source);
String result = stringBuilder.replace(fromIndex, toIndex, repeat(new String(new char[]{c}), toIndex - fromIndex)).toString();
return result;
}
public static String repeat(String segment, int times) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < times; i++) {
sb.append(segment);
}
return sb.toString();
}
public static <K extends BTPrinterAdapter<K>> void printTree(K root) {
NodePrinter nodePrinter = getNodePrinter(root);
System.out.println(repeat("-", nodePrinter.width));
for (String line : nodePrinter.lines) {
System.out.println(line);
}
}
static class NodePrinter {
// 这个节点总共多少行
List<String> lines;
// 总共宽多少个字符
int width;
// 顶点值起始索引
int rootStartIndex;
// 顶点值终点索引
int rootEndIndex;
public NodePrinter(List<String> lines, int width, int rootStartIndex, int rootEndIndex) {
this.lines = lines;
this.width = width;
this.rootStartIndex = rootStartIndex;
this.rootEndIndex = rootEndIndex;
}
}
}
思路很简单，首先是需要理解一个最小单元，就是在控制台输出一个子树需要哪些基本的信息，其实只需要一个 List<String> 即可，然后把渲染完子树，再渲染子树所处的父节点的时候，只需要把子树的内容 List<String> 复制一下即可。但是我们为了美观，还需要画子节点跟父节点之间的连接线，为了美观，这些连接线最好处于子节点的值跟父节点的值中间，因此，我们需要把子节点的内容中顶级节点的位置信息告诉父节点，于是返回三个内容即可，一个是子节点树的总的宽度，以及根节点的的值字符串的起点索引跟根节点索引，这样当我们渲染父节点树的时候，我们就能很清楚地知道，链接线从哪里开始画，画到哪为之。于是我们就确定了最小子树的渲染输出对象的内容 NodePrinter
然后输出的步骤就变成了
- 先根据左子树的宽度右子树的宽度，还有当前根节点的值的跨度，再加上用来画
|和_的宽度，确定当前子树的宽度 - 画第一行，也就是当前根节点所在的行
- 画第二行，画连接线所在的行
- 取左子树和右子树的最大高度，然后将左子树的内容和右子树的内容复制到指定的位置
示例
TreeNode 需要实现 BTPrinterAdapter 接口
/**
* @author xiashuo.xyz
* @date 2025-05-14 22:25
*/
public class TreeNode implements BTPrinterAdapter<TreeNode> {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
this.val = x;
}
@Override
public String getNodeString() {
return Integer.toString(val);
}
@Override
public TreeNode getLeftNode() {
return left;
}
@Override
public TreeNode getRightNode() {
return right;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(100);
root.left = new TreeNode(21);
root.right = new TreeNode(303);
root.right.left = new TreeNode(1245);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(555);
root.left.left.left = new TreeNode(455);
root.left.left.left.left = new TreeNode(855);
BTPrinter.printTree(root);
}
}
输出
------------------------------------
100
______| |_______
21 303
_| |_ _|
4 555 1245
_|
455
_|
855
非常地直观，而且美观