樹狀結構是應用極廣的一類資料結構。人類社會的宗族族譜、現代企業的組織形式都是樹;在電腦領域中,檔案系統的目錄管理、記憶體管理的頁表、資料庫的索引也都是樹。隨著網際網路的快速發展,樹狀結構在瀏覽器/伺服器(B/S)架構應用中的使用也越來越普遍。
目前網路上常見的樹狀結構大致分為靜態與動態兩種。靜態結構數量最多、實作簡單,但缺點是無法改變樹的結構與內容,反映不出節點資訊的變化;動態構造樹雖然可以動態新增、刪除、更新節點,但大多不能直接拖曳節點來改變樹的結構與節點次序,而且會反覆刷新整個頁面,維護起來很不方便。
本文提出一種以 Ajax(Asynchronous JavaScript and XML)為基礎的通用動態節點載入方案。實作採用 J2EE 多層架構,樹節點的描述資訊以資料庫儲存,再以 XML 呈現給 JavaScript 解析,支援無刷新地新增、刪除、更新節點,以及拖曳節點來改變樹的結構與次序。以下先簡介 Ajax,再說明技術實作,最後分析效率。
依 Ajax 概念最早提出者 Jesse James Garrett 的說法,Ajax 並不是新的語言或技術,而是幾項技術按特定方式組合、在協作中各司其職:
Ajax 的原理是在使用者與伺服器之間加一個中間層,讓使用者操作與伺服器回應變成非同步。並非所有請求都會送到伺服器——部分資料驗證與資料處理交給 Ajax 引擎自理,只有確定需要新資料時才由引擎代為送出請求。如此一來,就把部分伺服器負擔轉移到用戶端,善用用戶端閒置的運算能力,降低伺服器與頻寬的負擔。

圖 1 未使用 Ajax(a)與使用 Ajax(b)的 Web 應用比較
傳統的伺服器程式常採用 Model 1 開發模型,把業務邏輯、伺服器端處理流程與 HTML 集中在一起,適合快速開發。Model 1 在小規模專案時優勢明顯,但實作本質上是基於流程的:一組伺服器頁面對應一個流程,流程一改就得動到多處,不利於擴充與更新;而且業務邏輯與呈現邏輯混在同一頁,耦合緊密、無法模組化,程式碼難以重用。
Model 2 則是物件導向的 MVC 模式在 Web 開發中的應用:Model 表示業務邏輯,View 是呈現層頁面,Controller 負責流程控制。透過這種切分,應用邏輯、處理流程與顯示邏輯各自獨立,元件之間可以互動與重用。
本方案採用 J2EE 多層架構,並結合 Struts 框架,把呈現層、業務邏輯層與資料層劃分為不同模組。呈現層專注於樹的外觀顯示;業務邏輯層為伺服器端處理程式,負責樹的生成與變化,並全部模組化實作,不在頁面中嵌入伺服器程式以降低耦合;模型層則是資料的儲存與表示。
類似 Windows 檔案總管的資料夾模式,節點的圖片樣式如下:

表 1 樹節點的前導圖片樣式
每個節點的 DHTML 程式碼需要包含節點的位置、前導圖片、樣式,以及針對該節點的其他操作;為了顯示的連貫性,還需要一些前導圖片。
對於非葉子節點,圖片與節點資訊以一個 DIV 容器包住。DIV 是 DHTML 的基礎,可以透過腳本操作其屬性——例如設定 style 的 display 屬性來控制子節點的展開與隱藏。節點位置、前導圖片、樣式與其他操作都放進容器中:
<DIV id="mParentID">
<IMG align="center" border="0" onclick="nodeExpand('leafid')"
name="m1Tree" src="Tplus.gif">
<IMG align="center" border="0" name="m1Folder" src="folderClosed.gif">
計算機學院
</DIV>
葉子節點不需要容器,直接輸出即可。點擊節點前的「+」「-」圖片時,就透過 DIV 的 display 屬性控制子節點的展開與隱藏(none 為隱藏、block 為顯示):
if (expandChild.style.display == "none") {
// 目前為隱藏狀態,執行展開
this.Loading(parentObject); // 判斷該分支的資料是否已載入
expandChild.style.display = "block";
if (para2 == "last") parentObject.src = "Lminus.gif"; // 最後一個節點
else parentObject.src = "Tminus.gif";
expandFolder.src = "folderOpen.gif";
} else {
// 把目前節點的子節點全部隱藏
expandChild.style.display = "none";
if (para2 == "last") parentObject.src = "Lplus.gif";
else parentObject.src = "Tplus.gif";
expandFolder.src = "folderClosed.gif";
}
以資料庫為載體記錄節點變化,樹形表至少要有:節點編號(CLASSID)、節點描述(ClassName)、父節點編號(ParentId)。同時再引入類別代碼(ClassCode)、節點級別(ClassLevel)、是否為葉子節點(Terminated)等輔助欄位。

