c# - Reingold-Tilford 算法的步骤是什么？我应该如何对其进行编程？

Question

来自演示文稿:Graphs and Trees在第 3 页上，直观地展示了 Reigngold-Tilford 过程中发生的事情；它还预先对该算法给出了一个模糊的总结:“...从树的自下而上传递开始；
[结束于] 自上而下传递最终位置...” 我可以通过递归方式实现双向传递，并且我知道 Y 值对应于每个节点的生成级别，但我仍然不知道 X 坐标是如何求解的。

我确实遇到过这个项目:A Graph Tree Drawing Control for WPF但是代码太多了，我很难找到一个简单的 2-3 种方法来定义 X 值。 (也没有使用 WPF 的经验)

几天来我一直在搜索和试验如何执行此操作，非常感谢您的帮助!

Answer 1

我找到了 jwpat7's answer 中列出的文章非常有用，虽然我花了一段时间才弄清楚这个算法所需的确切逻辑，所以我写了我的 own blog post以简化解释。

这是确定 X 节点位置的纯文本逻辑:

• 以 post-order traversal 开头树的

• 为每个节点分配一个初始 X 值，如果它是集合中的第一个，则为 0，如果不是，则为 previousSibling + 1。

  

• 如果一个节点有子节点，请找到所需的 X 值，使其以其子节点为中心。

  • 如果该节点是最左边的节点，则将其 X 设置为该值

  • 如果节点不是最左边的节点，将节点上的 Mod 属性设置为 (X - centeredX) 以便移动所有子节点所以他们在这个节点下居中。树的最后一次遍历会使用这个Mod属性来决定每个节点最终的X值。

• 确定此节点的任何子节点是否会与此节点左侧的任何兄弟节点的子节点重叠。基本上对于每个Y，从两个节点中获取最大和最小的X，并比较它们。

  • 如果发生任何冲突，请将节点移到需要的位置。移动子树只需要添加到节点的 X 和 Mod 属性。

  • 如果移动了节点，还移动重叠的两个子树之间的任何节点，使它们等距

• 检查以确保在计算最终 X 时，没有负 X 值。如果找到任何一个，将最大的一个添加到根节点的 X 和 Mod 属性以将整棵树移动

• 使用先序遍历对树进行第二次遍历，并将每个节点父节点的 Mod 值的总和添加到它的 X 属性

上面树的最终 X 值如下所示:

我在 my blog post 中有更多详细信息和示例代码，但是在这里包含所有内容太长了，我想关注算法的逻辑而不是代码细节。