algorithm - 画树不受度数限制

Question

我正在研究解决树上问题的分布式算法的可视化。

我必须绘制一个作为输入给出的有根树。

目前，我知道如何处理每个节点最多有 2 个子节点的情况。在这种情况下，对于每个节点 v，我将 v 绘制为坐标为 (x(v), x(y)) 的圆，其中:

x(v) := index of v in the inorder traversal
y(v) := distance from v to the root

这很好用(当然树的宽度很大，但这对我来说并没有太大影响)但最多只适用于二叉树。

请建议我应该对一般树使用什么算法。我唯一的要求是绘图必须是平面的。

编辑:

the simpler algorithm is to implement, the better

Answer 1

引自文章"Drawing Presentable Trees" Bill Mill 提出的 m-ary 树绘制算法的核心步骤如下:

1. Do a post-order traversal of the tree
2. If the node is a leaf, give it an x coordinate of 0
3. Otherwise, for each of its children, place the child as close to its left sibling as possible
4. Place the parent node halfway between its leftmost and rightmost children

虽然上面的步骤有一个问题，左边的子树导致树的其余部分被推到右边并导致不平衡。文章实现了以下原则来解决问题:

Principle 6: The child nodes of a parent node should be evenly spaced.

有一个链接到 Python implementation文章中给出的这些步骤。