我有一个任意的节点树结构。我想绘制这棵树,以提供用户视觉表示。我需要递归遍历树,并为每个节点添加一个图形项到列表中,然后在树递归完成后只需绘制项目列表。递归和绘制项当然是微不足道的 - 更复杂的是如何定位图形节点,使它们不重叠其他分支。
我正在使用Android,但这并不重要 - 我正在寻找一种方法,可能是一种算法,可以在经过树时保持2D空间的图像,因此它只分配最合适的坐标给每个节点,因为它通过。
有什么想法吗?
更新
我正在使用Android,但这并不重要 - 我正在寻找一种方法,可能是一种算法,可以在经过树时保持2D空间的图像,因此它只分配最合适的坐标给每个节点,因为它通过。
有什么想法吗?
更新
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个步骤,依此类推。
接下来进行下一行。在最后(或中间步骤中),连接节点。
这个过程确保没有重叠的节点(如果网格线彼此足够远),但可能会导致相当大的树形图,可以更有效地利用空间。
为了检测未使用的空间,可以在上述过程之后扫描行,并查看是否有未使用的网格线交点,然后可能重新对齐一些节点以填充空间。
看一下DOT语言。您可以将树转换为点表示,然后使用Graphviz以任何格式可视化。例如,Doxygen使用它来表示程序的结构。
Graphviz和mfgraph非常强大,但它们是用于一般图形的,对于树结构来说可能过于复杂。
可以尝试在Google上搜索tree+layout+algorithm或者查看带有布局的图形JavaScript树。后者虽然有些老旧,但它使用HTML画布和JavaScript,并且解释了代码,因此代码和方法都应该是可移植的。