children如何画出任意数量的树？

Question

我正在努力想出一种算法，该算法允许我绘制树状数据结构，其中每个节点可以有 0..n children。 我的问题是，我不知道我必须将节点放置多远才能使 children 不会重叠。

在此示例中，"d" 是 "b" 的 children，"g" 是 "e" 的 children，并且它们重叠在 x-axis 上，当我根据树的总宽度将 children 均匀地分布在其 parent 上方时。

              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

为了确定间距，我建议使用一个包含三个主要步骤的算法。我们将使用 graph theory: The tree to be draw consists of nodes a, b, c, ...

的语言

• 步骤 1. 我们首先为每个测量 距离[=51= 的节点确定 层 ] 到 根节点 a。我们假设您已将树准备为 adjacency list which mainly a table with 2 columns, start-node and end-node of each edge。在给定的示例中，我们有 a - b、a - c、b - d1、... b - d9、c - e、e - g1、...e - g9。请注意节点命名方案，它明确解析了 d 和 g 的多重性。我们最终得到这样的 table：

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

• 步骤 2. 我们还必须确定并跟踪每层的节点总数以及每层的节点数 leaf nodes，即没有任何节点的节点继任者。叶子在邻接表中很容易被识别为节点标识符，它只出现在第二列，而不是第一列。在给定的示例中，第 0 层和第 1 层没有叶子，第 2 层有 9 个叶子，即 d1 ... d9，第 3 层只有叶子 e1 ... e9。在这个阶段，我们构建了如下table：

# 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

• 步骤 3. 最后，我们用 cumulative leaf count 列扩展我们刚刚创建的 table。我们所做的就是总结我们已经遇到了多少个叶节点：

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

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