利用內存多叉樹實現Ext JS中的無限級樹形菜單（一種構建多級有序樹形結構JSON的方法）
解決Ext JS無限級樹形菜單的問題，可以拓展出更多的應用場景，例如BI（商業智能）系統中的報表分析中的數據鉆取功能，也就是多級數據列表的展示，同時對多級數據列表按照某一列數據進行排序；或者可以利用本文的思路擴展出其他的更復雜的應用場景。 先看兩個圖例，有個直觀上的認識： 圖二，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.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 : '111000', text : '廊坊銀行金光道支行', leaf : true }, { id : '112000', text : '廊坊銀行解放道支行', children : [ { id : '112200', text : '廊坊銀行三大街支行', leaf : true }, { id : '112100', text : '廊坊銀行廣陽道支行', leaf : true } ] } ] } ] } 同時還可能需要對樹中每一個層次的節點按照某一屬性（比如分支機構編號）進行排序，以展示出有序的樹形菜單。 現在可以把問題概括為： 1、 把數據庫中的層次數據轉換成多級樹形結構的JSON格式的字符串 下面介紹解決問題的思路： 在數據結構這門課中，我們都學過二叉樹和B樹，二叉樹屬于內存數據結構，B樹屬于外存數據結構，我們的問題只涉及到內存操作，所以和B樹無關，但是無限級樹形菜單無法用二叉樹來表示，因為每個節點下面都會有多個子節點，所以需要設計一種新的數據結構，用來表示這種多叉樹結構，同時還要實現橫向排序，即對隸屬于同一個父節點下面的所有直接子節點按照某一節點屬性和規則進行排序，保持兄弟節點橫向有序。 1、 構造無序的內存多叉樹 2、 實現兄弟節點橫向排序方法 3、 實現深度遍歷方法，打印出JSON字符串 三、源代碼實現（Java語言版） 好了，通過上面的代碼，就可以實現內存多叉樹的兄弟節點橫向排序和深度遍歷了，實現了將層次數據轉換為有序無限級JSON字符串的目的。 在實際的項目中，可以把上面的有效代碼融入其中，或者在此基礎上進行一些擴展，比如能否實現對指定層次的排序（例如只排序第一層的節點，或者只排序某一父節點下的所有子節點）；實現節點的刪除功能；在節點類中增加一個父節點的引用，就可以計算出某一節點所處的級別；在沒有層次查詢（hierarical retrival）的數據庫應用系統中使用該算法實現相同的效果，等等。 既然可以構造無限級的JSON字符串，那么也可以根據這個思路構造無限級的XML字符串，或者構造具有層次結構的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）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> 同時對BI（商業智能）系統的報表分析也有一定的價值： 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 六、聯系方式
利用內存多叉樹（雙歷樹）實現Ext JS中的無限級樹形菜單（一種構建多級有序樹形結構JSON的方法）</span>
一、問題研究的背景和意義</span></span></strong></span></p>
目前在Web應用程序開發領域，Ext JS框架已經逐漸被廣泛使用，它是富客戶端開發中出類拔萃的框架之一。在Ext的UI控件中，樹形控件無疑是最為常用的控件之一，它用來實現樹形結構的菜單。TreeNode用來實現靜態的樹形菜單，AsyncTreeNode用來實現動態的異步加載樹形菜單，后者最為常用，它通過接收服務器端返回來的JSON格式的數據，動態生成樹形菜單節點。動態生成樹有兩種思路：一種是一次性生成全部樹節點，另一種是逐級加載樹節點（branch-by-branch）。對于大數據量的菜單節點來說，逐級加載是比較合適的選擇，但是對于小數據量的菜單來說，一次性生成全部節點應該是最為合理的方案。在實際應用開發中，一般不會遇到特別大數據量的場景，所以一次性生成全部菜單節點是我們重點研究的技術點，本文就是介紹基于Ext JS的應用系統中如何將數據庫中的無限級層次數據一次性在界面中生成全部菜單節點（例如在界面中以樹形方式一次性展示出銀行所有分支機構的信息），同時對每一個層次的菜單節點按照某一屬性和規則排序，展示出有序的菜單樹。
圖一，銀行分支機構樹形結構菜單
二、詳細設計方案
2、 對樹中每一個層次的節點按照某一屬性（比如分支機構編號）進行排序
這棵樹構造好之后，就可以通過深度優先遍歷遞歸打印出無限級JSON字符串了,為了區別它和B樹（一種外存多叉樹結構），可以稱它為內存多叉樹。
如圖所示：
概括起來分為三步：
由于這棵樹使用了廣度優先遍歷和深度優先遍歷，實現了樹的雙遍歷，所以可以簡稱它為
“雙歷樹”。
實現這樣一顆樹，需要設計三個類：樹類（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("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)).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 = "{"
+ "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();
}
}
}
/**
* 孩子列表類
*/
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("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字符串，一次性生成樹形菜單，而不是利用AJAX的方式，反復向服務器端發送請求，一級接一級的加載樹節點。
1、Mark Allen Weiss，數據結構與算法分析（Java語言描述）
memorymultitree@163.com
memorymultitree 
zhou__18 
碼頭工人 
gil_guo