如何正确对齐二叉搜索树(BST)中的左节点？

要实现节点对齐规范且斜线单独成行的树形输出，核心是基于父节点的位置和宽度动态计算子节点的缩进，同时单独处理斜线层的打印。以下是具体修改方案：

核心思路 #

1. 计算每个节点值的字符宽度，确保缩进计算精准
2. 左子节点的缩进需对齐到父节点的正下方（父节点起始位置 + 父节点宽度的一半）
3. 斜线层单独成行，根据左右子节点的位置对应打印/和\
4. 每一层的宽度动态分配（下一层宽度为上一层的一半），保证树形对称

修改后的完整代码 #

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 获取节点值的字符串宽度
int getNodeWidth(int val) {
    return to_string(val).size();
}

// 递归打印辅助函数
void printTreeHelper(TreeNode* root, int baseIndent, int levelWidth, bool isLeftChild) {
    if (!root) return;

    // 计算当前节点的缩进，确保对齐到父节点正下方
    int nodeWidth = getNodeWidth(root->val);
    int nodeIndent = baseIndent + (isLeftChild ? (levelWidth / 2 - nodeWidth / 2) : (levelWidth - nodeWidth / 2));
    cout << string(nodeIndent, ' ') << root->val << endl;

    // 无子女则无需打印斜线
    if (!root->left && !root->right) return;

    // 打印斜线层（单独成行）
    int leftSlashIndent = baseIndent + levelWidth / 2 - 1;
    cout << string(leftSlashIndent, ' ') << "/";
    if (root->right) {
        int rightSlashIndent = baseIndent + levelWidth - levelWidth / 2;
        cout << string(rightSlashIndent - leftSlashIndent - 1, ' ') << "\\";
    }
    cout << endl;

    // 递归打印左右子树，调整下一层的基准缩进和宽度
    int nextLevelWidth = levelWidth / 2;
    printTreeHelper(root->left, baseIndent, nextLevelWidth, true);
    printTreeHelper(root->right, baseIndent + nextLevelWidth, nextLevelWidth, false);
}

// 主打印函数
void printTree(TreeNode* root) {
    if (!root) {
        cout << "Empty tree" << endl;
        return;
    }

    // 递归计算树的高度
    auto getTreeHeight = [](auto&& self, TreeNode* node) -> int {
        if (!node) return 0;
        return max(self(self, node->left), self(self, node->right)) + 1;
    };
    int treeHeight = getTreeHeight(getTreeHeight, root);
    int initialWidth = pow(2, treeHeight) * 2; // 根据高度动态分配初始宽度

    printTreeHelper(root, 0, initialWidth, false);
}

// 测试示例
int main() {
    // 构建测试树：根5，左子5，右子8，右子的左7、右9
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(5);
    root->right = new TreeNode(8);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(9);

    printTree(root);

    // 实际使用时需手动释放内存，此处省略
    return 0;
}

关键细节说明 #

• 节点对齐逻辑：通过levelWidth / 2 - nodeWidth / 2计算左子节点的偏移，确保其正好位于父节点的正下方；右子节点则基于半层宽度偏移
• 斜线层处理：斜线的位置完全对应子节点的打印位置，单独成行输出，符合格式需求
• 动态宽度适配：通过计算树的实际高度自动分配初始宽度，避免固定值导致的适配问题

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