如何用任意数量的孩子画一棵树？

Question

我正在努力想出一种算法，它允许我绘制一个像数据结构一样的树，其中每个节点可以有0..n个子节点。对我来说，问题是，我不知道我必须放置节点多远，以便子节点不会重叠。

在本例中，“d”是“b”的子级，“g”是“e”的子，当我在给定树的总宽度的情况下，将子级均匀分布在其父级上方时，它们在x轴上重叠。

              g g g g g g g g   (9 nodes)
              \ \ \ \ | / / /
d d d d d d d d d     e         (10 nodes)
\ \ \ \ / / / / /     |
       b              c         (2 nodes)
           \      /
              a                 (1 node)

节点不以任何方式排序。所以它实际上更像一个必须看起来像树的图。

Answer 1

为了确定间距，我提出了一种由三个主要步骤组成的算法。我们将使用图论的语言：要绘制的树由节点a、b、c组成。。。

• 第1步。我们从确定每个节点的层开始，该层测量到根节点的距离。我们假设您已将树准备为邻接列表，该列表主要是一个包含2列的表，每个边缘的起始节点和结束节点。在给定的示例中，我们有a-b，a-c，b-d1，...b-d9，c-e，e-g1，...e-g9。注意节点命名方案，它显式地解析了d和g的多重性。我们最终得到了这样的表：

# node: layer
a: 0
b: 1
c: 1
d1: 2
d2: 2
...
d9: 2
e: 2
g1: 3
g2: 3
...
g9: 3

< li >步骤2。我们还必须确定和跟踪每层的节点总数以及每层的叶节点数，即没有任何后继节点的节点数。在邻接表中，叶子很容易被识别为节点标识符，它只出现在第二列，而不出现在第一列。在给定的例子中，层0和1没有叶子，层2有9个叶子，即< code>d1...< code>d9，而第三层只剩下< code>e1...< code>e9在此阶段，我们已经构建了下表:

# layer: leave nodes, overall nodes, non-leave nodes (in this layer)
0: 0, 1, 1
1: 0, 2, 2
2: 9, 10, 1
3: 9, 0, 0

< li >步骤3。最后，我们用一列累积叶子计数来扩展刚刚创建的表。我们所做的就是合计我们已经遇到了多少个叶节点:

# layer: cumulative nodes
0: 0
1: 0
2: 9
3: 18

结果是18，这是显示无重叠树所需的列数。