二叉搜索树的漂亮打印：使用盒绘字符与垂直连线实现结构化输出

梦婷姑娘_5869

发布时间：2026-03-30 12:22:03

846人浏览过

来源于php中文网

原创

二叉搜索树的漂亮打印：使用盒绘字符与垂直连线实现结构化输出

本文详解如何为二叉搜索树（BST）实现专业级 prettyPrint() 方法，利用 Unicode 盒绘字符（如 ┌、└、┤、│）构建层次清晰、左右对齐、带垂直连接线的树形字符串表示。

本文详解如何为二叉搜索树（bst）实现专业级 `prettyprint()` 方法，利用 unicode 盒绘字符（如 `┌`、`└`、`┤`、`│`）构建层次清晰、左右对齐、带垂直连接线的树形字符串表示。

在可视化二叉搜索树结构时，仅靠缩进或简单符号（如 - 或 +）难以准确反映父子关系，尤其当树深度增加、分支不对称时，传统递归打印极易丢失垂直连接逻辑——例如左子树最深节点与根之间的 │ 线无法自然延伸。问题核心在于：水平位置需动态跟踪，而垂直支撑线必须跨层级“记忆”并回填。

标准解法是采用双缓冲构建策略：一个 StringBuilder（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 getSize() {
            return Integer.toString(data).length();
        }
    }

    private Node root;

    @Override
    public void add(int i) {
        root = insert(root, i);
    }

    private Node insert(Node node, int value) {
        if (node == null) return new Node(value);
        if (value < node.data) node.left = insert(node.left, value);
        else node.right = insert(node.right, value);
        return node;
    }

    @Override
    public String prettyPrint() {
        return prettyString();
    }

    public String prettyString() {
        StringBuilder treeSB = new StringBuilder();
        // 初始 lineSB 以换行符开头，便于统一处理首行前缀
        prettyString(root, new StringBuilder("\n"), treeSB);
        return treeSB.length() > 0 ? treeSB.substring(1) : "";
    }

    private void prettyString(Node node, StringBuilder lineSB, StringBuilder treeSB) {
        if (node == null) return;

        int dataSize = node.getSize();
        int depth = lineSB.length(); // 当前行状态长度（含 '\n'）
        char lastChar = lineSB.charAt(depth - 1);
        // i: 0→'│' 表示该位置有向下延伸线；1→' ' 表示被截断（即父节点无右子树时此处为空）
        int i = "\n │".indexOf(lastChar);
        // j: 编码子树存在性组合：0=无子树, 1=仅有右, 2=仅有左, 3=左右均有 → 映射到 " ┐┘┤"
        int j = (node.left != null ? 2 : 0) + (node.right != null ? 1 : 0);

        // 向 lineSB 追加当前节点数据宽度 + 1 个空格（为后续符号留位）
        lineSB.append(" ".repeat(dataSize + 1));
        // 递归处理左子树（先序，但构建逻辑为中-左-右）
        prettyString(node.left, lineSB, treeSB);
        // 回溯：恢复 lineSB 到进入本层前的状态（去掉刚加的空格及可能新增的 '\n│'）
        lineSB.setLength(depth - 1);

        // 【关键】将当前路径状态（不含末尾换行）写入最终结果
        treeSB.append(lineSB);
        // 添加连接符 + 数据 + 结束符
        treeSB.append("\n┌└".charAt(i)); // 根据父路径决定是┌（左支）还是└（右支）
        treeSB.append(node.data);
        treeSB.append(" ┐┘┤".charAt(j)); // 根据子树存在性选择符号

        // 更新 lineSB：为右子树准备新一行的前缀
        // 若原位置是 '│'，则延续为 '│'；若是 ' '，则保持空格；末尾追加对应竖线或空格
        lineSB.append("\n│ ".charAt(i));
        lineSB.append(" ".repeat(dataSize));
        lineSB.append(" │ │".charAt(j)); // j=0→' ', j=1→'│', j=2→'│', j=3→'│'
        // 递归处理右子树
        prettyString(node.right, lineSB, treeSB);
    }
}

✅ 关键设计说明：

无状态依赖：lineSB 作为参数传递，避免实例变量导致的并发/重入问题；
精准对齐：每个节点的水平偏移由其祖先路径上的 │ 数量和各节点数值宽度共同决定，天然支持不同位数整数（如 1 vs 1000）；
符号语义明确：
- ┌ / └：表示当前节点是父节点的左/右子节点；
- ┐ / ┘ / ┤：分别表示“仅有右子”、“仅有左子”、“左右均有”；
- │：垂直连接线，在 lineSB 中逐层累积，确保跨深度对齐。