10

从演示文稿：第 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的经验）

几天来，我一直在搜索和试验如何做到这一点，非常感谢您的帮助！

4

2 回答 2

43

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

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

  • 从树的后序遍历开始

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

    在此处输入图像描述

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

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

    • 如果节点不是最左边的节点，请将Mod节点上的属性设置(X - centeredX)为 以移动所有子节点，使它们位于该节点的中心。树的最后一次遍历将使用此Mod属性来确定每个节点的最终 X 值。

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

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

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

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

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

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

在此处输入图像描述

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

于 2014-04-21T15:36:38.983 回答
4

A couple of articles are available that include code, in python at billmill.org and in C on page 2 of a 1 February 1991 Dr. Dobb's Journal article. You have asked for “simple 2-3 methods” (perhaps meaning cookbook methods) but drawing trees nicely in all their generality is an NP-complete problem (see Supowit, K.J. and E.M. Reingold, "The complexity of drawing trees nicely," Acta Informatica 18, 4, January 1983, 377-392, ref. 4 in the DDJ article). The Reingold–Tilford method draws binary trees more or less nicely in linear time, and Buchheim's variation draws n-ary trees more or less nicely in linear time. However, the billmill article points out (shortly after stating Principle 6), “Every time so far that we've looked at a simple algorithm in this article, we've found it inadequate...” so the likelihood of simpler methods working ok is small.

于 2012-10-29T21:11:27.417 回答