jsp实现树状结构

现在的位置: 首页 > 综合 > 正文

RSS

jsp实现树状结构

2011年12月09日 ⁄ 综合 ⁄ 共 2216字 ⁄ 字号小中大 ⁄ 评论关闭

首先，介绍一下树状结构在DB中的存储。

使用二维表，如下图，存储树状结构：

现在，我们的目标是想要把这一树状结构表示成：

由上图可以看出它们之间含有一种层级关系，查看源代码，如下：

现在，算法的思路是，先将树状结构按照list的顺序排列出来，这个顺序其实就是去掉了UL和LI标签的顺序，如：

要实现这个顺序其实很简单。

再来看看我们的树

abcdef其实就是这颗树的先序遍历的结果。

那么，如果现在我们只有一张二维表，那么我们要怎样生成这个先序遍历的结果呢？（不使用递归）

观察这张二维表：

node到fatherNode是一对一映射，而fatherNode到node之间则是一对多映射。

也就是说我们可能不太容易知道某个节点的兄弟节点（需要先确定父节点，再通过父节点query兄弟节点），但是确定某个节点的子节点是非常容易的。

如，节点a的所有子节点，只要query fatherNode=a即可。

因此，我们可以使用广搜的思想来解决这个问题。

广搜就是先遍历离根最近的第一层节点，将这些节点放入queue中，然后从queue头不断取出节点，再遍历这个节点的所有子节点，并将其子节点放入queue的队尾，依次下去，知道所有节点都遍历到为止。

拿我们的树来说，就是

但是，如果直接用广搜这个算法的话，我们得到的序列是：

abdcef

与我们所期待的不同。

所以，改进一下该算法。

为了存储我们的结构，新建一个列表。现在，我们就有两个列表了，一个是广搜用的queue，另一个是存储结果的list。

当广搜每摘掉一个头元素，并将该元素的子节点放入queue中时，就在存储的list中的相应位置插入这些子节点们。那么相应位置是哪里呢？就是被摘掉的这个头元素。

例如，现在queue的形态为 “a” ，那么现在要做的操作是把queue的头，a元素摘掉，并且将其子节点"b d"加入queue中，与此同时，在list中查找到a的位置，并将“b d”添加到其后面。此时，queue的形态变为"b d"，而list则变为"a b d"。重复此步骤，现在摘掉queue中的头元素，即b，并且将其子节点（c）放入queue尾部，同时在list的b元素后面添加b的子节点（c），此时，queue的形态变为“d c”，而list的形态变为“a b c d”。依照此方式一直进行到广搜结束，即进行到queue为空。

该算法结束时，就可以得到 a b c d e f 这一我们希望见到的序列了。

但是，这一序列丢失了一项很重要的信息，就是层次信息。

所以，再对算法进行一下改进，我们引入一个结构体

<node, level>

使用 level 属性来记录某个节点所处的层次。

那么level这个属性在什么时候进行赋值呢？

在将某个元素的子元素插入list中时。

如何赋值呢？

这个问题很简单，因为是为某个元素插入子元素，因此，被插入的这些元素的level相当于其父节点的 level + 1

所以，list最后就变成了这样一个结构：

node list的顺序 “abcdef”，以及其level属性都是必须的。

现在，我们既知道了节点的顺序，也知道了节点中各个点的关系，因此就可以构建又ul和li表示的树状结构了。

我们再观察一下源代码：

发现，

（1）当level增大时，就会出现一个<ul>标签。

（2）当level减小时，就会出现</ul>标签，而</ul>标签的数量与level减小的程度有关，即减小的level是N，就应该出现N个</ul>标签。

（3）对于每一个list中的item，都由一个<li></li>标签对包围。

由上述规则，我们就可以写出如下程序：

Stack<String> stack = new Stack<String>();
        String item = "</ul>";
        String res = "";
        
        ArrayList<SightLevelPair>  list = this.sightTree.getList();
        
        int lastLevel = 0;
        int currLevel = 0;
        
        if(list.size() != 0){
            
            Iterator<SightLevelPair> iter = list.iterator();
            
            while(iter.hasNext()){
                
                SightLevelPair pair = iter.next();
                
                currLevel = pair.getLevel();
                
                if(currLevel > lastLevel){
                    res += "<ul>";
                    stack.push(item);
                }else if(currLevel < lastLevel){
                    int delta = lastLevel - currLevel;
                    
                    while(delta > 0){
                        res += stack.pop();
                        --delta;
                    }
                    
                }
                
                res += "<li>" + pair.getSight().getSightName() + "</li>";
                lastLevel = currLevel;
            }
            
            while(0 != stack.size()){
                res += stack.pop();
            }
        }