圖 2 樹形表結構示意
樹遍歷的時間複雜度是 O(n),但把樹資訊放進資料庫後,就不能用傳統方式遍歷,必須以 SQL 存取;而一次取得的資料量越大,消耗的資源越多、使用者等待越久。若把無序資料讀出來再在伺服器端排序,又多了負擔。因此最好的做法是直接從資料庫讀出「已排好序」的樹。
關鍵在於:字串排序依字典序進行。結合 SQL 的特性與樹結構的特點,我們讓類別代碼採用多級字串形式,例如 AAABBBCCC——從根節點開始,每往下一層就多一級,且子節點的代碼以父節點的代碼開頭,再接上本級代碼。同層節點依生成順序編號:代碼 AAA 的下一層為 AAAAAA、AAAAAB……;AAAAAB 的子節點則為 AAAAABAAA、AAAAABAAB……。每級編碼的寬度可視實際需求調整,例如 AAA~ZZZ 一級可容納 26³ 個節點,不夠用時再增加一個字元。
這個編碼方式讓 select * from tree_class order by classcode 一次就能取回完整的先序樹。
動態載入。如果一次取回完整的先序樹再組裝成 XML 交給 JavaScript 解析,資料量越大、用戶端延遲越嚴重。因此對大資料量的樹,改用動態載入:每次點擊「+」時先判斷該分支是否已載入,若未載入則透過 XMLHttpRequest 非同步送出請求,執行 select * from tree_class where parent = ? order by classcode 取得節點資料。
/* 判斷是否已載入資料,未載入則向伺服器載入 */
dhtmlTree.prototype.Loading = function(pObject) {
if (((pObject.XMLload == 0) && (this.XMLsource)) && (!this.XMLloading)) {
pObject.XMLload = 1;
this.loadXML(this.XMLsource + getUrlSymbol(this.XMLsource)
+ "id=" + escape(pObject.id));
}
};
dtmlXMLObject.prototype.loadXML = function(url) {
try {
this.xmlDoc = new XMLHttpRequest();
this.xmlDoc.open("GET", url, true); // true:非同步
this.xmlDoc.send(null);
} catch (e) {
this.xmlDoc = new ActiveXObject("Microsoft.XMLHTTP"); // IE
this.xmlDoc.open("GET", url, true);
this.xmlDoc.send(null);
}
return this.xmlDoc.responseXML;
};
每次只取同一個父節點的子節點序列,並封裝成 XML:
<tree id="0">
<leaf child="1" text="國防科技大學" id="1"
im0="leaf.gif" im1="folderOpen.gif" im2="folderClosed.gif" />
</tree>
交給 JavaScript 的 insertItem() 解析並組出 HTML 節點。其中 child 為 1 表示有子節點、0 表示沒有;im0 是無子節點時的圖示,im1 是展開時的圖示,im2 是收合時的圖示——因此圖示也可在組 XML 時自訂。
樹的構造。從資料庫回傳的是有序的先序樹,而 XML 本身就是完整的樹形文件,所以只要從根節點開始遍歷一次,就能把整棵樹生成出來:
/* 動態載入時的樹構造方法 */
dtmlXMLObject.prototype.constructTree = function() {
var node = this.XMLLoader.getXMLTopNode("tree");
var parentId = node.getAttribute("id");
for (var i = 0; i < node.childNodes.length; i++) {
if ((node.childNodes[i].nodeType == 1) &&
(node.childNodes[i].tagName == "leaf")) {
var name = node.childNodes[i].getAttribute("text");
// ……其餘屬性略……
var temp = dhtmlObject.a0Find(parentId); // 取得父節點物件
temp.XMLload = 1; // 標記為已載入
dhtmlObject.insertItem(parentId, cId, name, im0, im1, im2, chd);
dhtmlObject.addDragger = this; // 設定可拖曳的物件
}
}
};
樹的維護。刪除節點最簡單,一句 SQL 即可連同其後代一起刪除:
delete from tree_class where classcode like 'APREFIX%'
新增節點分為前插、後插與插入子節點三種情況:前兩種需要遞迴更新類別代碼,後者只需找出父節點下現有的最大類別代碼加一即可。而透過拖曳改變樹的結構時,只要把被拖曳節點的 parentId 更新為目標節點的 CLASSID:
update tree_class set parentId = <classidTo> where classid = <classidFrom>
樹的儲存一般有兩種形式:二維表與鏈表;遍歷方式則有深度優先與廣度優先兩種,時間複雜度都是 O(n)。用二維表儲存時,在記憶體中可透過陣列索引直接定位父節點與兄弟節點;資料庫中的節點定位同樣準確,但把節點讀進記憶體後,若無法用索引定位,就必須遍歷尋找,n 個節點中找一個是 O(n/2),而 n 個節點排序的複雜度將達到 O(n²/2)——這正是一般 B/S 模式樹結構效率低下的原因。
本方案採用字典序編碼,使資料庫取出的樹「已經排好序」,直接遍歷即可生成客戶端頁面,時間複雜度回到 O(n)。
本文討論了基於 Ajax 的動態樹形結構實作方案,支援無刷新地動態維護節點資訊,也支援拖曳節點來改變結構與次序;同時以資料庫儲存節點資訊,確保方案具備一定的通用性;再加上以 XML 描述節點,任何符合預定 XML 結構的資料都能透過這棵樹呈現。本方案已實際應用於某校的智慧化迎新系統與老百姓大藥房的資訊系統中。