代码之家 › 专栏 › 技术社区 › flesh

如何绘制树结构?(二维空间分配树递归算法?)

visualization tree graphics data-structures algorithm

flesh · 技术社区 · 14 年前

我有一个任意的节点树结构。我想画这棵树,为用户提供一个直观的表示。我需要在树上递归,并为每个节点向列表中添加一个图形项,然后在树递归完成后绘制项目列表。项目的递归和绘制当然很简单——更复杂的是如何定位图形节点,以便它们不会与其他分支重叠。

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

更新

5 回复 | 直到 14 年前

Jay Askren 14 年前

我想试试沃克算法。 Here's an academic paper NodeLinkTreeLayout 在里面 Prefuse . Prefuse是开源的,所以只要您遵守许可条款,就不应该有任何问题来调整代码以适应您的情况。

phimuemue 14 年前

我建议按线条画这棵树。您可以通过使用某种移动的“绘图光标”来实现这一点。

你可以存储一个属性 width 对于每个节点,计算如下:

然后,你在中间画根“在第一行”,也就是说,你只需要根的有一半。

然后,在图像上生成一个网格,使每个网格线分别对应于一条线。从左到右一步,网格线的每个交点都可以包含一个节点,每个节点都有足够的空间。

然后,遍历childs,在迭代的同时,累积childs的 宽度 把孩子们画在“下一行”。画 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

然后,自下而上 宽度 作为孩子的总和 宽度 学生:

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

所以,你从根开始( 宽度 9) 走4.5步到第一行的右边。

第一个孩子 2,我们走吧 2/2=1 宽度 4,也就是说,我们向右走4/2=2条网格线,画,走剩下的2步,依此类推。

此过程确保没有重叠的节点(如果网格线彼此之间的距离足够远),但它可能会生成相当大的树形图,从而可以更有效地利用空间。

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

pmod 14 年前

看一看 Dot . 可以将树转换为点表示,然后使用 格拉夫维兹 编程辅助工具

LarsH 14 年前

Graphviz和mfgraph功能强大,但它们适用于一般的图,可能对树有过多的杀伤力。

Graphic Javascript Tree with Layout 后者很旧,但它使用HTML画布和javascript,并且它解释了代码,因此代码和方法都应该是可移植的。

Carl Manaster 14 年前

根据数据的性质 TreeMap