二叉搜索树的漂亮打印：使用 Unicode 框线字符实现层次化结构可视化

本文详解如何为二叉搜索树（bst）实现符合规范的 `prettyprint()` 方法，通过递归构建带垂直连接线（`│`）和分支符号（`┌`/`└`/`┤`/`┐`/`┘`）的 ascii/unicode 树形结构，解决水平对齐与跨层竖线继承等核心难点。

在实现二叉树的“漂亮打印”（pretty print）时，关键挑战不在于遍历顺序（中序遍历保证值从小到大输出），而在于结构可视化：如何用 Unicode 框线字符（如 ┌、└、┤、│）准确表达父子关系、左右子树位置，并确保垂直连接线能跨越多层节点——这正是原始实现失败的核心原因。简单地按深度缩进或硬编码空格无法维持竖线的连续性；必须动态维护每行“左侧状态”，即哪些列应持续绘制 │。

核心思路：双 StringBuilder 协同建模

解决方案采用状态驱动的递归构建策略，引入两个 StringBuilder 协作：

treeSB：最终输出的完整字符串，逐行追加；lineSB：当前行左侧“连接状态”的快照，记录从根到当前节点路径上每一层级应显示的字符（如空格、│ 或换行符 \n）。其长度即为当前递归深度，内容隐式编码了“该位置是否需要向下延伸竖线”。

该设计巧妙将“跨层竖线”问题转化为字符串状态传递：每次进入子树前扩展 lineSB，返回时回溯（setLength(depth – 1)），确保右子树复用左子树退出后的正确状态。

完整可运行实现

public class PrettyPrintableTree implements PrintableTree { private static class Node { final int data; Node left, right; Node(int data) { this.data = data; } int getSize() { return Integer.toString(data).length(); } } private Node root; @Override public void add(int i) { root = add(root, i); } private Node add(Node node, int value) { if (node == null) return new Node(value); if (value < node.data) { node.left = add(node.left, value); } else { node.right = add(node.right, value); } return node; } @Override public String prettyPrint() { return prettyString(); } public String prettyString() { StringBuilder treeSB = new StringBuilder(); // 初始 lineSB 以 "\n" 开头，便于统一处理首行前缀 prettyString(root, new StringBuilder("\n"), treeSB); return treeSB.substring(1); // 去除开头多余的 ‘\n’ } private void prettyString(Node node, StringBuilder lineSB, StringBuilder treeSB) { if (node == null) return; final int dataSize = node.getSize(); final int depth = lineSB.length(); // 当前递归深度（即 lineSB 长度） // 解析上一层留下的“连接符”：’\n’→0（新行起始），’│’→1（竖线延续） final int i = "\n│".indexOf(lineSB.charAt(depth – 1)); // 计算当前节点连接符类型：0=叶节点（┘/┐），1=仅右子（┐），2=仅左子（┘），3=双子（┤） final int j = (node.left != null ? 2 : 0) + (node.right != null ? 1 : 0); // 为左子树预留空间：追加 "dataSize+1" 个空格（数字占位+分隔） lineSB.append(" ".repeat(dataSize + 1)); prettyString(node.left, lineSB, treeSB); // 递归处理左子树 lineSB.setLength(depth – 1); // 回溯：恢复到进入左子树前的状态 // 【关键】将当前行左侧状态写入 treeSB（不含末尾换行符） treeSB.append(lineSB.subSequence(0, depth – 1)); // 去掉末尾的 ‘\n’ 或 ‘│’ // 添加节点符号：i 控制前缀（┌/└），j 控制后缀（┐/┘/┤） treeSB.append("┌└".charAt(i)) .append(node.data) .append(" ┐┘┤".charAt(j)) .append("\n"); // 更新 lineSB 为右子树准备： // – 在原深度位置插入 ‘│’ 或 ‘ ‘（由 i 决定） // – 后接 dataSize 个空格（对齐数字宽度） // – 最后添加右子树连接符（’│’ 或 ‘ ‘，由 j 决定） lineSB.setCharAt(depth – 1, "\n│".charAt(i)); lineSB.append(" ".repeat(dataSize)); lineSB.append(" ││".charAt(j)); prettyString(node.right, lineSB, treeSB); // 递归处理右子树 }}

关键机制解析

组件作用示例（节点 123，左子 11，右子 200）lineSB 初始值 “\n”标记新行起点，使 i = 0 → 前缀为 ┌┌123┤ 首行无左侧干扰i = “\n│”.indexOf(…)判断父节点如何连接本节点：\n→新分支（┌），│→延续竖线（└）若 123 是 11 的右兄弟，则 i=1 → └123┤j 计算逻辑(left?2:0)+(right?1:0) 编码子树存在性：0→叶（┘/┐），1→仅右（┐），2→仅左（┘），3→双子（┤）123 有左右子 → j=3 → 后缀 ┤lineSB.setLength(depth-1)精确回溯，确保右子树获得与左子树对称的左侧状态左子 11 处理完后，lineSB 恢复至 123 层级，再为 200 构建新状态

注意事项与最佳实践

避免实例变量状态污染：原始代码中 mainSB 作为成员变量，在多次调用 prettyPrint() 时会累积结果。本方案使用局部 StringBuilder，保障线程安全与可重入性。Unicode 兼容性：确保终端/IDE 支持 UTF-8 并启用等宽字体，否则框线字符可能错位。Java 字符串原生支持 Unicode，无需额外编码。空树处理：当前实现对 root == null 返回空字符串，符合多数场景需求；如需显示 “(empty)”，可在 prettyString() 中添加前置判断。性能考量：时间复杂度为 O(nh)（n 为节点数，h 为高度），主要消耗在字符串拼接；对于超大树，可考虑基于字符数组的缓冲区优化，但本实现已平衡可读性与实用性。

通过这种状态传递式递归，我们不再手动计算缩进数值，而是让 lineSB 自然承载结构拓扑信息——这是解决“竖线跨越”问题的优雅范式，也是理解高级树形打印算法的关键跃迁。