有趣的算法--关于树的界面展示

夏德虎

本篇讨论的是多叉树的界面展示算法.
对于多叉树的数据结构我们较容易实现，如下面所示代码:
/**
*多叉树
* @author 3zhengtao
*/
public class Node implements TreeNode{
    Node patent=null;//父节点
    VectorNode> children=new VectorNode>(2);//所有子节点
但现在假设一个多叉树已生成，并且数据已填充，展示到界面的算法又如何呢?
这方面肯定有较多的实现案例，如多数图形设计工具，UML设计器，JDevelop Bpel流程设计器，JBPM工作流设计器等等，他们已经有了成熟的实现案例。但算法却很难查找得到。
下面根据本人对该问题的尝试，偶尔发现一个较有趣的实现算法思想，与大家分享。
多叉树展示的难点在于:
1.父节点坐标要由所有下层孩子结点坐标确定，下层孩子几点个数不定。
2.父节点坐标受兄弟结点坐标相互约束，横坐标不允许交叉
即要展示成如下所示:
g-01

刚开始想了一段时间，无论是自上而下还是自下而上都不好实现(大家可尝试去想想)。
后来打开Eclipse，操作资源管理器树时，突然有了一种想法，如果先把树变成一般菜单的形式，则再转换成目标形式就容易了.
g-02

以上是纵向的形式，如果转置成横向的形式，就成了如下的形式:
g-03

如果转换成了g-03的形式，要变成g-01的结果，只需从最底层结点遍历，父节点横坐标取下级孩子结点的中点就完成了。这一步便相当简单了。
那么接下来关键是如何转换成g-03的形式，其实从g-03表现图来分析也不难了，由父节点完全可以决定下级孩子结点的坐标，因此用最普通的类先序遍历一次多叉树便可以了。


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/103146/showart_2056164.html