ruby - 以文本/ASCII 形式呈现水平二叉树的算法

Question

这是一个非常普通的二叉树，除了其中一个节点可能是空的。

我想找到一种方法以水平方式输出它(即根节点在左侧并向右扩展)。

我有一些垂直扩展树的经验(顶部的根节点，向下扩展)，但在这种情况下，我不确定从哪里开始。

最好，它将遵循以下几条规则:

如果一个节点只有一个子节点，它可以作为冗余跳过(总是显示没有子节点的“末端节点”)

所有相同深度的节点必须垂直对齐；所有节点必须在所有较浅节点的右侧和所有较深节点的左侧。

节点有一个字符串表示，其中包括它们的深度。

每个“端节点”都有自己独特的线路；也就是说，行数是树中端节点的数量，当一个端节点在一条线上时，该端节点之后的那条线上可能没有其他东西。

作为最后一条规则的结果，根节点在左上角或左下角可能会更好；左上角是首选。

例如，这是一个有效的树，有六个末端节点(节点由名称及其深度表示):编辑:请参阅问题底部的替代方法，更简单的渲染


[a0]-----------[b3]------[c5]------[d8]
\\\-----------[e9]
\\----[f5]
\-[g1]--------[h4]------[i6]
\\--------------------[j10]
\-[k3]

代表垂直的、显式的二叉树:

0个
/\
1 克 *
/\\
2 * * *
/\\
3 k * b
//\
4 小时 * *
/\\\
5 * * f c
/\/\
6 * 我 * *
//\
7 * * *
//\
8 * * d
//
9 * e
/
10 小时

(分支为了紧凑而折叠； * 代表冗余的单子(monad)节点；请注意， * 是实际节点，每个节点存储一个子节点，为了便于展示，这里省略了名称)

(另外，澄清一下，我想生成第一个水平树；而不是这个垂直树)

我说语言不可知，因为我只是在寻找一种算法；我说 ruby​​ 是因为无论如何我最终都必须在 ruby​​ 中实现它。

假设每个 Node数据结构仅存储其 id、左节点和右节点。

大师Tree class 跟踪所有节点并有足够的算法来查找:

节点的第 n 个祖先

节点的第 n 个后代

一个节点的所有端节点后代，以及它们的计数

节点的生成

两个给定节点的最低共同祖先

我已经知道:

端节点数

任何人都知道我可以从哪里开始？我应该采用递归方法吗？迭代？
一些伪代码也会很酷，非常感谢 =)

进度

根据 walkytalky 的建议，我决定看看将每个“相关”或重要节点映射到网格会是什么样子，列是深度，行是其末端节点可识别的。这是发生的情况(跳过第 7 列，因为深度 7 中没有重要节点):

深度:0 1 2 3 4 5 6 8 9 10
A B C D
电子
F
吉我
j
克

使用广度优先或深度优先搜索来生成这个网格应该很容易。也许最简单的方法是简单地保留一个二维数组并将找到的每个重要节点放入其中，为每个“第二个 child ”插入一行。

现在，知道这些事实:

一行中的最后一个节点必须是结束节点

子节点始终位于其父节点的右侧，并在同一行或更低的位置。

所有非端节点必须正好有 两个 child

因此，所有非端节点都有 的子节点。其列右侧的第一个 ，第一个子节点在同一行上，第二个子节点在它们下面的 n 行，其中 n 是它右侧的节点数。

我们可以看到，给定任何有效的网格，有 一种明确的方式 “连接点”，可以这么说；有一个明确的树被表示。

现在，“连接点”不再是一个二叉树结构的问题……它只是一个装饰问题。我们只需要构建一个算法来正确放置正确的 -的和 \是他们可以去的地方，也许只遵循简单的网格/词典规则，而不是二叉树结构规则。

基本上，这意味着渲染树的问题现在是更简单的问题 渲染网格 ，带有华丽的装饰。

任何人都可以提出任何制定这些规则的方法吗？或者可能是完全不同的方法？

编辑

我设想了一个更容易的最终渲染:

--d0----d1----d3----d4----d5----d6----d8----d9----d10-- => 引导线(未呈现)

[a0 ]-------[b3 ]-------[c5 ]-------[d8 ]
| |\--------------[e9]
|\---------[f5]
\---[g1 ]-------[h4 ]-------[i6 ]
|\---------------------------[j10]
\---[k3]

--d0----d1----d3----d4----d5----d6----d8----d9----d10-- => 引导线(未呈现)

尝试创建这个可能更容易，而不是我之前发布的那个。一方面，它保留了漂亮的网格形状，而且您不必对对角线变化无常。行都沿着清晰可见的列线映射。不幸的是，它远没有第一个那么漂亮。

Answer 1

如果有N端节点，必须有N-1有 2 个 child 的内部节点。 (可以有任意数量的具有 1 个子节点的内部节点，我们必须对其进行计数以获得深度，否则将忽略。)因此，生成树等效于将这些节点定位在网格上，其中:

网格中的行数为 N

我认为列数在 1+floor(log2(N)) 之间和 2*N-1 ，取决于有多少重叠；尽管

对我们的目的来说这可能无关紧要

每个端点出现在不同的行

相同深度的所有节点出现在同一列

所有内部节点与其最右边的后代端点出现在同一行

那么，让我们看看:

从右到左遍历树深度优先。

对于每个端点，记录其深度和标签。

对于每个 2-child 内部，记录其深度、标签以及最右侧和最左侧子端点的索引。

按深度对整个批次进行排序——这为您提供了列排序，不同深度的数量给出了实际的列数。 (我认为所有其他排序都应该从 walk 中自动出来，但这里不是这种情况，因为任何分支都可以是任何深度。)

将所有节点放在网格中。

将每个非端点节点右侧的空单元格标记为水平分支。

将每个内部节点向下到其左子节点上方行的空单元格标记为垂直分支，将左子节点级别的单元格标记为连接点。

使用适当的 ASCII 装饰打印。

更新:

正如你所说，定位足以明确确定连接，但你仍然需要做一些自下而上的工作才能做到这一点，所以我可能仍然会在网格构建过程中进行“标记”步骤。

我有点认为打印是微不足道的，足以掩盖，但是:

向下迭代每一列并确定列宽为 size of fixed elements + max label length + floor(log10(depth) + 1) . (例如，固定元素可能是 [ 和 ]- 。我们可以替换 ]\n 作为端点的后缀。)

对于每一行

对于每一列

如果单元格包含节点或端点

打印固定前缀

打印标签

打印深度

打印填充空间(最大标签长度 - 当前标签长度)

打印适当的后缀

如果节点是端点，则跳到下一行

如果单元格为空，则将填充空格打印到列的宽度

如果单元格包含一个垂直，打印一些选择的前缀数量的空格，一个条形，并用空格填充

如果单元格包含连接点，则打印一些选定的前缀空格数、反斜杠并用连字符填充

如果单元格包含水平，则打印连字符的完整列宽

如果首先生成直线版本，然后在字符数组中进行一些替换，则将其转换为打印对角线可能是最简单的——否则，您可能会遇到在与所在列不同的列中渲染长垂直分支的情况起源。

在某些时候，我可能会尝试将其放入代码中，但今天可能不会——要做的事情!