北京交通大学北京交通大学 计算机系计算机系 硕士论文（硕士论文（ 2012 年）年）多叉树结合 JavaScript 树形控件实现无限级树形结构（一种构建多级有序树形结构 JSON（或 XML）数据源的方法）一、问题研究的背景和意义在 Web应用程序开发领域，基于 Ajax技术的 JavaScript树形控件已经被广泛使用，它用来在 Html页面上展现具有层次结构的数据项。目前市场上常见的 JavaScript框架及组件库中均包含自己的树形控件，例如 jQuery、Dojo、YUI、Ext JS 等，还有一些独立的树形控件，例如 dhtmlxTree等，这些树形控件完美的解决了层次数据的展示问题。展示离不开数据，树形控件主要利用 Ajax技术从服务器端获取数据源，数据源的格式主要包括JSON、XML 等，而这些层次数据一般都存储在数据库中。 “无限级树形结构” ，顾名思义，没有级别的限制，它的数据通常来自数据库中的无限级层次数据，这种数据的存储表通常包括 id和 parentId这两个字段，以此来表示数据之间的层次关系。现在问题来了，既然树形控件的数据源采用 JSON或 XML等格式的字符串来组织层次数据，而层次数据又存储在数据库的表中，那么如何建立起树形控件与层次数据之间的关系，换句话说，如何将数据库中的层次数据转换成对应的层次结构的 JSON或 XML格式的字符串，返回给客户端的JavaScript树形控件？这就是我们要解决的关键技术问题。本文将以目前市场上比较知名的 Ext JS框架为例，讲述实现无限级树形结构的方法，该方法同样适用于其它类似的JavaScript树形控件。Ext JS框架是富客户端开发中出类拔萃的框架之一。在 Ext的 UI控件中，树形控件无疑是最为常用的控件之一，它用来实现树形结构的视图。TreeNode 用来实现静态的树形结构，AsyncTreeNode 用来实现动态的异步加载树形结构，后者最为常用，它通过接收服务器端返回来的 JSON格式的数据，动态生成树形结构节点。动态生成树有两种思路：一种是一次性生成全部树节点，另一种是逐级加载树节点（利用 Ajax，每次点击节点时查询下一级节点） 。对于大数据量的树节点来说，逐级加载是比较合适的选择，但是对于小数据量的树节点来说，一次性生成全部节点应该是最为合理的方案。在实际应用开发中，一般不会遇到特别大数据量的场景，所以一次性生成全部树节点是我们重点研究的技术点，也就是本文要解决的关键技术问题。本文以基于 Ext JS的应用系统为例，讲述如何将数据库中的无限级层次数据一次性在界面中生成全部树节点（例如在界面中以树形方式一次性展示出银行所有分支机构的信息） ，同时对每一个层次的节点按照某一属性和规则排序，展示出有序的树形结构。解决一次性构造无限级树形结构的问题，可以拓展出更多的应用场景，例如树形结构表格 TreeGrid，一次性生成树形表格，对树形表格进行完整分页，对表格列进行全排序；或者可以利用本文的思路扩展出其他的更复杂的应用场景。先看两个图例，有个直观上的认识：图一，银行分支机构树形结构Jinchutou.com北京交通大学北京交通大学 计算机系计算机系 硕士论文（硕士论文（ 2012 年）年）图二，树形结构表格二、详细设计方案让我们先看两段代码片段：文件一，branchTree.html （Ext 树形控件页面）Ext.onReady(function()var tree = new Ext.tree.TreePanel(height: 300,width: 400,Jinchutou.com北京交通大学北京交通大学 计算机系计算机系 硕士论文（硕士论文（ 2012 年）年）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字符串）以上两个程序文件是一次性生成无限级树形结构所必须的，其中最为关键的部分就是如何生成一个无限级的树形结构 JSON字符串，返回给客户端的 Ext树形控件。对于银行分支机构来说，需要返回类似如下的 JSON串：id: 100000,text: 廊坊银行总行,children: id: 110000,text: 廊坊分行,children: Jinchutou.com北京交通大学北京交通大学 计算机系计算机系 硕士论文（硕士论文（ 2012 年）年）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、 对树中每一个层次的节点按照某一属性（比如分支机构编号）进行排序下面介绍解决问题的思路：在数据结构这门课中，我们都学过树，无限级树形结构就可以抽象成一种多叉树结构，即每个节点下包含多个子节点的树形结构，首先就需要把数据库中的层次数据转换成多叉树结构的对象树，也就是构造出一棵多叉树。有了数据结构，还要实现相应的算法，我们需要实现两种算法：Jinchutou.com北京交通大学北京交通大学 计算机系计算机系 硕士论文（硕士论文（ 2012 年）年）1、兄弟节点横向排序算法，对隶属于同一个父节点下面的所有直接子节点按照某一节点属性和规则进行排序，保持兄弟节点横向有序；2、先序遍历算法，递归打印出无限级 JSON字符串。概括起来分为三步：1、 构造无序的多叉树结构2、 实现兄弟节点横向排序方法3、 实现先序遍历方法，打印出 JSON字符串如图所示：Jinchutou.com北京交通大学北京交通大学 计算机系计算机系 硕士论文（硕士论文（ 2012 年）年）Jinchutou.com北京交通大学北京交通大学 计算机系计算机系 硕士论文（硕士论文（ 2012 年）年）三、源代码实现（Java 语言版）实现这样一颗树，需要设计两个类：树类（MultipleTree） 、节点类（Node） ；排序时还需要一个比较器类（NodeIDComparator） ；为了方便演示，还需要构造一些假的层次数据，因此还需要建一个构造假数据的类（VirtualDataGenerator） ，以下代码拷贝出来之后可直接运行测试：package tree;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();Jinchutou.com北京交通大学北京交通大学 计算机系计算机系 硕士论文（硕士论文（ 2012 年）年）if (node.parentId = null | node.parentId.equals() root = node; else (Node) nodeList.get(node.parentId).addChild(node);/ 输出无序的树形结构的 JSON 字符串System.out.println(root);/ 对多叉树进行横向排序root.sortChildren();/ 输出有序的树形结构的 JSON 字符串System.out.println(root);/ 程序输出结果如下:/ 无序的树形结构（格式化后的结果，可使用 JSON 格式化工具查看，例如 http:/jsonviewer.stack.hu/ 在线查看器） : / / 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/ ,Jinchutou.com北京交通大学北京交通大学 计算机