高效绘制树形结构的算法？

Question

我需要在C#中绘制公司组织结构树（类似于家谱）。所有附属代码都已经准备好了。它是彩色的、互动的和花哨的。唯一的问题是实际决定放置每个节点的算法让我很苦恼。

目前，盒子大小为100x50，并且我有一个名为StaffNode的类，表示特定x、y坐标处的员工。

该算法只需要创建一个具有相应x和y值的List<StaffNode>。

这非常棘手。

基本上，该算法沿着公司结构进行递归，因此沿着树的左->右，然后是上->下。显然，如果两个节点重叠在一起，就会出现问题。

我可以想到几种可能产生这样结果的算法：

          *
    o         O
o o o o o     O
o         O O O O O
                O

相比之下，像这样做会更好，因为树非常大，空间非常有限：

       *
    o     O
o o o o o O
o     O O O O O
            O

您们中有没有人曾经画过这样的树形图？如果有，我相信您们也遇到了我所面临的许多障碍。您们有什么建议吗？到目前为止，我已经花了整整一天的时间在上面。

- user1002358

---

你想做什么？难道不应该在微软Visio或其他类似的软件中完成吗？ - DrStrangeLove

@DrStrangeLove 不，我正在编写一个交互式可视化。 - user1002358

Answer 1

有许多好的算法可以用于绘制树，每种算法都展示了树的不同属性。如果您想展示层级结构，可以使用这段WPF代码绘制层次结构。对于绘制图形和树形结构的更一般性讨论，请考虑查看这些关于Reingold-Tilden算法的幻灯片，该算法相对容易实现并且在理论和实践中运行速度快。此外还有这些优秀的幻灯片涵盖类似的内容。

希望能对您有所帮助！

- templatetypedef

---

太完美了！正是我所需要的。它使用了Reingold-Tilford算法。 - user1002358

@user1002358 谢谢您的评论。我在这里列出的答案中有些难以理解算法，但是通过谷歌搜索“Reingold-Tilford algorithm”，我找到了这个问题，我觉得更有用。我还总结了编写该算法的步骤在这里，以防其他人正在寻找简单的解释。 - Rachel

Answer 2

您可以使用迭代方法。使用类似于您上面使用的第一个示例的方式布置树形结构。然后将节点或子树彼此靠近，同时确保不违反任何约束条件（例如：节点不能重叠，子节点必须在父节点下方）。

优点：

• 简单的算法。
• 得到足够好的解决方案。
• 可连续应用于变化的树形结构。
• 可以让它看起来很酷。

缺点：

• 可能需要多次迭代才能达到良好的效果。
• 可能无法找到最佳解决方案（陷入局部最大值）。

- geofftnz

---

你可以在单次迭代中完成类似的操作。 - Michael Nett

同意，但是如果单次遍历算法在大量节点上计算不可行时，迭代优化方法有时会很有用。 - geofftnz