如何画树结构？（二维空间分配树递归算法？）

发布于 2024-09-16 18:38:35 字数 388 浏览 9 评论 0原文

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

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

有什么想法吗？

更新

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

泼猴你往哪里跑 2024-09-23 18:38:35

我会尝试沃克算法。这是一篇关于该算法的学术论文。如果您想查看代码，请查看 NodeLinkTreeLayout 在 Prefuse 中。 Prefuse 是开源的，因此只要您遵守许可证条款，根据您的情况调整代码就不会有任何问题。

回复收藏 0 原文

情绪失控 2024-09-23 18:38:35

我建议沿线绘制树。您可以通过使用某种移动的“绘图光标”来完成此操作。

您可以为每个节点存储一个属性width，其计算如下：

离开的width是1，
内部节点的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

然后，自下而上，宽度 s 作为子级 widths 的总和：

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

因此，您从根 (width 9) 开始，经过 4.5 步到达第一行中的 rigt。

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

第一个子节点的 width 为 2，因此我们向右移动 2/2=1 条网格线并绘制节点，然后将绘图光标从剩余的 1 条网格线移动到正确地完成节点。因此，下一个节点的宽度为 4，这意味着我们向右走 4/2=2 条网格线，绘制，走剩下的 2 步，依此类推。

下一行依此类推。最后（或在中间步骤中），连接节点。

此过程可确保不存在重叠节点（如果网格线彼此距离足够远），但它可能会导致相当大的树图，从而可以更有效地使用空间。

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

I suggest drawing the tree linewise. You do this by using some kind of moving "drawing cursor".

You could store an attribute width for each node which is calculated as follows:

the width of a leave is 1
the width of an inner node is the sum of all childrens' widths

Then, you draw the root "in the first line" in the middle, which means, you just take root's width's half.

Then, you generate a grid over the image such that each gridline corresponds to one line resp. one step from left to right and each intersection of grid lines can contain a node and each node has enough space.

Then, you iterate through the childs and while iterating, you accumulate the children's widths and draw the children "in the next line". To draw currentChild, you move your drawing cursor currentWidth/2 to the right, draw currentChild, and move the drawing cursor the remaining currentWidth/2 to the right.

In order to get the nodes in a good order, you might consider a breadth first search.

I hope my explanation is clear, but I think it will be better, if I draw a little picture.

This is our tree (x are nodes, everything else edges)

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

So, you calculate the leaf's widths:

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

Then, bottom up, the widths as sums of childrens' widths:

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

So, you start at the root (width 9) and go 4.5 steps to the rigt in the first line.

Then, you move your "drawing cursor" to the second line, "column 0" (go to left).

The first child has width 2, so we go 2/2=1 grid lines to the right and draw the node and move the drawing cursor the remaining 1 grid lines to the right in order to finish the node. So, the next node has width 4, which means, that we go right 4/2=2 grid lines, draw, go the remaining 2 steps, and so on.

And so on with the next line. At the end (or in intermediate steps), connect the nodes.

This procedure ensures that there are no overlapping nodes (if grid lines are far enough from each other), but it might lead to quite large tree diagrams that could use the space more efficiently.

In order to detect unused space, one might just scan the lines after the above process and look if there are unused grid line intersections and then possibly realign some nodes in order to fill space.

回复收藏 0 原文