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

Question

在第3页的演示文稿：Graphs and Trees中，有一个在Reigngold-Tilford过程中发生的可视化演示；它还预先对此算法进行了模糊的总结："...starts with bottom-up pass of the tree; [finishes with] Top-down pass for assignment of final positions..." I可以通过递归方式实现两个方向的传递，我知道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值；如果不是，则为每个节点分配一个previousSibling + 1。

​

• 如果某个节点有子节点，则查找所需的X值，使其居中于其子节点的中心。

- If the node is the left-most node, set its X to that value
- If the node is not the left-most node, set a `Mod` property on the node to `(X - centeredX)` in order to shift all children so they're centered under this node. The last traversal of the tree will use this `Mod` property to determine the final X value of each node.

​

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

- If any collisions occur, shift the node over by however much needed. Shifting a subtree just requires adding to the `X` and `Mod` properties of the node.
- If node was shifted, also shift any nodes between the two subtrees that were overlapping so they are equally spaced out

​

• 执行检查以确保在计算最终X时，没有负的X值。如果找到最大的一个，则将最大的一个添加到根结点的X和Mod属性中，以在
• 上移动整个树。使用预排序遍历来第二次遍历树，并将每个结点的父结点的Mod值之和添加到其X属性

中

上述树的最终X值如下所示：

​

​

我在my blog post中有一些更多的细节和一些示例代码，但是它太长了，无法在这里包含所有内容，我想把重点放在算法的逻辑上，而不是代码的细节上。

Answer 2

有几篇文章包括代码，在billmill.org上用python编写，在page 2上用C编写，1991年2月1日发布的Dr. Dobb's Journal article。您要求的是“简单的2-3方法”(可能指的是食谱方法)，但是很好地绘制树的所有一般性是一个NP-完全问题(参见Supowit，K.J.和E.M. Reingold，"The complete of drawing trees nicely“，Acta Informatica 18，4,1983年1月，377-392，参考文献)。4在DDJ文章中)。Reingold-Tilford方法在线性时间内绘制二叉树或多或少很好，而Buchheim的变体在线性时间内绘制n元树或多或少很好。然而，比尔的文章指出(在陈述原则6之后不久)，“到目前为止，我们在本文中研究了一个简单的算法，我们发现它是不够的……”因此，更简单的方法正常工作的可能性很小。