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

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

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

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

• 这个 宽度 休假天数为1
• 宽度 一个内部节点的值是所有子节点的值之和 宽度 s

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

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

然后,遍历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步,依此类推。

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

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

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

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

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

根据数据的性质 TreeMap