摘要:本文提出一種通用、可動態載入節點的樹形結構實作方案。方案以 Asynchronous JavaScript and XML(AJAX)為基礎,結合 Struts 框架,形成結構清晰、擴充性良好的多層架構;資料存放於資料庫,並以 XML 描述節點資訊,使得任何符合預定 XML 文件描述的資料,都能透過動態樹呈現。
關鍵詞:MVC 模式;AJAX;樹形結構;字典序
樹形結構是應用極廣的一類資料結構。人類社會的宗族族譜、現代企業的組織編制都是樹;在電腦領域,檔案系統的目錄管理、記憶體管理中的頁表、資料庫的索引,同樣都是樹。隨著網際網路的快速發展,樹形結構在瀏覽器/伺服器(B/S)應用系統中的使用也越來越普遍。
目前網路上常見的樹形結構大致分為靜態與動態兩種。靜態結構數量最多、實作簡單,但結構與內容無法變更,也就反映不出節點資訊的變化;動態構造樹雖然能動態新增、刪除、更新節點,實作相對複雜,多數卻不支援拖曳節點來改變樹形與節點順序,而且會反覆刷新整個頁面,給維護工作帶來不少困擾。本文提出的,正是一種基於 AJAX 的通用動態載入方案:採用 J2EE 多層架構,節點描述資訊以資料庫保存,並以 XML 呈現給 JavaScript 解析,支援無刷新地新增、刪除、更新節點,也能透過拖曳調整結構與順序。

圖 1 未使用 AJAX(a)與使用 AJAX(b)的 Web 應用比較
最早提出 AJAX 概念的 Jesse James Garrett 認為,AJAX 並不是一門新語言或新技術,而是多項既有技術按特定方式組合、在協作中各司其職:
AJAX 的工作原理,是在使用者與伺服器之間加入一個中間層,讓使用者操作與伺服器回應非同步化。並非所有請求都會被送往伺服器——資料驗證、資料處理等工作交給 AJAX 引擎自行消化,只有確定需要新資料時,才由引擎代為送出請求。如此一來,部分伺服器負擔被移轉到客戶端,利用客戶端闲置的運算能力處理,減輕伺服器與頻寬壓力,也節省了 ISP 的空間與頻寬租用成本。
傳統伺服器程式常採用 Model 1 開發模型,把業務邏輯、伺服器端處理流程與 HTML 集中在一起,開發速度快。Model 1 在小規模專案中優勢明顯,但本質上是基於流程的:一組伺服器頁面對應一段流程,流程一旦調整就得改多處,不利於擴充與更新;加上業務邏輯與顯示邏輯混在同一頁,耦合緊密、無法模組化,程式碼難以複用。
Model 2 則解決了這些問題。它是物件導向的 MVC 模式(Model-View-Controller)在 Web 開發中的應用:Model 承載業務邏輯,View 是表現層頁面,Controller 負責流程控制。透過這種切分,應用邏輯、處理流程與顯示邏輯被分配到不同元件與模組,彼此可互動、可重用。
本方案採用 J2EE 多層架構,並結合 Struts 框架把表現層、業務邏輯層與資料層拆解為獨立模組。表現層專注於樹的外觀呈現;業務邏輯層是伺服器端處理程式,負責樹的生成與變化,為降低耦合,該層完全模組化實作,不在表現頁面中嵌入伺服器程式;模型層則負責資料的儲存與表示。
節點的視覺樣式類似 Windows 檔案總管的資料夾模式。對每個節點而言,其 DHTML 程式碼需要包含節點位置、前導圖示、樣式,以及針對該節點的其他操作;為了讓整體顯示連貫,也需要一些輔助的前導圖示。

表 1 樹節點的前導圖示樣式
對於非葉子的節點,圖示與節點資訊都包在一個 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>
葉子節點則無需容器,直接輸出即可。點擊節點前的「+」「−」圖示時,透過容器 style 的 display 屬性來控制子節點的展開與隱藏:display 設為 "none" 隱藏、設為 "block" 顯示。核心 JavaScript 邏輯大致如下:
if (expandChild.style.display == "none") {
// 當前為隱藏狀態,執行展開動作
this.Loading(parentObject); // 判斷該分支資料是否已載入
expandChild.style.display = "block";
parentObject.src = (para2 == "last") ? "Lminus.gif" : "Tminus.gif";
expandFolder.src = "folderOpen.gif";
} else {
// 將當前節點的子節點全部隱藏
expandChild.style.display = "none";
parentObject.src = (para2 == "last") ? "Lplus.gif" : "Tplus.gif";
expandFolder.src = "folderClosed.gif";
}
我們以資料庫作為承載節點變化的媒介。樹形表結構至少需要三個欄位:節點編號(CLASSID)、節點描述(ClassName)、父節點編號(ParentId)——這些是建構樹結構的必要資訊。此外再引入節點類別碼(ClassCode)、節點層級(ClassLevel)、是否為葉子節點(Terminated)等輔助欄位,用來記錄節點順序。

