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

本篇讨论的是多叉树的界面展示算法.

对于多叉树的数据结构我们较容易实现，如下面所示代码:

/**
 *多叉树
 * @author 3zhengtao
 */
public class Node implements TreeNode{
    Node patent=null;//父节点

    Vector<Node> children=new Vector<Node>(2);//所有子节点

但现在假设一个多叉树已生成，并且数据已填充，展示到界面的算法又如何呢?

这方面肯定有较多的实现案例，如多数图形设计工具，UML设计器，JDevelop Bpel流程设计器，JBPM工作流设计器等等，他们已经有了成熟的实现案例。但算法却很难查找得到。

下面根据本人对该问题的尝试，偶尔发现一个较有趣的实现算法思想，与大家分享。

多叉树展示的难点在于:

1.父节点坐标要由所有下层孩子结点坐标确定，下层孩子几点个数不定。

2.父节点坐标受兄弟结点坐标相互约束，横坐标不允许交叉

即要展示成如下所示:

g-01


刚开始想了一段时间，无论是自上而下还是自下而上都不好实现(大家可尝试去想想)。

后来打开Eclipse，操作资源管理器树时，突然有了一种想法，如果先把树变成一般菜单的形式，则再转换成目标形式就容易了.

g-02



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

g-03



如果转换成了g-03的形式，要变成g-01的结果，只需从最底层结点遍历，父节点横坐标取下级孩子结点的中点就完成了。这一步便相当简单了。

那么接下来关键是如何转换成g-03的形式，其实从g-03表现图来分析也不难了，由父节点完全可以决定下级孩子结点的坐标，因此用最普通的类先序遍历一次多叉树便可以了。