一尘不染

Reingold-Tilford算法的步骤是什么?如何编程?

algorithm

从演示文稿:第3页的图和树,直观地展示了Reigngold-
Tilford过程中发生的事情;事先也对该算法给出了模糊的总结:"...starts with bottom-up pass of the tree; [finishes with] Top-down pass for assignment of final positions..."我可以通过递归方法实现两个定向传递,而且我知道Y值分别对应于每个节点的生成级别,但是我仍然对如何X坐标求解。

我确实遇到了这个项目:WPF的图形树绘图控件,但是有太多代码使我很难找到应该使用简单的2-3种方法定义X值的方法。(也没有使用WPF的经验)

我已经搜索并尝试了几天,现在已经做了很多实验,非常感谢您的帮助!


阅读 1187

收藏
2020-07-28

共1个答案

一尘不染

1991年2月1日Dr. Dobb的Journal文章的第2页上提供了几篇文章,其中包括代码,分别在python的billmill.org和C中提供。。您曾经要求“简单的2-3种方法”(也许是指菜谱方法),但在所有方面很好地绘制树是一个NP完全问题(请参见Supowit,KJ和EM
Reingold,“很好地绘制树的复杂性”,Acta Informatica
18,4,1983年1月,377-392,DDJ文章中的参考文献4)。Reingold–Tilford方法在线性时间或多或少地很好地绘制了二叉树,而Buchheim的变体在线性时间或多或少地很好地绘制了n元树。但是,billmill文章指出(在陈述了原则6之后不久),“到目前为止,我们每次都在研究本文中的简单算法时,都发现它不够用……”,因此,更简单方法可行的可能性好的很小。

2020-07-28