What are the step to the Reingold-Tilford algorithm and how might I program it?

Question

From the presentation: Graphs and Trees on page 3, there is a visual presentation of what takes place during the Reigngold-Tilford process; it also gives a vague summary to this algorithm before hand: "...starts with bottom-up pass of the tree; [finishes with] Top-down pass for assignment of final positions..." I can achieve both directional passes through recursive means, and I know that the Y-value(s) are respective to each node's generation level, but I'm still lost as to how the X-coordinates are solved.

我确实遇到过这个项目:WPF的图树绘制控件,但是有很多代码我很难找到应该是一个简单的2-3方法来定义X值.(也没有WPF的经验)

我一直在寻找和试验如何做这几天,所以非常感谢你的帮助!

Answer 1

我发现jwpat7的答案中列出的文章非常有用,虽然我花了一些时间来弄清楚这个算法所需的确切逻辑,所以我写了自己的博客文章来简化解释.

以下是如何确定X节点位置的纯文本逻辑:

• 从树的后序遍历开始

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

  

• 如果某个节点有子节点,请找到所需的X值,使其居中于子节点上.

  • 如果节点是最左侧的节点,请将其X设置为该值

  • 如果节点不是最左侧的节点,请Mod在节点上设置一个属性(X - centeredX),以便移动所有子节点,使它们在此节点下居中.树的最后一次遍历将使用此Mod属性来确定每个节点的最终X值.

• 确定此节点的任何子节点是否与此节点左侧的兄弟节点子节点重叠.基本上对于每个Y,从两个节点获取最大和最小的X,并进行比较.

  • 如果发生任何冲突,请将节点移动一段时间.移位子树只需要添加到X和Mod节点的性能.

  • 如果节点被移位,也移动重叠的两个子树之间的任何节点,使它们等间隔

• 进行检查以确保在计算最终X时,没有负X值.如果找到任何一个,则将最大的一个添加到根节点X和Mod适当的位置以将整个树移过

• 使用预顺序遍历对树进行第二次遍历,并将Mod节点父节点中每个值的总和添加到其X属性中

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

我在博客文章中有一些更多细节和一些示例代码,但是在这里包含所有内容太长了,我想专注于算法的逻辑而不是代码细节.