本文详解如何为二叉搜索树（BST）实现专业级 prettyPrint() 方法，利用 Unicode 箱线字符（如 ┌、└、┤、│）构建清晰、对齐、可读性强的垂直树形结构，并解决常见水平缩进错位与竖线连接断裂问题。
本文详解如何为二叉搜索树（bst）实现专业级 `prettyprint()` 方法，利用 unicode 箱线字符（如 `┌`、`└`、`┤`、`│`）构建清晰、对齐、可读性强的垂直树形结构，并解决常见水平缩进错位与竖线连接断裂问题。
在实现二叉树的美观打印（Pretty Print）时，核心挑战并非遍历本身，而在于同步维护横向缩进与纵向连接关系：既要按中序逻辑（左–根–右）组织节点顺序，又要用 │ 字符在多行间“延续”父节点的垂直路径，使树形结构在视觉上连贯可读。原始实现中直接拼接空格与符号的方式无法回溯已生成的上层行内容，导致 │ 无法精准对齐到祖先节点下方——这正是竖线缺失与缩进混乱的根本原因。
正确解法的关键在于采用双缓冲构建策略：
- 使用一个 treeSB（主缓冲区）累积最终每一行的完整字符串；
- 同时用一个 lineSB（行状态缓冲区） 动态记录当前递归深度下，“该行在对应列位置应显示什么字符”（例如 │、空格或换行符），它本质上是一条“虚拟垂直导轨”，随递归深入而增长、回退，确保每个子树分支都能在正确列插入连接符。
以下是符合 PrintableTree 接口的专业实现（已优化可读性与鲁棒性）：
public class PrettyPrintableTree implements PrintableTree {
private static class Node {
final int data;
Node left, right;
Node(int data) {
this.data = data;
}
int width() { // 节点数值字符串宽度（支持多位数）
return Integer.toString(data).length();
}
}
private Node root;
@Override
public void add(int i) {
root = insert(root, i);
}
private Node insert(Node node, int val) {
if (node == null) return new Node(val);
if (val < node.data) node.left = insert(node.left, val);
else node.right = insert(node.right, val);
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); // 去除开头多余的换行
}
private void prettyString(Node node, StringBuilder lineSB, StringBuilder treeSB) {
if (node == null) return;
final int nodeWidth = node.width();
final int depth = lineSB.length(); // 当前行状态长度（即当前“导轨”高度）
// 步骤1：向 lineSB 追加占位（为左子树预留空间：数值宽度 + 1 个分隔空格）
lineSB.append(" ".repeat(nodeWidth + 1));
// 递归处理左子树 → 此时 lineSB 已包含左子树所需的竖线/空格路径
prettyString(node.left, lineSB, treeSB);
// 回退至当前节点层级：截断 lineSB 到进入左子树前的状态（即移除左子树添加的所有内容）
lineSB.setLength(depth - 1);
// 步骤2：将当前行状态（含祖先竖线）写入主结果
treeSB.append(lineSB).append('\n');
// 添加节点符号：根据 lineSB 末尾字符决定是 "┌"（来自左支）还是 "└"（来自右支）
char prefix = lineSB.charAt(depth - 1) == '│' ? '└' : '┌';
treeSB.append(prefix).append(node.data);
// 根据子树存在情况选择后缀符号：
// 0: 无子树 → "┘"（左叶子）或 "┐"（右叶子）→ 实际由 prefix 隐含方向，此处统一用 "┤" 更合理？
// 但参考答案逻辑：0=┘, 1=┐, 2=┤ → 对应 (left?2:0)+(right?1:0)
int suffixIndex = (node.left != null ? 2 : 0) + (node.right != null ? 1 : 0);
treeSB.append(" ┐┘┤".charAt(suffixIndex));
// 步骤3：为右子树更新 lineSB 状态：
// - 若当前是左支（lineSB 末为 '│'），则右子树导轨继续用 '│'
// - 若当前是根或右支（末为 '\n'），则右子树导轨起始为 ' '
char verticalChar = lineSB.charAt(depth - 1) == '│' ? '│' : ' ';
lineSB.append(verticalChar)
.append(" ".repeat(nodeWidth)) // 数值占位
.append(" │ │".charAt(suffixIndex)); // 右子树连接符（┐/┘/┤）
prettyString(node.right, lineSB, treeSB);
}
}✅ 关键设计亮点说明：
- 无状态副作用：lineSB 作为递归参数传递，避免 StringBuilder 实例变量引发的并发或重入风险；
- 动态导轨机制：lineSB 不存储整行，而是逐层构建“从根到当前节点路径的列标记”，天然支持任意深度的 │ 对齐；
- 符号语义明确：┌/└ 表示分支方向，┐/┘ 表示单子树终结，┤ 表示双子树分叉，│ 维持纵向连接；
- 宽度自适应：node.width() 确保两位数（如 100）与三位数（如 2000）均能正确对齐，不依赖固定缩进。
⚠️ 注意事项：
- 此算法默认输出符合中序遍历顺序（左–根–右），严格满足题目“从小到大”的结构展示要求；
- 输出依赖 Unicode 字体支持（现代 IDE 和终端均兼容 ┌ └ ┤ │ 等字符），若环境受限，可降级为 ASCII 替代（如 +, |, -），但美观度下降；
- 时间复杂度为 O(n × h)（h 为树高），因每行生成需遍历路径；空间复杂度 O(h)（递归栈 + lineSB 长度）。
通过这种“状态驱动式字符串构建”，我们超越了简单空格计数的思维定式，让树的拓扑关系真正映射为可视化的字符布局——这才是专业级 Pretty Print 的实现精髓。
