|
精华帖 (1) :: 良好帖 (2) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2012-01-24
最后修改：2012-08-19
利用多叉树实现Ext JS中的无限级树形菜单（一种构建多级有序树形结构JSON的方法）
一、问题研究的背景和意义
解决Ext JS无限级树形菜单的问题，可以拓展出更多的应用场景，例如树形结构表格TreeGrid，一次性生成树形表格，对树形表格进行完整分页，对表格列进行全排序；或者可以利用本文的思路扩展出其他的更复杂的应用场景。
先看两个图例，有个直观上的认识：
图二，树形结构表格
二、详细设计方案
文件一，branchTree.html （Ext树形控件页面）
Ext.onReady(
function(){
var tree = new Ext.tree.TreePanel({
height: 300,
width: 400,
animate:true,
enableDD:true,
containerScroll: true,
rootVisible: false,
frame: true,
// getBranch.do请求服务器返回多级树形结构的JSON字符串
loader: new Ext.tree.TreeLoader({dataUrl:'getBranch.do'}),
root : new Ext.tree.AsyncTreeNode({id:'0',text:'根结点'})
});
tree.expandAll();
}
);
文件二，branchTreeJSON.jsp （接收getBranch.do请求，返回无限级JSON字符串）
<% // 读取银行分支机构的层次数据 List result = DataAccess.getBankInfoList(); // 将层次数据转换为多叉树对象（本文下面会详细介绍该数据结构的实现方法） Node root = ExtTreeHelper.createExtTree(result); %> [ <%=root.toString()%> <!-- 以JSON的形式返回响应数据，Ext.tree.TreeLoader会根据此数据生成树形菜单 --> ]
以上两个程序文件是一次性生成无限级树形菜单所必须的，其中最为关键的部分就是如何生成一个无限级的JSON字符串，返回给客户端的Ext树形控件。对于银行分支机构来说，需要返回类似如下的JSON串：
{
id: '100000',
text: '廊坊银行总行',
children: [
{
id: '110000',
text: '廊坊分行',
children: [
{
id: '113000',
text: '廊坊银行开发区支行',
leaf: true
},
{
id: '112000',
text: '廊坊银行解放道支行',
children: [
{
id: '112200',
text: '廊坊银行三大街支行',
leaf: true
},
{
id: '112100',
text: '廊坊银行广阳道支行',
leaf: true
}
]
},
{
id: '111000',
text: '廊坊银行金光道支行',
leaf: true
}
]
}
]
}
同时还可能需要对树中每一个层次的节点按照某一属性（比如分支机构编号）进行排序，以展示出有序的树形菜单。
现在可以把问题概括为： 1、 把数据库中的层次数据转换成JSON格式的字符串 2、 对树中每一个层次的节点按照某一属性（比如分支机构编号）进行排序
下面介绍解决问题的思路： 在数据结构这门课中，我们都学过树，无限级树形菜单就可以抽象成一种多叉树结构，即每个节点下包含多个子节点的树形结构，首先就需要把数据库中的层次数据转换成多叉树结构的对象树，也就是构造出一棵多叉树。
概括起来分为三步：
如图所示：
三、源代码实现（Java语言版）
package test;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Collections;
/**
* 多叉树类
*/
public class MultipleTree {
public static void main(String[] args) {
// 读取层次数据结果集列表
List dataList = VirtualDataGenerator.getVirtualResult();
// 节点列表（散列表，用于临时存储节点对象）
HashMap nodeList = new HashMap();
// 根节点
Node root = null;
// 根据结果集构造节点列表（存入散列表）
for (Iterator it = dataList.iterator(); it.hasNext();) {
Map dataRecord = (Map) it.next();
Node node = new Node();
node.id = (String) dataRecord.get("id");
node.text = (String) dataRecord.get("text");
node.parentId = (String) dataRecord.get("parentId");
nodeList.put(node.id, node);
}
// 构造无序的多叉树
Set entrySet = nodeList.entrySet();
for (Iterator it = entrySet.iterator(); it.hasNext();) {
Node node = (Node) ((Map.Entry) it.next()).getValue();
if (node.parentId == null || node.parentId.equals("")) {
root = node;
} else {
((Node) nodeList.get(node.parentId)).addChild(node);
}
}
// 输出无序的树形菜单的JSON字符串
System.out.println(root.toString());
// 对多叉树进行横向排序
root.sortChildren();
// 输出有序的树形菜单的JSON字符串
System.out.println(root.toString());
// 程序输出结果如下（无序的树形菜单）（格式化后的结果）：
// {
// id : '100000',
// text : '廊坊银行总行',
// children : [
// {
// id : '110000',
// text : '廊坊分行',
// children : [
// {
// id : '113000',
// text : '廊坊银行开发区支行',
// leaf : true
// },
// {
// id : '111000',
// text : '廊坊银行金光道支行',
// leaf : true
// },
// {
// id : '112000',
// text : '廊坊银行解放道支行',
// children : [
// {
// id : '112200',
// text : '廊坊银行三大街支行',
// leaf : true
// },
// {
// id : '112100',
// text : '廊坊银行广阳道支行',
// leaf : true
// }
// ]
// }
// ]
// }
// ]
// }
// 程序输出结果如下（有序的树形菜单）（格式化后的结果）：
// {
// id : '100000',
// text : '廊坊银行总行',
// children : [
// {
// id : '110000',
// text : '廊坊分行',
// children : [
// {
// id : '111000',
// text : '廊坊银行金光道支行',
// leaf : true
// },
// {
// id : '112000',
// text : '廊坊银行解放道支行',
// children : [
// {
// id : '112100',
// text : '廊坊银行广阳道支行',
// leaf : true
// },
// {
// id : '112200',
// text : '廊坊银行三大街支行',
// leaf : true
// }
// ]
// },
// {
// id : '113000',
// text : '廊坊银行开发区支行',
// leaf : true
// }
// ]
// }
// ]
// }
}
}
/**
* 节点类
*/
class Node {
/**
* 节点编号
*/
public String id;
/**
* 节点内容
*/
public String text;
/**
* 父节点编号
*/
public String parentId;
/**
* 孩子节点列表
*/
private Children children = new Children();
// 先序遍历，拼接JSON字符串
public String toString() {
String result = "{"
+ "id : '" + id + "'"
+ ", text : '" + text + "'";
if (children != null && children.getSize() != 0) {
result += ", children : " + children.toString();
} else {
result += ", leaf : true";
}
return result + "}";
}
// 兄弟节点横向排序
public void sortChildren() {
if (children != null && children.getSize() != 0) {
children.sortChildren();
}
}
// 添加孩子节点
public void addChild(Node node) {
this.children.addChild(node);
}
}
/**
* 孩子列表类
*/
class Children {
private List list = new ArrayList();
public int getSize() {
return list.size();
}
public void addChild(Node node) {
list.add(node);
}
// 拼接孩子节点的JSON字符串
public String toString() {
String result = "[";
for (Iterator it = list.iterator(); it.hasNext();) {
result += ((Node) it.next()).toString();
result += ",";
}
result = result.substring(0, result.length() - 1);
result += "]";
return result;
}
// 孩子节点排序
public void sortChildren() {
// 对本层节点进行排序
// 可根据不同的排序属性，传入不同的比较器，这里传入ID比较器
Collections.sort(list, new NodeIDComparator());
// 对每个节点的下一层节点进行排序
for (Iterator it = list.iterator(); it.hasNext();) {
((Node) it.next()).sortChildren();
}
}
}
/**
* 节点比较器
*/
class NodeIDComparator implements Comparator {
// 按照节点编号比较
public int compare(Object o1, Object o2) {
int j1 = Integer.parseInt(((Node)o1).id);
int j2 = Integer.parseInt(((Node)o2).id);
return (j1 < j2 ? -1 : (j1 == j2 ? 0 : 1));
}
}
/**
* 构造虚拟的层次数据
*/
class VirtualDataGenerator {
// 构造无序的结果集列表，实际应用中，该数据应该从数据库中查询获得；
public static List getVirtualResult() {
List dataList = new ArrayList();
HashMap dataRecord1 = new HashMap();
dataRecord1.put("id", "112000");
dataRecord1.put("text", "廊坊银行解放道支行");
dataRecord1.put("parentId", "110000");
HashMap dataRecord2 = new HashMap();
dataRecord2.put("id", "112200");
dataRecord2.put("text", "廊坊银行三大街支行");
dataRecord2.put("parentId", "112000");
HashMap dataRecord3 = new HashMap();
dataRecord3.put("id", "112100");
dataRecord3.put("text", "廊坊银行广阳道支行");
dataRecord3.put("parentId", "112000");
HashMap dataRecord4 = new HashMap();
dataRecord4.put("id", "113000");
dataRecord4.put("text", "廊坊银行开发区支行");
dataRecord4.put("parentId", "110000");
HashMap dataRecord5 = new HashMap();
dataRecord5.put("id", "100000");
dataRecord5.put("text", "廊坊银行总行");
dataRecord5.put("parentId", "");
HashMap dataRecord6 = new HashMap();
dataRecord6.put("id", "110000");
dataRecord6.put("text", "廊坊分行");
dataRecord6.put("parentId", "100000");
HashMap dataRecord7 = new HashMap();
dataRecord7.put("id", "111000");
dataRecord7.put("text", "廊坊银行金光道支行");
dataRecord7.put("parentId", "110000");
dataList.add(dataRecord1);
dataList.add(dataRecord2);
dataList.add(dataRecord3);
dataList.add(dataRecord4);
dataList.add(dataRecord5);
dataList.add(dataRecord6);
dataList.add(dataRecord7);
return dataList;
}
}
好了，通过上面的代码，就可以实现多叉树的兄弟节点横向排序和先序遍历了，实现了将层次数据转换为有序无限级JSON字符串的目的。
在实际的项目中，可以把上面的有效代码融入其中，或者在此基础上进行一些扩展： 1、 实现对指定层次的排序（例如只排序第一层的节点，或者只排序某一父节点下的所有子节点）
四、思考与总结
既然可以构造无限级的JSON字符串，那么也可以根据这个思路构造无限级的XML字符串，或者构造具有层次结构的UL – LI组合（用UL - LI来展示树形结构），或者构造具有层次结构的TABLE（用TABLE来展示树形结构）。如下所示：
（1）XML层次结构 <menuGroup id="100000" name="廊坊银行总行">
<menuGroup id="110000" name="廊坊分行">
<menu id="113000" name="廊坊银行开发区支行">
</menu>
<menu id="111000" name="廊坊银行金光道支行">
</menu>
<menuGroup id="112000" name="廊坊银行解放道支行">
<menu id="112200" name="廊坊银行三大街支行">
</menu>
<menu id="112100" name="廊坊银行广阳道支行">
</menu>
</menuGroup>
</menuGroup>
</menuGroup>
（2）UL - LI 层次结构
<ul>
<li>廊坊银行总行</li>
<ul>
<li>廊坊分行</li>
<ul>
<li>廊坊银行开发区支行</li>
<li>廊坊银行解放道支行</li>
<ul>
<li>廊坊银行三大街支行</li>
<li>廊坊银行广阳道支行</li>
</ul>
<li>廊坊银行金光道支行</li>
</ul>
</ul>
</ul>
（3）TABLE层次结构
<table> <tr><td>廊坊银行总行</td></tr> <tr><td> 廊坊分行</td></tr> <tr><td> 廊坊银行开发区支行</td></tr> <tr><td> 廊坊银行解放道支行</td></tr> <tr><td> 廊坊银行三大街支行</td></tr> <tr><td> 廊坊银行广阳道支行</td></tr> <tr><td> 廊坊银行金光道支行</td></tr> </table>
另外对TreeGrid树形表格也有一定的价值： 1、 一次性构造树形表格，实现数据分级展示 2、 通过更换比较器，实现对不同表格列的全排序（全排序指的是对所有页的数据进行排序，而不是只对当前页的数据排序） 3、 实现对树形表格的完整分页（每次分页时，只取固定数目的第一层节点，之后调用toString方法，展示出完 整条数的分级数据）
五、参考书籍 2、Bruce Eckel，Thinking In Java Third Edition 3、David Flanagan，JavaScript: The Definitive Guide, 5th Edition 4、OCA Oracle Database 11g SQL Fundamentals I Exam Guide
六、联系方式
* 注：在另一篇文章《多叉树结合JavaScript树形控件实现无限级树形菜单（一种构建多级有序树形结构JSON（或XML）数据源的方法）》中，对代码进行了优化，去掉了Children类， 链接见： http://www.iteye.com/topic/1122125
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2012-02-02
很强大啊
|
| 返回顶楼 | |
|
发表时间：2012-02-03
这么认真的技术性帖子，很难得了。
|
| 返回顶楼 | |
|
发表时间：2012-02-07
虽说我不用ext js 但是楼主很认真
|
| 返回顶楼 | |
|
发表时间：2012-02-14
欣赏LZ得认真， 提个小意见如果文章出现自创词汇(双历树)最好在第一次出现这个词汇时就给出解释。
|
| 返回顶楼 | |
|
发表时间：2012-02-23
好文章赞一个，不知结合ztree的效果会如何呢！
|
| 返回顶楼 | |
|
发表时间：2012-03-13
最后修改：2012-07-25
我一共写了三篇文章（目的很简单：不想让肉烂在锅里）： 1、《利用多叉树实现Ext JS中的无限级树形菜单（一种构建多级有序树形结构JSON的方法》 2、《（原创）新概念智能树形菜单--利用加权多叉树结合JavaScript树形控件实现》 3、《（原创）统计分析系统中的树形结构统计报表--利用加权多叉树实现 》
后来又把第一篇文章做了扩展，题目叫《多叉树结合JavaScript树形控件实现无限级树形菜单（一种构建多级有序树形结构JSON（或XML）数据源的方法）》，链接是http://www.iteye.com/topic/1122125，对代码进行了优化（去掉了Children类），发在了JQuery板块以及百度文库上（http://wenku.baidu.com/view/ce101955ad02de80d4d84065.html）
这三篇文章的思路是层层推进、逐步深入的，第一篇发在Ext板块，第二、三篇发在Java综合板块， 欢迎依次阅读，希望能给您的工作带来帮助！
文中提到的4本参考书很值得阅读，都是基础的技术书，这几本书是我写这篇文章的基础（由于多年不看，这几本书的内容我已经快忘了， 1、Mark Allen Weiss，数据结构与算法分析（Java语言描述）
2、Bruce Eckel，Thinking In Java Third Edition 3、David Flanagan，JavaScript: The Definitive Guide, 5th Edition 4、OCA Oracle Database 11g SQL Fundamentals I Exam Guide
各位同志，对这篇文章发表回复请到【java综合】板块，那里有一篇帖子，叫《【分享原创文章，推动技术创新】“多叉树”和“加权多叉树”在软件开发中的应用（讨论帖，欢迎各位IT人踊跃发表评论）》，专门集中讨论这个话题的，多谢了，链接是：http://www.iteye.com/topic/1124411
|
| 返回顶楼 | |
|
发表时间：2012-07-11
不知道 楼主是否还在关注您的这篇帖子和文章 最近想在android上利用树形结构做一些统计图形，正在研读您的文章 有什么问题再交流
|
| 返回顶楼 | |
|
发表时间：2012-07-11
seventhfox 写道 不知道 楼主是否还在关注您的这篇帖子和文章 最近想在android上利用树形结构做一些统计图形，正在研读您的文章 有什么问题再交流
欢迎通过邮箱交流：multipletree@163.com |
| 返回顶楼 | |
浏览 23278 次
）：