打印二叉搜索树时如何计算每行所需的空间？

Question

我正在尝试创建一个函数，按照教授的要求以垂直方式打印二维二叉搜索树。但是，我无法计算打印树的每一行时所需的适当间距。这反过来又导致它看起来很混乱。

这是我的函数的循环/段，用于打印当前层：

for (int i = 0; i < nodesInLevel; i++)
        {
            current = dequeue(q);

            if (current != NULL)
            {
                printf("%d", current->data);
                enqueue(q, current->left);
                enqueue(q, current->right);
            }
            else
            {
                printf(" ");
                enqueue(q, NULL);
                enqueue(q, NULL);
            }

            if (i < nodesInLevel - 1) {
                printSpaces(4);
            }
        }
    
        printf("\n");

很简单，我使用广度遍历来导航树并相应地打印每一行。 下一部分是混乱的地方。 我应该打印斜线来指示边缘。 这应该很容易。只需打印一个新行（如新函数中所示），然后根据子项是否存在打印斜杠。

有问题的循环：

for (int i = 0; i < nodesInNextLevel; i++)
    {
        printSpaces(spaces  -   2);

        if (current == NULL)
        {
            printSpaces(2);
            continue;
        }

        if (current->left == NULL && current->right == NULL)
        {
            continue;
        }
        else if (current->left != NULL && current->right == NULL)
        {
            printSpaces(2);
            putchar('/');
        }
        else if (current->left == NULL && current->right != NULL)
        {
            printSpaces(3);
            putchar('\\');
        }else
        {
            printSpaces(2);
            putchar('/');
            printSpaces(2);
            putchar('\\');
        }
    }
        printf("\n");

两个 for 循环都在具有以下变量的更大 for 循环中执行：

for (int level = 1; level <= treeHeight; level++)
    {
        nodesInLevel = 1 << (level - 1);
        nodesInNextLevel = nodesInLevel;
        spaces = (1 << (treeHeight - level + 1) - 1);
...

现在，这可能是因为我缺乏使用二元运算符的经验。我直接使用 chatgpt 初始化了这些变量（我现在后悔这个想法）。

但由于某种原因，输出最终看起来像这样：

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

与我想要的相反，即：

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

在思考/起草程序概念时，如何纠正我的计算，以及如何继续进行此类计算。

Answer 1

您没有发布 [mcve]，因此有原始路线图。

如果树是平衡的，则取叶子节点中的最大数字，例如

D

。

行占位符的长度为

(D + 1) * N

，假设为 L，其中

N

为

2^(tree depth + 1)

。

对于每行输出，如

(L - N * (level node count)) / 2

空间、节点。

你将会得到

     5
  3     45
2   4  25 105

实现后，添加与 + 1 行类似的奇数行，但节点值只是替代

 /

和

\ 

。