如何绘制树形结构？（一个二维空间分配的树递归算法？）

Question

6

我有一个任意的节点树结构。我想绘制这棵树，以提供用户视觉表示。我需要递归遍历树，并为每个节点添加一个图形项到列表中，然后在树递归完成后只需绘制项目列表。递归和绘制项当然是微不足道的 - 更复杂的是如何定位图形节点，使它们不重叠其他分支。

我正在使用Android，但这并不重要 - 我正在寻找一种方法，可能是一种算法，可以在经过树时保持2D空间的图像，因此它只分配最合适的坐标给每个节点，因为它通过。

有什么想法吗？

更新

- flesh

5个回答

4

我会尝试使用Walker算法。这里是关于该算法的学术论文。如果您想查看代码，请查看Prefuse中的NodeLinkTreeLayout。Prefuse是开源软件，只要遵循许可证条款，适应您的情况不应该有任何问题。

- Jay Askren

2

最终，我使用了Buchhiem版本的Walker算法。谢谢。 - flesh

2

看一下DOT语言。您可以将树转换为点表示，然后使用Graphviz以任何格式可视化。例如，Doxygen使用它来表示程序的结构。

- pmod

谢谢，虽然Graphviz在Android上不起作用，所以它并没有太大帮助 :( - flesh

@flesh，你说过“我正在使用Android但这并不重要”。现在你又说如果它不能在Android上运行，那么它就没有太大的帮助了？ - LarsH

LarsH - 我说这不重要是因为我在寻找一种理论方法或算法，而不是一个库。你建议了一个库，或者至少需要一个库来解析的语言，但似乎都不能在Android上工作。不过还是感谢你的建议 :) - flesh

2

Graphviz和mfgraph非常强大，但它们是用于一般图形的，对于树结构来说可能过于复杂。

可以尝试在Google上搜索tree+layout+algorithm或者查看带有布局的图形JavaScript树。后者虽然有些老旧，但它使用HTML画布和JavaScript，并且解释了代码，因此代码和方法都应该是可移植的。

- LarsH

0

根据您的数据性质，TreeMap 可能比 tinkertoy 表示更合适。

- Carl Manaster

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phimuemue · Accepted Answer

我建议按行绘制树形图。你可以使用某种移动的“绘图光标”来实现。

你可以为每个节点存储一个名为width的属性，其计算方法如下：

- 叶子节点的width为1 - 内部节点的width为所有子节点的width之和

接下来，在图像中心的“第一行”绘制根节点，这意味着仅需要取根节点width的一半。

然后，生成一个网格，使每条网格线对应一行或从左到右的一步，每个网格线的交点都可以包含一个节点，而且每个节点都有足够的空间。

接下来，你可以迭代子节点，同时累加子节点的width并“在下一行”绘制子节点。要绘制currentChild，请将绘图光标向右移动currentWidth/2，绘制currentChild，然后将绘图光标向右移动剩余的currentWidth/2。

为了以良好的顺序获取节点，你可能需要考虑广度优先搜索。

希望我的解释清楚明了，但如果我画一个小图会更好。

这是我们的树形图（x是节点，其他内容是边缘）。

   +-------x--+-------+
   |          |       |
 +-x-+     +-+x+-+  +-x-+
 |   |     | | | |  | | |
 x   x     x x x x  x x x

所以，您需要计算叶子的宽度：

   +-------x--+-------+
   |          |       |
 +-x-+     +-+x+-+  +-x-+
 |   |     | | | |  | | |
 1   1     1 1 1 1  1 1 1

接下来，从底部开始，将子元素的width相加得到父元素的width:

   +-------9--+-------+
   |          |       |
 +-2-+     +-+4+-+  +-3-+
 |   |     | | | |  | | |
 1   1     1 1 1 1  1 1 1

因此，您从根（width 9）开始，在第一行向右移动4.5步。

然后，将“绘图光标”移动到第二行，“列0”（向左移动）。

第一个子节点的width为2，因此我们向右移动2/2=1个网格线，绘制节点并将绘图光标向右移动剩余的1个网格线以完成节点。因此，下一个节点的width为4，这意味着我们向右移动4/2=2个网格线，绘制，向右移动剩余的2个步骤，依此类推。

接下来进行下一行。在最后（或中间步骤中），连接节点。

这个过程确保没有重叠的节点（如果网格线彼此足够远），但可能会导致相当大的树形图，可以更有效地利用空间。

为了检测未使用的空间，可以在上述过程之后扫描行，并查看是否有未使用的网格线交点，然后可能重新对齐一些节点以填充空间。