Reingold-Tilford算法的步骤是什么，我该如何编程实现它？

Question

Reingold-Tilford算法的步骤是什么，我该如何编程实现它？

11

从第三页的演示文稿：图表和树中，展示了 Reigngold-Tilford 过程的可视化过程；在此之前，它也对该算法进行了粗略的摘要：

"...从下往上遍历树;
[完成]从上往下遍历以分配最终位置..."

我可以通过递归方式实现两个方向的遍历，并且我知道 Y 坐标与每个节点的生成级别相关，但我仍然不知道如何解决 X 坐标。

我确实找到了这个项目：用于 WPF 的 Graph Tree Drawing 控件但是有太多代码，我很难找到应该是简单的2-3方法来定义 X 值。（我也没有使用过 WPF）

我已经搜索和尝试了几天如何实现它，所以非常感谢您的帮助！

- TekuConcept

2个回答

4

有一些涉及Python的代码文章可以在billmill.org上找到，关于C语言的代码可以在1991年2月1日的Dr. Dobb's Journal article的第2页中找到。你要求“简单的2-3种方法”（可能是指食谱式的方法），但是以所有可能性绘制树状图是一个NP完全问题（请参见Supowit，K.J.和E.M. Reingold，“The complexity of drawing trees nicely”，Acta Informatica 18，4，1983年1月，377-392，DDJ文章中的参考文献4）。Reingold-Tilford算法以线性时间更或多或少地漂亮地绘制二叉树，而Buchheim的变体以线性时间更或多或少地漂亮地绘制n元树。然而，billmill文章在陈述原则6之后指出，“到目前为止，每当我们在本文中查看简单算法时，我们发现它不足以...”，因此较简单的方法能否正常工作的可能性很小。

- James Waldby - jwpat7

我所说的2-3个简单方法是指“简单地”获取那些x值。我已经知道为了正确地将每个节点绘制到屏幕上需要更多的方法：我的第一个数据可视化控件是一个太阳图控件，可以在这里找到：http://tekuconcept.blogspot.com/2012/10/adjacency-sunburst-diagram-in-c.html；我会阅读你刚才分享的链接。 - TekuConcept

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rachel · Accepted Answer

我发现 jwpat7的回答中列出的文章很有用，尽管我花了一些时间才弄清楚这个算法所需的确切逻辑，所以我写了自己的博客文章来简化解释。

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

从树的后序遍历开始
将每个节点的初始X值分配为0（如果它是集合中的第一个）或previousSibling + 1 （如果不是第一个）。
如果一个节点有子节点，则找到使其居中在其子节点上方的所需X值。
- 如果该节点是最左边的节点，则将其X设置为该值
- 如果该节点不是最左边的节点，则在节点上设置一个Mod属性，用于将所有子节点向左移动，以便它们在该节点下居中。树的最后一次遍历将使用此Mod属性来确定每个节点的最终X值。
确定该节点的任何子节点是否会重叠到此节点左侧兄弟节点的任何子节点。基本上，对于每个Y，从两个节点中获取最大和最小的X，然后进行比较。
- 如果发生任何冲突，请移动节点以满足需要的距离。移动一个子树只需要添加到节点的 X和Mod属性中。
- 如果节点被移动了，还需要将两个重叠的子树之间的任何节点移动，使它们保持等间距
检查最终X值的计算结果，确保没有负数的X值。如果发现有任何负数值，则将最大的负数值添加到根节点的X和Mod属性上，以平移整棵树
使用前序遍历对树进行第二次遍历，并将每个节点的父节点的Mod值之和添加到该节点的X属性中

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

enter image description here

我在我的博客文章中提供了更多细节和一些示例代码，但这里无法包含所有内容，我希望着重关注算法的逻辑而非代码的具体细节。