圖 3 樹形表結構示意圖
樹遍歷的時間複雜度是 O(n),但把樹資訊放進資料庫後,就不能再用傳統方式遍歷,而必須以 SQL 存取資料表;一次取得的資料量越大,消耗的資源越多,使用者等待越久。若從資料庫讀出的是無序資料,伺服器端還得先排序再送到客戶端。因此,最好的做法是直接讓資料庫交出「已經排好序」的樹。
字串排序依字典序進行。結合 SQL 的特性與樹的結構特點,我們讓節點類別碼採用多層字串形式,例如 AAABBBCCC:從根節點開始,每往下一層就增加一層編碼,且子節點的類別碼必定以父節點的類別碼為開頭。同層節點則按生成順序編號——類別碼為 AAA 的節點,其子節點為 AAAAAA、AAAAAB……;AAAAAB 的子節點則為 AAAAABAAA、AAAAABAAB……。
每一層編碼的寬度可視實際應用調整,例如 AAA~ZZZ 一層就有 26³ 個節點,不夠用時再增加一個字元即可。這個看似簡單的編號方式帶來一個關鍵好處:執行 select * from tree_class order by classcode 之後,一次就能取得完整的先序樹。
動態載入技術。若一次抓出完整的先序樹再組裝成 XML 交給 JavaScript 解析,資料量越大,資源消耗與客戶端延遲就越嚴重。因此對大資料量的樹,我們改採動態載入:每次點擊「+」時先判斷子節點是否已載入,若未載入,才透過 AJAX 的 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:非同步;false:同步
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;
};
每次只取同一個 ParentId 底下的子節點序列,並封裝成 XML 格式的樹文件結構,例如:
<tree id="0">
<leaf child="1" name="國防科技大學" id="1"
im0="leaf.gif" im1="folderOpen.gif" im2="folderClosed.gif"/>
</tree>
這段 XML 交由 JavaScript 的 insertItem() 解析並組出 HTML 節點。其中 child 為 1 表示有子節點、0 表示沒有;im0 是無子節點時的圖示,im1 是有子節點且展開時的圖示,im2 則是收合時的圖示——因此圖示完全可以在組 XML 時自訂。
樹形結構的建構。資料庫返回的是有序先序樹,而 XML 本身就是完整的樹形文件,所以只要從根節點開始遍歷一次,就能把整棵樹生成完畢。實作上先取出 XML 的 tree 節點,逐一遍歷其 leaf 子節點,讀取名稱、圖示、是否有子節點等屬性,找到對應的父節點物件並標記為已載入,最後呼叫 insertItem() 輸出 HTML,同時設定可拖曳物件。
樹形結構的維護。刪除節點最簡單:delete from tree_class where classcode like 'classcode%',即可把節點與其所有後代一併移除。新增節點分為前插、後插與插入子節點三種情況:前兩種需要遞迴更新類別碼,後者只要找出父節點下現有子節點的最大類別碼加一即可。而透過拖曳改變樹形時,只需把被拖曳節點的 parentId 更新為目標節點的 ClassId,對應的 SQL 為 update tree_class set parentId = classidTo where classid = classidFrom。
樹的儲存一般有兩種形式:二維表與鏈表;遍歷方式則有深度優先與廣度優先兩種,時間複雜度都是 O(n)。用二維表儲存時,在記憶體中可透過陣列索引精準定位父節點與兄弟節點;資料庫中節點的定位同樣準確,但把節點資訊讀進記憶體後,若無法用陣列索引直接定位,就必須遍歷搜尋——在 n 個節點中找一個節點是 O(n²),而為 n 個節點排序的複雜度更會膨脹到 O(n²/2)。這正是一般 B/S 模式樹形結構效率低落的根本原因。
本方案採用字典序編號,讓資料庫交出的樹天生有序,直接遍歷即可產生客戶頁面程式,時間複雜度降回 O(n)。
本文討論了基於 AJAX 的動態樹形結構實作方案,支援無刷新地動態維護節點資訊,也支援拖曳節點來改變結構與順序;同時以資料庫儲存節點資訊,保證方案具備一定的通用性;再加上以 XML 描述節點,任何符合預定 XML 文件描述的資料都能用這棵樹呈現。該方案此前已實際應用於數字迎新系統與老百姓大藥房資訊系統之中。