基于内存多叉树的Ext JS无限级树形菜单实现方案

基于内存多叉树的Ext JS无限级树形菜单实现方案

（版权所有：北京宇信易诚科技有限公司网上银行事业部）

一、论文研究的背景和意义

目前在Web应用程序开发领域，Ext JS框架已经逐渐被广泛使用，它是富客户端开发中出类拔萃的框架之一。在Ext的UI控件中，树形控件无疑是最为常用的控件之一，它用来实现树形结构的菜单。TreeNode用来实现静态的树形菜单，AsyncTreeNode用来实现动态的异步加载树形菜单，后者最为常用，它通过接收服务器端返回来的JSON格式的数据，动态生成树形菜单节点。生成树有两种思路，一种是一次性生成全部树节点，另一种是异步加载树节点（branch-by-branch）。对于大数据量的菜单节点来说，异步加载是比较合适的选择，但是对于小数据量的菜单来说，一次性生成全部节点应该是最为合理的方案，在实际应用开发中，一般不会遇到特别大数据量的场景，所以一次性生成全部菜单节点是我们重点研究的技术点，本文就是介绍基于Ext JS的应用系统中如何将数据库中的无限级层次数据一次性在界面中生成全部菜单节点（例如在界面中以树形方式一次性展示出银行所有分支机构的信息）。

解决Ext JS无限级树形菜单的问题，可以拓展出更多的应用场景，例如BI（商业智能）系统中的报表分析中的数据钻取功能，也就是多级数据列表的展示；或者可以利用本文的思路扩展出其他的更复杂的应用场景。

二、详细设计方案

让我们先看一段代码片段：

文件一，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, loader: new Ext.tree.TreeLoader({dataUrl:'getBranch.do'}), // getBranch.do请求服务器返回无限级的JSON字符串

root : new Ext.tree.AsyncTreeNode({id:'0',text:'根结点'}) });

tree.expandAll();

} );

文件二，branchTreeJSON.jsp （接收getBranch.do请求，返回无限级JSON字符串） <%

// 读取银行分支机构的层次数据

List result = DataAccess.getResultList();

// 将层次数据转换为内存多叉树对象（本文下面会详细介绍该数据结构的实现方法） Node root = ExtTreeHelper.createExtTree(result); %> [

<%=root.toString()%> ]

以上两个程序文件是一次性生成无限级树形菜单所必须的，其中最为关键的部分就是如何生成一个无限级的JSON字符串，返回给客户端的Ext树形控件。对于银行分支机构来说，需要返回类似如下的JSON串： {

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 } ] } ] } ] }

同时还可能需要对树中每一个层次的节点按照某一属性（比如分支机构编号）进行排序，以展示出有序的树形菜单。

现在可以把问题概括为：

1、 把层次数据转换成JSON格式的字符串

2、 对树中每一个层次的节点按照某一属性（比如分支机构编号）进行排序

下面介绍解决问题的思路：

在数据结构这门课中，我们都学过二叉树和B树，二叉树属于内存数据结构，B树属于外存数据结构，我们的问题只涉及到内存操作，所以和B树无关，但是无限级树形菜单无法用二叉树来表示，因为每个节点下面都会有多个子节点，所以需要设计一种新的数据结构，用来表示这种多叉树结构，同时还要实现横向排序，即对隶属于同一个父节点下面的所有直接子节点按照某一节点属性和规则进行排序，保持兄弟节点横向有序。如图所示：

123456212231515261221222223

这棵树构造好之后，就可以通过纵向遍历（深度遍历）递归打印出无限级JSON字符串了。 为了区别它和B树（一种外存多叉树），可以称它为内存多叉树。

概括起来分为三步：

1、 构造无序的内存多叉树 2、 实现兄弟节点横向排序方法

3、 实现深度遍历方法，打印出JSON字符串

三、源代码实现（Java版）

实现这样一颗树，需要设计三个类：树类（ExtTree.java）、节点类（Node.java）、孩子列表类（Children.java）；为了方便演示，还需要构造一些假的层次数据，因此还需要建一个构造假数据的类（VirtualDataGenerator.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 ExtTree { 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(\ node.text = (String) dataRecord.get(\ node.parentId = (String) dataRecord.get(\ 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)).children.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; /**

* 孩子节点列表 */

public Children children = new Children();

// 深度遍历，拼接JSON字符串 public String toString() { String result = \ + \ + \ if (children != null && children.getSize() != 0) { result += \

} /**

} else { result += \ } return result + \}

// 对子节点进行横向排序 public void sortChildren() { if (children != null && children.getSize() != 0) { children.sortChildren(); } }

* 孩子列表类 */

class Children { public 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(\ dataRecord1.put(\廊坊银行解放道支行\ dataRecord1.put(\ HashMap dataRecord2 = new HashMap(); dataRecord2.put(\ dataRecord2.put(\廊坊银行三大街支行\ dataRecord2.put(\ HashMap dataRecord3 = new HashMap(); dataRecord3.put(\ dataRecord3.put(\廊坊银行广阳道支行\ dataRecord3.put(\

HashMap dataRecord4 = new HashMap(); dataRecord4.put(\

dataRecord4.put(\廊坊银行开发区支行\dataRecord4.put(\

HashMap dataRecord5 = new HashMap(); dataRecord5.put(\

dataRecord5.put(\廊坊银行总行\dataRecord5.put(\

HashMap dataRecord6 = new HashMap(); dataRecord6.put(\dataRecord6.put(\廊坊分行\dataRecord6.put(\

HashMap dataRecord7 = new HashMap(); dataRecord7.put(\

dataRecord7.put(\廊坊银行金光道支行\ dataRecord7.put(\ 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、数据结构与算法分析（Java语言描述） 2、Thinking In Java 3th Edition

3、JavaScript: The Definitive Guide, 5th Edition 4、OCA 11g SQL Fundamentals

本文来源：https://www.bwwdw.com/article/zug5.html