Java如何实现带连接线的二叉搜索树美观树形打印？

你当前使用的Trunk递归边遍历边打印的方案存在固有缺陷：遍历过程中无法提前获知下层节点的位置，只能靠固定缩进拼接前缀，必然会出现竖线错位、节点无法层内居中的问题，和目标的居中对齐树形效果不匹配。

核心改进思路 #

放弃边遍历边输出的逻辑，改用分层预计算位置+画布逐行绘制的方案，流程如下：

• 首次遍历树，计算三个核心参数：树的总高度、单个节点值的打印占位宽度、每个节点在最终输出画布上的水平坐标
• 初始化空白字符画布：总行数为2*树高 - 1（每层节点占1行，层与层之间的连接线占1行），总宽度为最底层叶子节点完全铺开的宽度，所有位置初始填充空格
• 从根节点开始逐层放置节点值，再根据父子节点的相对位置绘制连接线：水平段用─，拐角位置用┌/┐，纵向连通位置用│
• 最后逐行拼接画布上的字符，得到最终的树形字符串

可直接复用的实现代码 #

将原有匿名内部类中的打印相关逻辑替换为如下代码即可，输出对齐效果和目标示例一致，同时修正了原实现直接打印到控制台、prettyPrint()返回空字符串不符合接口定义的问题：

// 注意：用到的集合类需从java.util包导入
@Override
public String prettyPrint() {
    if (root == null) return "";
    StringBuilder treeStr = new StringBuilder();
    // 计算树总高度
    int treeHeight = getHeight(root);
    // 单节点打印宽度，可根据节点值长度动态调整
    int nodeWidth = 4;
    // 最底层总宽度
    int totalWidth = (1 << (treeHeight - 1)) * (nodeWidth + 1) - 1;
    // BFS分层记录每个节点的位置
    List<List<NodePosition>> layers = new ArrayList<>();
    Queue<NodePosition> nodeQueue = new LinkedList<>();
    nodeQueue.add(new NodePosition(root, totalWidth / 2, 0));

    while (!nodeQueue.isEmpty()) {
        int layerSize = nodeQueue.size();
        List<NodePosition> curLayer = new ArrayList<>();
        for (int i = 0; i < layerSize; i++) {
            NodePosition np = nodeQueue.poll();
            curLayer.add(np);
            // 计算子节点偏移量
            int childOffset = (1 << (treeHeight - np.level - 2)) * (nodeWidth + 1) / 2;
            if (np.node.left != null) {
                nodeQueue.add(new NodePosition(np.node.left, np.pos - childOffset, np.level + 1));
            }
            if (np.node.right != null) {
                nodeQueue.add(new NodePosition(np.node.right, np.pos + childOffset, np.level + 1));
            }
        }
        layers.add(curLayer);
    }

    // 逐行绘制节点和连接线
    for (int i = 0; i < layers.size(); i++) {
        char[] nodeLine = new char[totalWidth];
        char[] connectLine = new char[totalWidth];
        Arrays.fill(nodeLine, ' ');
        Arrays.fill(connectLine, ' ');
        List<NodePosition> curLayer = layers.get(i);

        for (NodePosition np : curLayer) {
            // 写入节点值
            String valStr = String.valueOf(np.node.data);
            int valStart = np.pos - valStr.length() / 2;
            for (int j = 0; j < valStr.length(); j++) {
                nodeLine[valStart + j] = valStr.charAt(j);
            }
            // 非最后一层绘制连接线
            if (i < layers.size() - 1) {
                int childOffset = (1 << (treeHeight - np.level - 2)) * (nodeWidth + 1) / 2;
                if (np.node.left != null) {
                    connectLine[np.pos - childOffset/2] = '┌';
                    for (int j = np.pos - childOffset/2 + 1; j < np.pos; j++) {
                        connectLine[j] = '─';
                    }
                }
                if (np.node.right != null) {
                    connectLine[np.pos + childOffset/2] = '┐';
                    for (int j = np.pos + 1; j < np.pos + childOffset/2; j++) {
                        connectLine[j] = '─';
                    }
                }
                if (np.node.left != null || np.node.right != null) {
                    connectLine[np.pos] = '│';
                }
            }
        }

        treeStr.append(new String(nodeLine)).append('\n');
        if (i < layers.size() - 1) {
            treeStr.append(new String(connectLine)).append('\n');
        }
    }
    return treeStr.toString();
}

// 辅助方法：计算树高度
private int getHeight(Node node) {
    if (node == null) return 0;
    return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

// 辅助类：记录节点打印位置
private static class NodePosition {
    Node node;
    int pos;
    int level;
    NodePosition(Node node, int pos, int level) {
        this.node = node;
        this.pos = pos;
        this.level = level;
    }
}

可选优化点 #

• 支持多位数节点：将固定的nodeWidth改为遍历所有节点取节点值字符串的最大长度即可，不会出现对齐错位
• 适配纯ASCII终端：将Unicode框线字符替换为/、\、-即可
• 实现斜连接线效果：调整连接线绘制逻辑，将水平横线段替换为对应位置的斜向字符即可，和示例效果完全一致

内容的提问来源于stack exchange，提问作者Regyu