本文详解如何为二叉搜索树（BST）实现符合规范的 prettyPrint() 方法，通过递归构建带垂直连接线（│）和分支符号（┌/└/┤/┐/┘）的 ASCII/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 自然承载结构拓扑信息——这是解决“竖线跨越”问题的优雅范式，也是理解高级树形打印算法的关键跃迁。
