如何修正二叉搜索树垂直打印的空格计算逻辑？

问题描述 #

需实现二叉搜索树（BST）的垂直打印功能，采用广度优先遍历打印每层节点，但现有代码的空格计算逻辑错误，导致树形格式混乱。核心问题是通过位运算初始化的nodesInLevel、spaces变量未正确匹配每层的缩进和节点间隔需求。

错误输出 #

5
                /  \
        3    45
        /  \        /  \
    2    4    25    105

期望输出 #

5
            /  \
           3     45
         /  \   /  \
        2   4  25 105

核心修正思路 #

垂直打印二叉树的空格计算核心是保证父节点与子节点的对齐关系，需基于树的高度动态计算每层的前置缩进和节点间隔：

1. 前置缩进：第i层（从1开始计数）的前置空格数为 (1 << (height - i)) - 1，确保每层节点整体居中。
2. 节点间隔：同层节点之间的空格数为 (1 << (height - i + 1)) - 1，保证子节点能对齐到父节点的左右下方。
3. 边层空格：打印斜线（/和\）时，前置空格为当前层前置缩进减1，斜线组之间的间隔为节点间隔减2，确保斜线正确连接父节点与子节点。

修正后的完整代码 #

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;

    void printVertical() {
        if (root == null) return;

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        int height = getHeight(root);
        int nodesInLevel = 1;

        for (int i = 1; i <= height; i++) {
            // 计算当前层的前置空格和节点间隔
            int leadSpaces = (1 << (height - i)) - 1;
            int nodeGap = (1 << (height - i + 1)) - 1;

            // 打印节点层
            printSpaces(leadSpaces);
            for (int j = 0; j < nodesInLevel; j++) {
                Node curr = queue.poll();
                if (curr != null) {
                    System.out.printf("%d", curr.data);
                    queue.add(curr.left);
                    queue.add(curr.right);
                } else {
                    System.out.print(" ");
                    queue.add(null);
                    queue.add(null);
                }
                // 最后一个节点后不打印间隔
                if (j != nodesInLevel - 1) {
                    printSpaces(nodeGap);
                }
            }
            System.out.println();

            // 打印边层（非最后一层）
            if (i != height) {
                int edgeLead = leadSpaces - 1;
                int edgeGap = nodeGap - 2;

                printSpaces(edgeLead);
                for (int j = 0; j < nodesInLevel; j++) {
                    Node curr = queue.peek();
                    // 打印左斜线
                    System.out.print((curr != null && curr.left != null) ? "/" : " ");
                    printSpaces(2);
                    // 打印右斜线
                    System.out.print((curr != null && curr.right != null) ? "\\" : " ");
                    // 最后一组斜线后不打印间隔
                    if (j != nodesInLevel - 1) {
                        printSpaces(edgeGap);
                    }
                }
                System.out.println();
            }

            nodesInLevel *= 2;
        }
    }

    // 计算树的高度（根节点高度为1）
    int getHeight(Node node) {
        if (node == null) return 0;
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // 打印指定数量的空格
    void printSpaces(int count) {
        for (int i = 0; i < count; i++) {
            System.out.print(" ");
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(5);
        tree.root.left = new Node(3);
        tree.root.right = new Node(45);
        tree.root.left.left = new Node(2);
        tree.root.left.right = new Node(4);
        tree.root.right.left = new Node(25);
        tree.root.right.right = new Node(105);

        tree.printVertical();
    }
}

关键调整说明 #

1. 移除原代码中固定的spaces初始化和每层除以2的逻辑，改为每层动态计算leadSpaces（前置空格）和nodeGap（节点间隔）。
2. 节点层打印时，最后一个节点不再打印后续间隔，避免多余空格。
3. 边层打印时，斜线组之间的间隔调整为nodeGap - 2，确保斜线与上下层节点对齐。
4. 位运算的核心是利用2的幂次特性，匹配完全二叉树的节点分布规律，保证树形整体居中。

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