以文本/ ASCII形式渲染水平二进制树的算法

Question

它是一个非常普通的二叉树,除了其中一个节点可能为空的事实.

我想找到一种以水平方式输出它的方法(也就是说,根节点在左侧并向右扩展).

我有一些垂直扩展树木的经验(根节点在顶部,向下扩展),但在这种情况下,我不知道从哪里开始.

最好是遵循以下几条规则:

• 如果一个节点只有一个子节点,则可以将其作为冗余跳过(始终显示"终端节点",没有子节点)
• 相同深度的所有节点必须垂直对齐; 所有节点必须位于所有较低深度节点的右侧,并且位于所有较深节点的左侧.
• 节点具有包含其深度的字符串表示.
• 每个"端节点"都有自己独特的线路; 也就是说,行数是树中终端节点的数量,当终端节点在一条线上时,该终端节点之后该行上可能没有其他内容.
• 作为最后一条规则的结果,根节点在左上角或左下角可能会更好; 左上角是首选.

例如,这是一个有效的树,有六个端节点(节点由一个名称及其深度表示):编辑:请参阅问题的底部以获得替代,更容易渲染

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

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

0              a
              / \
1            g   *
            / \   \
2          *   *   *
          /     \   \
3        k       *   b
                /   / \
4              h   *   *
              / \   \   \
5            *   *   f   c
            /     \     / \
6          *       i   *   *
          /           /     \
7        *           *       *
        /           /         \
8      *           *           d
      /           /
9    *           e
    /
10 j

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

(另外,为了澄清,我想生成第一个水平树;而不是这个垂直树)

我说语言不可知因为我只是在寻找算法; 我说ruby是因为我最终还是要在ruby中实现它.

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

主Tree类保留所有节点的轨道,并具有足够的算法来查找:

• 节点的第n个祖先
• 节点的第n个后代
• 节点的所有端节点后代及其计数
• 生成节点
• 两个给定节点的最低共同祖先

我已经知道了:

• 端节点的数量

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

---

进展

根据walkytalky的建议,我决定看看将每个"相关"或重要节点映射到网格的样子,其中列是深度,行可以通过端节点识别.以下是发生的情况(跳过第7列,因为深度7中没有重要节点):

depth: 0  1  2  3  4  5  6  8  9  10
       a        b     c     d
                               e
                      f
          g        h     i
                                  j
                k

使用广度优先或深度优先搜索生成此网格应该很容易.也许最简单的是通过简单地保持2D数组并将每个重要节点放入其中,为每个"第二个孩子"插入一行.

现在,了解这些事实:

• 一行中的最后一个节点必须是结束节点
• 子节点始终位于其父节点的右侧,同一行或更低位置.
• 所有非端节点必须只有两个子节点
• 因此,所有非端节点都有子列,它们是列的右边第一个,第一个子节点位于同一行,第二个子节点位于它们下面n行,其中n是右侧节点的数量.它.

我们可以看到,给定任何有效网格,有一种明确的方法可以"连接点",可以这么说; 有一个明确的树被代表.

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

基本上,这意味着渲染树的问题现在是渲染网格的更简单的问题,具有奇特的装饰.

谁能建议任何制定这些规则的方法？或者可能完全不同的方法？

---

编辑

我已经设想了一个更容易,更简单的最终渲染:

--d0----d1----d3----d4----d5----d6----d8----d9----d10-- => guide line (not rendered)

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

--d0----d1----d3----d4----d5----d6----d8----d9----d10-- => guide line (not rendered)

尝试创建这个可能更容易,而不是我之前发布的那个.首先,它保留了一个漂亮的网格形状,你不必用对角线变幻无常.这些行都沿着清晰可见的列线映射.不幸的是,它远没有第一个那么漂亮.

Answer 1

如果有N结束节点，则必须有N-1具有 2 个子节点的内部节点。（可以有任意数量的具有 1 个子节点的内部节点，我们必须对其进行计数才能获得深度，但否则会忽略。）因此，生成树相当于将这些节点放置在网格上，其中：

• 网格中的行数是N
• 我认为列数介于1+floor(log2(N))和 之间2*N-1, depending on how much overlap there is; this probably doesn't matter much for our purposes, though
• 每个端点出现在不同的行上
• 同一深度的所有节点都出现在同一列中
• 所有内部节点与其最右边的后代端点出现在同一行

那么，让我们看看：

• 从深度优先、从右到左遍历树。
• 对于每个端点，记录其深度和标签。
• 对于每个 2 子内部，记录其深度、标签以及最右边和最左边子端点的索引。
• 按深度对整个批次进行排序——这为您提供了列排序，不同深度的数量给出了实际的列数。（我认为，所有其他排序都应该从步行中自动得出，但这里不是这种情况，因为任何分支都可以是任何深度。）
• 将所有节点放置在网格中。
• 将每个非端点节点右侧的空单元标记为水平分支。

• 将每个内部节点向下到其左子节点上方的行的空单元标记为垂直分支，并将左子节点所在级别的单元标记为结点。

• 使用适当的 ASCII 装饰进行打印。

更新：

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

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

• 向下迭代每一列并将列宽确定为size of fixed elements + max label length + floor(log10(depth) + 1)。（例如，固定元素可能是[和。我们可以替换]-]\n as the suffix for endpoints.)
• 对于每一行
  • 对于每一列
    • 如果单元包含节点或端点
      • 打印固定前缀
      • 打印标签
      • 打印深度
      • 打印填充空间（最大标签长度 - 当前标签长度）
      • 打印适当的后缀
      • 如果节点是端点，则跳到下一行
    • 如果单元格为空，则打印填充空格至列宽
    • 如果单元格包含垂直线，则打印一些选定的空格前缀数、一个条，并用空格填充
    • 如果单元格包含连接，则打印一些选定的前缀空格数、反斜杠，并用连字符填充
    • 如果单元格包含水平连字符，则打印连字符的完整列宽

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

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