没有度数限制的绘制树形结构

Question

我正在进行分布式算法的可视化，该算法解决树相关的问题。

我需要绘制一颗给定的根树。

目前，我只能处理每个节点最多有两个子节点的情况。在这种情况下，对于每个节点 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

- pkacprzak

---

你可能会发现这个链接有用。m元树的情况在文章的最后讨论。 - rrufai

@rrufai请将评论发布为答案，我会接受它。 - pkacprzak

完成。将尽力逐步扩展，使其尽可能自包含。 - rrufai

Answer 1

引用Bill Mill的文章"Drawing Presentable Trees"，m元树绘图算法的核心步骤如下：

1. 对树进行后序遍历
2. 如果节点是叶子节点，则将其x坐标设置为0
3. 否则，对于每个子节点，将子节点尽可能靠近其左侧兄弟节点
4. 将父节点放置在其最左和最右子节点之间的中点位置

但上述步骤有一个问题，左侧的子树会导致其余部分向右推，导致不平衡。该文章实现了以下原则来解决这个问题：

原则6：父节点的子节点应该均匀分布。

文章中给出了这些步骤的Python实现链接。

- rrufai

Answer 2

这是一篇比较有名的论文，涉及绘制任意度数的树。

如果你想要一个快速且简单的方法，可以参考我的一个旧博客文章，其中会以ASCII艺术形式打印出树形结构。

- andrew cooke

---

这些链接很棒，但如果没有它们，你的答案就毫无价值。请尝试包含概念摘要以改善你的回答。 - idmean