如何垂直打印二叉树搜索类？

Question

我一直在学习如何使用C++中的链接列表编写二叉树搜索.一切正常,我理解二进制树是如何工作的,但是我希望能够打印出头部顶部的树以及下面的所有节点,我试图在这里演示:

                                     [root or head]
                            [left]                    [right]

                      [left]      [right]       [left]       [right]

我使用控制台打印树,因此可以随意使用'cout'或'printf'.我相信我需要设置控制台的宽度,但我不知道如何开始.

谢谢,Y_Y

Answer 1

正如sbi所提到的,制作左对齐版本比中心对齐版本更容易.但无论你选择哪种对齐,你的基本算法方法应该是:

首先遍历树的广度.通过使用具有以下算法的队列来执行此操作:

1. 声明队列
2. 将根节点添加到队列中
3. 当队列包含更多节点时,请执行4 - 6:
4. 将节点出列队列
5. 打印节点.每次打印比第2次(从1开始)小一次打印​​后,也打印换行.
6. 将节点的子节点排入队列

(见http://www.cs.bu.edu/teaching/c/tree/breadth-first/)

为了打印中心对齐的树,也要执行以下操作(仅在树完成时才有效.如果它不完整,最简单的方法是制作一个完整的副本,其中应该有节点的每个地方都有某种形式一个空节点):

• 不是打印到屏幕上,而是将每行"打印"成字符串数组中的字符串.
• 随着时间的推移,跟踪您打印的最长元素的字符长度.我们称之为maxElemLen.
• 无论何时打印元素,都要在其前面打印一个制表符,在其后面打印一个制表符.
• 最后,返回,并在数组的每一行中,用2 ^(nLines - lineNum)制表符替换每个制表符.
• 然后将标签或换行符后面的每个标签展开到maxElemLen + 1个空格,并展开其他任何标签后的每个标签(即打印后的elem)到(maxElemLen + 1 - (自上一个标签后经过的字符数) ))空间.
• 最后,按顺序打印数组的每一行.