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

Question

从演示文稿：第 3 页的图表和树，可以直观地展示 Reigngold-Tilford 过程中发生的情况；它还预先对该算法给出了一个模糊的总结：

"...starts with bottom-up pass of the tree;
[finishes with] Top-down pass for assignment of final positions..."

我可以通过递归方式实现两个方向的传递，并且我知道Y值对应于每个节点的生成级别，但我仍然迷失关于X坐标如何求解。

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

我已经搜索和试验了几天如何做到这一点，所以非常感谢您的帮助！

Answer 1

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

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

• 从树的后序遍历开始

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

  previousSibling + 1

  。

  

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

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

  • 如果该节点不是最左边的节点，请将节点上的

    Mod

    属性设置为

    (X - centeredX)

    以便移动所有子节点，使它们在此节点下居中。树的最后一次遍历将使用这个

    Mod

    属性来确定每个节点的最终 X 值。

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

  • 如果发生任何冲突，请将节点移动所需的距离。移动子树只需要添加节点的

    X

    和

    Mod

    属性。

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

• 进行检查以确保计算最终 X 时不存在负 X 值。如果找到，请将最大的添加到根节点的

  X

  和

  Mod

  属性中，以将整棵树移动到

• 使用前序遍历对树进行第二次遍历，并将每个节点父节点的

  Mod

  值的总和添加到其

  X

  属性

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

我在我的博客文章中提供了更多详细信息和一些示例代码，但是这里太长了，无法包含所有内容，我想重点关注算法的逻辑而不是代码细节。

Answer 2

有几篇包含代码的文章，在 billmill.org 上有 Python 版本，在 1991 年 2 月 1 日的第 2 页上有 C 版本 Dr.多布的日记文章。您要求使用“简单的 2-3 种方法”（可能意味着食谱方法），但从总体上讲，很好地绘制树木是一个 NP 完全问题（请参阅 Supowit、K.J. 和 E.M. Reingold，“精美绘制树木的复杂性”，Acta Informatica 18, 4, 1983 年 1 月，377-392，DDJ 文章中的参考文献 4）。 Reingold-Tilford 方法或多或少地在线性时间内很好地绘制了二叉树，而布赫海姆的变体或多或少地在线性时间内很好地绘制了 n 叉树。然而，billmill 的文章指出（在陈述原则 6 后不久），“到目前为止，每次我们在本文中查看一个简单的算法时，我们都会发现它不够......”因此更简单的方法起作用的可能性还好就是小。

Answer 3

当前存在的两个答案都非常好且有帮助。我在 python 中面临同样的问题，而且，我的树中的节点具有不同的宽度和高度。

我查看了两个答案中的所有链接，还从Rachel的博客下载了代码。但不幸的是，所有这些都没有包含解决此尺寸变化问题的解决方案。

我在网上进行了更多搜索，终于找到了一个完美的解决方案。我想在这里分享链接，希望这可以为有同样问题的人节省一些时间。

首先，我找到了这篇中文文章，是从这篇论文翻译过来的。在论文的同一文件夹，还有一些其他相关论文。

但对我来说，我想要一个可行的代码，而不是一篇解释如何做的论文。所以，我终于将这个JavaScript代码翻译成Python并解决了我的问题。

还有一个Java版本。

我希望这些信息可以帮助像我这样的人。