一纱扭、問題研究的背景和意義
在Web應(yīng)用程序開發(fā)領(lǐng)域，基于Ajax技術(shù)的JavaScript樹形組件已經(jīng)被廣泛使用，它用來在Html頁面上展現(xiàn)具有層次結(jié)構(gòu)的數(shù)據(jù)項(xiàng)。目前市場上常見的JavaScript框架及組件庫中均包含自己的樹形組件姐直，例如jQuery尼啡、Ext JS等习霹，還有一些獨(dú)立的樹形組件暇屋，例如dhtmlxTree等，這些樹形組件完美的解決了層次數(shù)據(jù)的展示問題攘轩。展示離不開數(shù)據(jù)叉存，樹形組件主要利用Ajax技術(shù)從服務(wù)器端獲取數(shù)據(jù)源，數(shù)據(jù)源的格式主要包括JSON度帮、XML等歼捏，而這些層次數(shù)據(jù)一般都存儲在數(shù)據(jù)庫中。“無限級樹形結(jié)構(gòu)”瞳秽，顧名思義瓣履，沒有級別的限制，它的數(shù)據(jù)通常來自數(shù)據(jù)庫中的無限級層次數(shù)據(jù)寂诱，這種數(shù)據(jù)的存儲表通常包括id和parentId這兩個字段拂苹，以此來表示數(shù)據(jù)之間的層次關(guān)系“财福現(xiàn)在問題來了痰洒，既然樹形組件的數(shù)據(jù)源采用JSON或XML等格式的字符串來組織層次數(shù)據(jù)，而層次數(shù)據(jù)又存儲在數(shù)據(jù)庫的表中浴韭，那么如何建立起樹形組件與層次數(shù)據(jù)之間的關(guān)系丘喻，換句話說，如何將數(shù)據(jù)庫中的層次數(shù)據(jù)轉(zhuǎn)換成對應(yīng)的層次結(jié)構(gòu)的JSON或XML格式的字符串念颈，返回給客戶端的JavaScript樹形組件泉粉？這就是我們要解決的關(guān)鍵技術(shù)問題。本文將以目前市場上比較知名的Ext JS框架為例榴芳，講述實(shí)現(xiàn)無限級樹形結(jié)構(gòu)的方法嗡靡，該方法同樣適用于其它類似的JavaScript樹形組件。
Ext JS框架是富客戶端開發(fā)中出類拔萃的框架之一窟感。在Ext的UI組件中讨彼，樹形組件無疑是最為常用的組件之一，它用來實(shí)現(xiàn)樹形結(jié)構(gòu)的視圖柿祈。TreeNode用來實(shí)現(xiàn)靜態(tài)的樹形結(jié)構(gòu)哈误，AsyncTreeNode用來實(shí)現(xiàn)動態(tài)的異步加載樹形結(jié)構(gòu)，后者最為常用躏嚎，它通過接收服務(wù)器端返回來的JSON格式的數(shù)據(jù)蜜自，動態(tài)生成樹形結(jié)構(gòu)節(jié)點(diǎn)。動態(tài)生成樹有兩種思路：一種是一次性生成全部樹節(jié)點(diǎn)卢佣，另一種是逐級加載樹節(jié)點(diǎn)（利用Ajax重荠，每次點(diǎn)擊節(jié)點(diǎn)時查詢下一級節(jié)點(diǎn)）。對于大數(shù)據(jù)量的樹節(jié)點(diǎn)來說虚茶，逐級加載是比較合適的選擇晚缩，但是對于小數(shù)據(jù)量的樹節(jié)點(diǎn)來說，一次性生成全部節(jié)點(diǎn)應(yīng)該是最為合理的方案媳危。在實(shí)際應(yīng)用開發(fā)中荞彼，一般不會遇到特別大數(shù)據(jù)量的場景，所以一次性生成全部樹節(jié)點(diǎn)是我們重點(diǎn)研究的技術(shù)點(diǎn)待笑，也就是本文要解決的關(guān)鍵技術(shù)問題鸣皂。本文以基于Ext JS的應(yīng)用系統(tǒng)為例，講述如何將數(shù)據(jù)庫中的無限級層次數(shù)據(jù)一次性在界面中生成全部樹節(jié)點(diǎn)（例如在界面中以樹形方式一次性展示出銀行所有分支機(jī)構(gòu)的信息），同時對每一個層次的節(jié)點(diǎn)按照某一屬性和規(guī)則排序寞缝，展示出有序的樹形結(jié)構(gòu)癌压。
解決一次性構(gòu)造無限級樹形結(jié)構(gòu)的問題，可以拓展出更多的應(yīng)用場景荆陆，例如樹形結(jié)構(gòu)表格TreeGrid滩届，一次性生成樹形表格，對樹形表格進(jìn)行完整分頁被啼，對表格列進(jìn)行全排序帜消；或者可以利用本文的思路擴(kuò)展出其他的更復(fù)雜的應(yīng)用場景。
先看兩個圖例浓体，有個直觀上的認(rèn)識：
圖一泡挺，銀行分支機(jī)構(gòu)樹形結(jié)構(gòu)
圖二，樹形結(jié)構(gòu)表格
二命浴、詳細(xì)設(shè)計方案
讓我們先看兩段代碼片段：
文件一娄猫，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請求服務(wù)器返回多級樹形結(jié)構(gòu)的JSON字符串
? ? ? loader: new Ext.tree.TreeLoader({dataUrl:'getBranch.do'}),
? ? ? root : new Ext.tree.AsyncTreeNode({id:'0',text:'根結(jié)點(diǎn)'})?
? ? ? });? ? ?
? ? ? tree.expandAll();
? }
);
文件二，branchTreeJSON.jsp （接收getBranch.do請求生闲，返回多級樹形結(jié)構(gòu)的JSON字符串）
<%
// 讀取銀行分支機(jī)構(gòu)的層次數(shù)據(jù)
List result = DataAccess.getBankInfoList();
// 將層次數(shù)據(jù)轉(zhuǎn)換為多叉樹對象（本文下面會詳細(xì)介紹該數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方法）
Node root = ExtTreeHelper.createExtTree(result);
%>? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
[
<%=root.toString()%> <!-- 以JSON的形式返回響應(yīng)數(shù)據(jù)媳溺，Ext.tree.TreeLoader會根據(jù)此數(shù)據(jù)生成樹形結(jié)構(gòu) -->
]
以上兩個程序文件是一次性生成無限級樹形結(jié)構(gòu)所必須的，其中最為關(guān)鍵的部分就是如何生成一個無限級的樹形結(jié)構(gòu)JSON字符串碍讯，返回給客戶端的Ext樹形組件悬蔽。對于銀行分支機(jī)構(gòu)來說，需要返回類似如下的JSON串：
{
? id: '100000',
? text: '廊坊銀行總行',
? children: [
? ? {
? ? ? id: '110000',
? ? ? text: '廊坊分行',
? ? ? children: [
? ? ? ? {
? ? ? ? ? id: '113000',
? ? ? ? ? text: '廊坊銀行開發(fā)區(qū)支行',
? ? ? ? ? leaf: true
? ? ? ? },
? ? ? ? {
? ? ? ? ? id: '112000',
? ? ? ? ? text: '廊坊銀行解放道支行',
? ? ? ? ? children: [
? ? ? ? ? ? {
? ? ? ? ? ? ? id: '112200',
? ? ? ? ? ? ? text: '廊坊銀行三大街支行',
? ? ? ? ? ? ? leaf: true
? ? ? ? ? ? },
? ? ? ? ? ? {
? ? ? ? ? ? ? id: '112100',
? ? ? ? ? ? ? text: '廊坊銀行廣陽道支行',
? ? ? ? ? ? ? leaf: true
? ? ? ? ? ? }
? ? ? ? ? ]
? ? ? ? },
? ? ? ? {
? ? ? ? ? id: '111000',
? ? ? ? ? text: '廊坊銀行金光道支行',
? ? ? ? ? leaf: true
? ? ? ? }
? ? ? ]
? ? }
? ]
}
同時還需要對樹中每一個層次的節(jié)點(diǎn)按照某一屬性（比如分支機(jī)構(gòu)編號）進(jìn)行排序冲茸，以展示出有序的樹形結(jié)構(gòu)屯阀。
現(xiàn)在可以把問題概括為：
1、 把數(shù)據(jù)庫中的層次數(shù)據(jù)轉(zhuǎn)換成多級樹形結(jié)構(gòu)的JSON格式的字符串
2轴术、 對樹中每一個層次的節(jié)點(diǎn)按照某一屬性（比如分支機(jī)構(gòu)編號）進(jìn)行排序
下面介紹解決問題的思路：
在數(shù)據(jù)結(jié)構(gòu)這門課中难衰，我們都學(xué)過樹，無限級樹形結(jié)構(gòu)就可以抽象成一種多叉樹結(jié)構(gòu)逗栽，即每個節(jié)點(diǎn)下包含多個子節(jié)點(diǎn)的樹形結(jié)構(gòu)盖袭，首先就需要把數(shù)據(jù)庫中的層次數(shù)據(jù)轉(zhuǎn)換成多叉樹結(jié)構(gòu)的對象樹，也就是構(gòu)造出一棵多叉樹彼宠。
有了數(shù)據(jù)結(jié)構(gòu)鳄虱，還要實(shí)現(xiàn)相應(yīng)的算法，我們需要實(shí)現(xiàn)兩種算法：
1凭峡、兄弟節(jié)點(diǎn)橫向排序算法拙已，對隸屬于同一個父節(jié)點(diǎn)下面的所有直接子節(jié)點(diǎn)按照某一節(jié)點(diǎn)屬性和規(guī)則進(jìn)行排序，保持兄弟節(jié)點(diǎn)橫向有序摧冀；
2倍踪、先序遍歷算法系宫，遞歸打印出無限級JSON字符串。
概括起來分為三步：
1建车、 構(gòu)造無序的多叉樹結(jié)構(gòu)
2扩借、 實(shí)現(xiàn)兄弟節(jié)點(diǎn)橫向排序方法
3、 實(shí)現(xiàn)先序遍歷方法缤至，打印出JSON字符串
如圖所示：
三潮罪、源代碼實(shí)現(xiàn)（Java版）
實(shí)現(xiàn)這樣一顆樹，需要設(shè)計兩個類：樹類（MultiwayTree）领斥、節(jié)點(diǎn)類（Node）嫉到；排序時還需要一個比較器類（NodeIDComparator）；為了方便演示戒突，還需要構(gòu)造一些假的層次數(shù)據(jù)屯碴，因此還需要建一個構(gòu)造假數(shù)據(jù)的類（VirtualDataGenerator）描睦，以下代碼拷貝出來之后可直接運(yùn)行測試：
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 MultiwayTree {
public static void main(String[] args) {
// 讀取層次數(shù)據(jù)結(jié)果集列表
List dataList = VirtualDataGenerator.getVirtualResult();
// 節(jié)點(diǎn)映射表膊存，用于臨時存儲節(jié)點(diǎn)對象
HashMap nodeMap = new HashMap();
// 根節(jié)點(diǎn)
Node root = null;
// 將結(jié)果集存入映射表（后面將借助映射表構(gòu)造多叉樹）
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");
nodeMap.put(node.id, node);
}
// 構(gòu)造無序的多叉樹
Set entrySet = nodeMap.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) nodeMap.get(node.parentId)).addChild(node);
}
}
// 輸出無序的樹形結(jié)構(gòu)的JSON字符串
System.out.println(root);
// 對多叉樹進(jìn)行橫向排序
root.sortChildren();
// 輸出有序的樹形結(jié)構(gòu)的JSON字符串
System.out.println(root);
// 程序輸出結(jié)果如下:
//
// 無序的樹形結(jié)構(gòu)（格式化后的結(jié)果，可使用JSON格式化工具查看忱叭，例如? http://jsonviewer.stack.hu/ 在線查看器）:?
//? {
//? id : '100000',
//? text : '廊坊銀行總行',
//? children : [
//? ? {
//? ? id : '110000',
//? ? text : '廊坊分行',
//? ? children : [
//? ? ? {
//? ? ? id : '113000',
//? ? ? text : '廊坊銀行開發(fā)區(qū)支行',
//? ? ? leaf : true
//? ? ? },
//? ? ? {
//? ? ? id : '111000',
//? ? ? text : '廊坊銀行金光道支行',
//? ? ? leaf : true
//? ? ? },
//? ? ? {
//? ? ? id : '112000',
//? ? ? text : '廊坊銀行解放道支行',
//? ? ? children : [
//? ? ? ? {
//? ? ? ? id : '112200',
//? ? ? ? text : '廊坊銀行三大街支行',
//? ? ? ? leaf : true
//? ? ? ? },
//? ? ? ? {
//? ? ? ? id : '112100',
//? ? ? ? text : '廊坊銀行廣陽道支行',
//? ? ? ? leaf : true
//? ? ? ? }
//? ? ? ]
//? ? ? }
//? ? ]
//? ? }
//? ]
//? }
// 有序的樹形結(jié)構(gòu)（格式化后的結(jié)果）：
//? {
//? 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 : '廊坊銀行開發(fā)區(qū)支行',
//? ? ? leaf : true
//? ? ? }
//? ? ]
//? ? }
//? ]
//? }?
}
}
/**
* 節(jié)點(diǎn)類
*/
class Node {
/**
* 節(jié)點(diǎn)編號
*/
public String id;
/**
* 節(jié)點(diǎn)內(nèi)容
*/
public String text;
/**
* 父節(jié)點(diǎn)編號
*/
public String parentId;
/**
* 孩子節(jié)點(diǎn)列表
*/
private List children = new ArrayList();
// 添加孩子節(jié)點(diǎn)
public void addChild(Node node) {
children.add(node);
}
// 先序遍歷隔崎，拼接JSON字符串
public String toString() {
String result = "{" + "id : '" + id + "'" + ", text : '" + text + "'";
if (children.size() != 0) {
result += ", children : [";
for (int i = 0; i < children.size(); i++) {
result += ((Node) children.get(i)).toString() + ",";
}
result = result.substring(0, result.length() - 1);
result += "]";
} else {
result += ", leaf : true";
}
return result + "}";
}
// 兄弟節(jié)點(diǎn)橫向排序
public void sortChildren() {
if (children.size() != 0) {
// 對本層節(jié)點(diǎn)進(jìn)行排序（可根據(jù)不同的排序?qū)傩裕瑐魅氩煌谋容^器韵丑，這里 傳入ID比較器）
Collections.sort(children, new NodeIDComparator());
// 對每個節(jié)點(diǎn)的下一層節(jié)點(diǎn)進(jìn)行排序
for (int i = 0; i < children.size(); i++) {
((Node) children.get(i)).sortChildren();
}
}
}
}
/**
* 節(jié)點(diǎn)比較器
*/
class NodeIDComparator implements Comparator {
// 按照節(jié)點(diǎn)編號比較
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));
}
}
/**
* 構(gòu)造虛擬的層次數(shù)據(jù)
*/
class VirtualDataGenerator {
// 構(gòu)造無序的結(jié)果集列表爵卒，實(shí)際應(yīng)用中，該數(shù)據(jù)應(yīng)該從數(shù)據(jù)庫中查詢獲得撵彻；
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", "廊坊銀行開發(fā)區(qū)支行");
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;
}
}
好了钓株，通過上面的代碼，就可以實(shí)現(xiàn)多叉樹的兄弟節(jié)點(diǎn)橫向排序和先序遍歷了陌僵，實(shí)現(xiàn)了將層次數(shù)據(jù)轉(zhuǎn)換為有序無限級樹形結(jié)構(gòu)JSON字符串的目的轴合。
在實(shí)際的項(xiàng)目中，可以把上面的有效代碼融入其中碗短，或者在此基礎(chǔ)上進(jìn)行一些擴(kuò)展：
1受葛、 實(shí)現(xiàn)對指定層次的排序（例如只排序第一層的節(jié)點(diǎn)，或者只排序某一父節(jié)點(diǎn)下的所有子節(jié)點(diǎn)）
2偎谁、 遍歷輸出樹形結(jié)構(gòu)時可以加入判斷條件過濾掉某些節(jié)點(diǎn)
3总滩、 實(shí)現(xiàn)節(jié)點(diǎn)的刪除功能
4、 在節(jié)點(diǎn)類中增加一個父節(jié)點(diǎn)的引用巡雨，就可以計算出某一節(jié)點(diǎn)所處的級別
5闰渔、 在不支持層次查詢的數(shù)據(jù)庫應(yīng)用系統(tǒng)中使用該算法實(shí)現(xiàn)相同的效果
四、思考與總結(jié)
這篇文章的重點(diǎn)是如何構(gòu)造有序的無限級的樹形結(jié)構(gòu)JSON字符串铐望，一次性生成樹形結(jié)構(gòu)冈涧，而不是利用Ajax的方式向挖，反復(fù)向服務(wù)器端發(fā)送請求，一級接一級的加載樹節(jié)點(diǎn)炕舵。
既然可以構(gòu)造無限級的JSON字符串何之，那么也可以根據(jù)這個思路構(gòu)造無限級的XML字符串，或者構(gòu)造具有層次結(jié)構(gòu)的UL – LI組合（用UL - LI來展示樹形結(jié)構(gòu)）咽筋，或者構(gòu)造具有層次結(jié)構(gòu)的TABLE（用TABLE來展示樹形結(jié)構(gòu)）溶推。如下所示：
（1）XML層次結(jié)構(gòu)
<nodeGroup id="100000" name="廊坊銀行總行">
<nodeGroup id="110000" name="廊坊分行">
<node id="113000" name="廊坊銀行開發(fā)區(qū)支行">
</node>
<node id="111000" name="廊坊銀行金光道支行">
</node>
<nodeGroup id="112000" name="廊坊銀行解放道支行">
<node id="112200" name="廊坊銀行三大街支行">
</node>
<node id="112100" name="廊坊銀行廣陽道支行">
</node>
</nodeGroup>
</nodeGroup>
</nodeGroup>
（2）UL - LI 層次結(jié)構(gòu)
<ul>
<li>廊坊銀行總行</li>
<ul>
<li>廊坊分行</li>
<ul>
<li>廊坊銀行開發(fā)區(qū)支行</li>
<li>廊坊銀行解放道支行</li>
<ul>
<li>廊坊銀行三大街支行</li>
<li>廊坊銀行廣陽道支行</li>
</ul>
<li>廊坊銀行金光道支行</li>
</ul>
</ul>
</ul>
（3）TABLE層次結(jié)構(gòu)
<table>
<tr><td>廊坊銀行總行</td></tr>
<tr><td> 廊坊分行</td></tr>
<tr><td> 廊坊銀行開發(fā)區(qū)支行</td></tr>
<tr><td> 廊坊銀行解放道支行</td></tr>
<tr><td> 廊坊銀行三大街支行</td></tr>
<tr><td> 廊坊銀行廣陽道支行</td></tr>
<tr><td> 廊坊銀行金光道支行</td></tr>
</table>
另外對TreeGrid樹形表格也有一定的價值：
1、 一次性構(gòu)造樹形表格奸攻，實(shí)現(xiàn)數(shù)據(jù)分級展示
2蒜危、 通過更換比較器，實(shí)現(xiàn)對不同表格列的全排序（全排序指的是對所有頁的數(shù)據(jù)進(jìn)行排序睹耐，而不是只對當(dāng)前頁的數(shù)據(jù)排序辐赞；排序規(guī)則與Oracle數(shù)據(jù)庫中的層次查詢類似，即兄弟節(jié)點(diǎn)橫向排序）
3硝训、 實(shí)現(xiàn)對樹形表格的完整分頁（每次分頁時响委，只取固定數(shù)目的第一層節(jié)點(diǎn)，之后調(diào)用toString方法窖梁，展示出完整條數(shù)的分級數(shù)據(jù)赘风，即每頁的記錄條數(shù)是不固定的，但必須是完整的樹形結(jié)構(gòu)）
