二叉树美观打印实现问题：竖线缺失与水平间距错误

我正在做一个代码挑战，需要实现PrintableTree接口——这是一个无平衡二叉搜索树，支持用add方法添加int值，核心要求是通过prettyPrint方法把树结构转换成带框画字符的字符串，按值从小到大展示。

我写了PrettyPrintableTree类实现该接口，但现在有两个问题：一是没法用“|”字符连接垂直距离远的节点，二是水平间距计算错误。

我的实现代码 #

public class PrettyPrintableTree implements PrintableTree {

    private static class Node {
        private final int data;
        private Node left = null;
        private Node right = null;

        public Node(int data) {
            this.data = data;
        }

        public int getSize() {
            return Integer.toString(data).length();
        }

    }

    private Node root = null;
    private StringBuilder mainSB = new StringBuilder();

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

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

    private void printSimple(Node node) {
        if (node != null) {
            printSimple(node.left);
            System.out.println(node.data);
            printSimple(node.right);
        }
    }

    @Override
    public String prettyPrint() {
        printTree(root,0, false);
        System.out.println(mainSB);
        return mainSB.toString();
    }

    private void printTree(Node node, int space, boolean isRight)
    {

        if (node == null) return;

        space += node.getSize() + 1;
        printTree(node.left, space, false);

        if (node == root) {
            space = space - root.getSize() - 1;
        }
        if (node == root.left) {
            space = root.getSize();
        }
        if (node == root.right) {
            space = root.getSize();
        }

        mainSB.append(" ".repeat(Math.max(0, space)));
        if (node.right == null && node.left == null) {
            if (node == root)
                mainSB.append(node.data).append("\n");
            else
                mainSB.append(isRight ? "└" : "┌").append(node.data).append("\n");
        }
        else if (node.right != null && node.left != null) {
            if (node == root)
                mainSB.append(node.data).append("┤").append("\n");
            else
                mainSB.append(isRight ? "└" : "┌").append(node.data).append("┤").append("\n");
        }
        else if (node.right == null) {
            if (node == root)
                mainSB.append(node.data).append("┘").append("\n");
            else
                mainSB.append(isRight ? "└" : "┌").append(node.data).append("┘").append("\n");
        }
        else {
            if (node == root)
                mainSB.append(node.data).append("┐").append("\n");
            else
                mainSB.append(isRight ? "└" : "┌").append(node.data).append("┐").append("\n");
        }

        printTree(node.right, space, true);

    }
}

当前错误输出示例 #

测试元素：123 11 200 1 100 150 2000 #

┌1
   ┌11┤
       └100
123┤
        ┌150
   └200┤
        └2000

测试元素：931 39 196 385 388 207 185 955 957 542 904 498 394 #

┌39┐
           ┌185
       └196┤
               ┌207
           └385┤
               └388┐
                           ┌394
                       ┌498┘
                   └542┤
                       └904
931┤
   └955┐
       └957

问题修复方案 #

1. 水平间距错误修复 #

当前硬编码root左右子节点间距的逻辑是问题核心，这种方式无法适配多层嵌套节点。需要改成基于节点层级和父节点尺寸的动态间距计算，移除针对特殊节点的硬编码判断，递归时根据父节点宽度动态调整缩进值。

2. 添加垂直连接符“|” #

要实现垂直连接，需要在递归时传递每层是否需要绘制垂直连接线的状态。可以用一个列表记录层级状态，在绘制缩进时，根据状态替换部分空格为“|”。

修改后的核心递归方法示例：

private void printTree(Node node, int indent, List<Boolean> drawVerticalLines) {
    if (node == null) return;

    // 处理左子树：标记对应层级需要保留垂直连线
    List<Boolean> leftLines = new ArrayList<>(drawVerticalLines);
    leftLines.add(true);
    printTree(node.left, indent + node.getSize() + 1, leftLines);

    // 绘制前缀：根据状态填充空格或垂直连线
    for (int i = 0; i < indent; i++) {
        mainSB.append(drawVerticalLines.get(i) ? "│" : " ");
    }

    // 绘制节点连接符与内容
    if (drawVerticalLines.isEmpty()) {
        // 根节点无前置连接符
        mainSB.append(node.data);
    } else {
        boolean isRightChild = !drawVerticalLines.get(drawVerticalLines.size() - 1);
        mainSB.append(isRightChild ? "└──" : "┌──").append(node.data);
    }

    // 根据子节点情况添加后缀符号
    if (node.left != null && node.right != null) {
        mainSB.append(" ┤");
    } else if (node.left != null) {
        mainSB.append(" ┘");
    } else if (node.right != null) {
        mainSB.append(" ┐");
    }
    mainSB.append("\n");

    // 处理右子树：标记对应层级不需要保留垂直连线
    List<Boolean> rightLines = new ArrayList<>(drawVerticalLines);
    rightLines.add(false);
    printTree(node.right, indent + node.getSize() + 1, rightLines);
}

同时更新prettyPrint方法，确保每次调用重置字符串缓存：

@Override
public String prettyPrint() {
    mainSB.setLength(0); // 重置缓存，避免多次调用累积内容
    printTree(root, 0, new ArrayList<>());
    return mainSB.toString();
}

3. 额外优化点 #

• 节点的getSize方法可以缓存计算结果，避免每次调用都执行Integer.toString
• 移除printSimple这类无关测试代码，保持实现简洁

内容的提问来源于stack exchange，提问作者Михаил Буркацкий