英文:
How to draw a tree with an arbitrary number of children?
问题
我正在努力设计一个算法，允许我绘制类似树形数据结构的图，其中每个节点可以有0到n个子节点。
对我来说，问题在于我不知道要多远地放置节点，以确保子节点不会重叠。
在这个示例中，"d" 是 "b" 的子节点，"g" 是 "e" 的子节点，当我仅仅将子节点均匀地分布在其父节点的上方时，它们在x轴上重叠。
g g g g g g g g (9 个节点)
\ \ \ \ | / / /
d d d d d d d d d e (10 个节点)
\ \ \ \ / / / / / |
b c (2 个节点)
\ /
a (1 个节点)
这些节点没有以任何方式排序。所以它实际上更像是一个必须看起来像树的图。
英文:
I'm struggling with coming up with an algorithm which allows me to draw a tree like data structure where each node can have 0..n children.
The issue for me is, I don't know how far apart I have to place nodes so that children won't overlap.
In this example the "d"s are children of "b" and the "g"s are children of "e" and they overlap on the x-axis when I just spread children out evenly above its parent given the total width of the tree.
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)
The nodes are not ordered in any way. So it's actually more like a graph which has to look like a tree.
答案1
得分: 1
为了确定间距，我建议采用一个包括三个主要步骤的算法。我们将使用图论的语言：要绘制的树由节点 a、b、c 等等组成。
- 步骤 1. 我们从确定每个节点的层次开始，该层次度量到根节点
a的距离。我们假设您已经准备好了您的树，将其表示为邻接表，这主要是一个具有2列的表，每个边的起始节点和终止节点。在给定的示例中，我们有a - b、a - c、b - d1、...b - d9、c - e、e - g1、...e - g9。请注意节点命名方案，它明确解决了d和g的多重性。我们最终得到一个如下的表格：
# 节点: 层次
a: 0
b: 1
c: 1
d1: 2
d2: 2
...
d9: 2
e: 2
g1: 3
g2: 3
...
g9: 3
- 步骤 2. 我们还需要确定和跟踪每个层次的节点总数，以及每个层次的叶节点数，即没有任何后继的节点。在邻接表中，叶子节点可以轻松地识别为仅在第2列中出现的节点标识符，而不在第1列中出现。在给定的示例中，层 0 和 1 不包含叶子节点，层 2 有 9 个叶子节点，分别是
d1...d9，层 3 只有叶子节点e1...e9。在这个阶段，我们构建了以下表格：
# 层次: 叶节点数, 总节点数, 该层中的非叶节点数
0: 0, 1, 1
1: 0, 2, 2
2: 9, 10, 1
3: 9, 0, 0
- 步骤 3. 最后，我们扩展刚刚创建的表格，添加一个累积叶节点计数列。我们所做的只是总结我们已经遇到了多少叶节点：
# 层次: 累积节点数
0: 0
1: 0
2: 9
3: 18
结果是 18，这是显示树不重叠所需的列数。
英文:
In order to determine the spacing, I suggest an algorithm which consists of three main steps. We will use the language of graph theory: The tree to be draw consists of nodes a, b, c, ...
- Step 1. We start with determining the layer for each node which measures the distance to the root node
a. We assume that you have prepared your tree as adjacency list which mainly a table with 2 columns, start-node and end-node of each edge. In the given example, we havea - b,a - c,b - d1, ...b - d9,c - e,e - g1, ...e - g9. Note the node naming scheme, which explicitly resolves the multiplicity ofdandg. We end up with a table like this:
# node: layer
a: 0
b: 1
c: 1
d1: 2
d2: 2
...
d9: 2
e: 2
g1: 3
g2: 3
...
g9: 3
- Step 2. We also have to determine and track the overall number of nodes per layer as well as the number of leaf nodes per layer, i.e. nodes without any sucessor. Leaves can be identified easily in the adjacency list as node-identifiers which occur only in the 2nd column, but not in the 1st column. In the given example, layer 0 and 1 are free of leaves, layer 2 has 9 leaves, namely
d1...d9, and layer 3 has only leavese1...e9. At this stage, we have constructed the following 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
- Step 3. Finally, we expand the table which we just created with a column cumulative leaf count. All we do is to sum up how many leaf nodes we already encountered:
# layer: cumulative nodes
0: 0
1: 0
2: 9
3: 18
The result is 18, which is the number of columns needed to display the tree overlap-free.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论