摘 要:簡(jiǎn)要介紹了一種通用的，動(dòng)態(tài)樹型結(jié)構(gòu)的實(shí)現(xiàn)方案，該方案基于Asynchronous JavaScript and XML，結(jié)合Struts框架設(shè)計(jì)實(shí)現(xiàn)了結(jié)構(gòu)清晰、擴(kuò)展性良好的多層架構(gòu)，數(shù)據(jù)存儲(chǔ)于數(shù)據(jù)庫(kù)，結(jié)合XML描述樹的節(jié)點(diǎn)信息，使得任何按預(yù)定的XML文檔描述的信息都可以通過動(dòng)態(tài)樹來展現(xiàn)。
關(guān)鍵詞:MVC模式；Ajax；樹型結(jié)構(gòu)；字典序
樹型結(jié)構(gòu)是一類應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)。人類社會(huì)中宗族的族譜和現(xiàn)代企業(yè)的組織形式都是樹型結(jié)構(gòu)。在計(jì)算機(jī)領(lǐng)域中,文件系統(tǒng)中文件的管理結(jié)構(gòu)、存儲(chǔ)器管理中的頁(yè)表、數(shù)據(jù)庫(kù)中的索引等也都是樹型結(jié)構(gòu)。隨著Internet的飛速發(fā)展，樹型結(jié)構(gòu)在瀏覽器/服務(wù)器（Browser/Server，簡(jiǎn)稱B/S）應(yīng)用系統(tǒng)的應(yīng)用也越來越廣泛。
目前，在互聯(lián)網(wǎng)上廣泛存在、應(yīng)用的樹型結(jié)構(gòu)一般分為兩種：靜態(tài)和動(dòng)態(tài)結(jié)構(gòu)。靜態(tài)結(jié)構(gòu)存在最多、實(shí)現(xiàn)簡(jiǎn)單，但是靜態(tài)導(dǎo)致不能改變樹的結(jié)構(gòu)和內(nèi)容，無法反映樹的節(jié)點(diǎn)信息的變化；而實(shí)現(xiàn)相對(duì)復(fù)雜的動(dòng)態(tài)構(gòu)造樹，雖然可以動(dòng)態(tài)增加、刪除、更新節(jié)點(diǎn)信息，但是大部分不能直接拖放節(jié)點(diǎn)來改變樹的結(jié)構(gòu)以及節(jié)點(diǎn)間的次序，并且反復(fù)刷新整個(gè)頁(yè)面，給用戶維護(hù)帶來了許多不便。本文提出了一種基于Ajax（Asynchronous JavaScript and XML）通用的、動(dòng)態(tài)加載節(jié)點(diǎn)的解決方案。實(shí)現(xiàn)上采用J2EE多層架構(gòu)，樹節(jié)點(diǎn)的描述信息采用數(shù)據(jù)庫(kù)存儲(chǔ)，以可擴(kuò)展標(biāo)記語(yǔ)言（eXtensible Markup Language，簡(jiǎn)稱XML）展現(xiàn)給JavaScript解析，支持無刷新地增加、刪除、更新節(jié)點(diǎn)信息，以及拖放節(jié)點(diǎn)來改變樹的結(jié)構(gòu)和節(jié)點(diǎn)間的次序。文中第1部分簡(jiǎn)要介紹了Ajax技術(shù)；第2部分詳細(xì)介紹了該方案的技術(shù)實(shí)現(xiàn)過程；第3部分分析了該方案的效率。
1、Ajax簡(jiǎn)介
Ajax概念的最早提出者Jesse James Garrett認(rèn)為：Ajax并不是一門新的語(yǔ)言或技術(shù)，它實(shí)際上是幾項(xiàng)技術(shù)按一定的方式組合在共同的協(xié)作中發(fā)揮各自的作用，它包括：
·使用擴(kuò)展超媒體標(biāo)記語(yǔ)言（eXtended Hypertext Markup Language，簡(jiǎn)稱XHTML）和級(jí)聯(lián)樣式單（Cascading Style Sheet，簡(jiǎn)稱CSS）標(biāo)準(zhǔn)化呈現(xiàn)；
·使用文檔對(duì)象模型（Document Object Model，簡(jiǎn)稱DOM）實(shí)現(xiàn)動(dòng)態(tài)顯示和交互；
·使用可擴(kuò)展標(biāo)記語(yǔ)言（eXtensible Markup Language，簡(jiǎn)稱XML）和可擴(kuò)展樣式表轉(zhuǎn)換（eXtensible Stylesheet Language Transformation，簡(jiǎn)稱XSLT）進(jìn)行數(shù)據(jù)交換與處理；
·使用XMLHTTP組件XMLHttpRequest對(duì)象進(jìn)行異步數(shù)據(jù)讀??；
·最后用JavaScript綁定和處理所有數(shù)據(jù)。
Ajax的工作原理如圖1所示，它相當(dāng)于在用戶和服務(wù)器之間加了一個(gè)中間層，使用戶操作與服務(wù)器響應(yīng)異步化。并不是所有的用戶請(qǐng)求都提交給服務(wù)器，像—些數(shù)據(jù)驗(yàn)證和數(shù)據(jù)處理等都交給Ajax引擎處理，只有確定需要從服務(wù)器讀取新數(shù)據(jù)時(shí)再由Ajax引擎代為向服務(wù)器提交請(qǐng)求。這樣就把一些服務(wù)器負(fù)擔(dān)的工作轉(zhuǎn)嫁到客戶端，利用客戶端閑置的處理能力來處理，減輕服務(wù)器和帶寬的負(fù)擔(dān)，從而達(dá)到節(jié)約ISP的空間及帶寬租用成本的目的。
 圖 1 未使用Ajax（a）和使用Ajax（b）的web應(yīng)用比較 |
2、總體設(shè)計(jì)方案
傳統(tǒng)的服務(wù)器程序采用Model 1開發(fā)模型，通常將業(yè)務(wù)邏輯、服務(wù)器端處理過程和HTML代碼集中在一起表示，快速完成應(yīng)用開發(fā)。Model 1 在小規(guī)模應(yīng)用開發(fā)時(shí)優(yōu)勢(shì)明顯，但是應(yīng)用實(shí)現(xiàn)一般是基于過程的，一組服務(wù)器頁(yè)面實(shí)現(xiàn)一個(gè)流程，如果流程改動(dòng)將導(dǎo)致多個(gè)地方修改，非常不利于應(yīng)用的擴(kuò)展和更新。此外業(yè)務(wù)邏輯和表示邏輯混合在服務(wù)器頁(yè)面中，耦合緊密，無法模塊化，導(dǎo)致代碼無法復(fù)用。
Model 2則解決了這些問題，它是面向?qū)ο蟮腗VC模式（Model-View-Controller，模型-視圖-控制器）在Web開發(fā)中的應(yīng)用，Model表示應(yīng)用的業(yè)務(wù)邏輯，View是應(yīng)用的表示層頁(yè)面，Controller是提供應(yīng)用的處理過程控制。通過這種MVC設(shè)計(jì)模式把應(yīng)用邏輯，處理過程和顯示邏輯劃分成不同的組件、模塊實(shí)現(xiàn)，組件間可以進(jìn)行交互和重用。
本方案是采用J2EE的多層架構(gòu)，設(shè)計(jì)時(shí)結(jié)合Struts框架將表示層、業(yè)務(wù)邏輯層和數(shù)據(jù)層劃分成不同的模塊。表示層專注于樹的外觀顯示，業(yè)務(wù)邏輯層為服務(wù)器端處理程序，處理樹的生成、變化，為減少耦合性，該程序全部模塊化實(shí)現(xiàn)，不在表示頁(yè)面嵌入服務(wù)器程序；模型層是數(shù)據(jù)的存儲(chǔ)和表示。下面分別介紹各層實(shí)現(xiàn)。
2.1 表示層實(shí)現(xiàn)
類似Windows資源管理器的文件夾模式，節(jié)點(diǎn)的圖片樣式如表1所示。對(duì)于每個(gè)節(jié)點(diǎn)的DHTML 代碼，需要包含節(jié)點(diǎn)的位置、前導(dǎo)圖片、樣式、針對(duì)該節(jié)點(diǎn)的其他操作等。同時(shí)為了節(jié)點(diǎn)顯示的連貫性，還需一些前導(dǎo)圖片。
表1 樹節(jié)點(diǎn)的前的圖片樣式表
對(duì)于樹的非葉子節(jié)點(diǎn)，圖片和節(jié)點(diǎn)信息等，采用一個(gè)DIV ( division) 容器包含。DIV 等容器是DHTML 的基礎(chǔ)，使用它可以通過腳本程序?qū)ζ鋵傩赃M(jìn)行操作，如設(shè)置其style 樣式的display 屬性來控制子節(jié)點(diǎn)的展開和隱藏。節(jié)點(diǎn)的位置、前導(dǎo)圖片、樣式、針對(duì)該節(jié)點(diǎn)的其他的操作等都放入容器中，例：
＜ 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′＞ 計(jì)算機(jī)學(xué)院 ＜/DIV＞ |
葉子節(jié)點(diǎn)無需容器直接輸出即可。
當(dāng)點(diǎn)擊某節(jié)點(diǎn)前的“ + ”、“ - ”圖片時(shí)通過DIV 的style 樣式的display 屬性控制子節(jié)點(diǎn)的展開和隱藏。display：“none”(隱藏,不可見)，display：“block”(顯示) 。相關(guān)JavaScript 代碼如下：
if (expandChild.style.display = =″none″){
// 當(dāng)前為隱藏狀態(tài),執(zhí)行展開動(dòng)作
this.Loading(parentObject);//判斷該分支的數(shù)據(jù)是否已經(jīng)加載
expandChild.style.display =″block″;
if (para2 = =″last″)
parentObject.src =″Lminus. gif″; // 最后一個(gè)節(jié)點(diǎn)
else
parentObject.src = ″Tminus. gif″; // 顯示┠
expandFolder.src = ″folderOpen. gif″;
}else {
// 將當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)全部隱藏
expandChild.style.display = ″none″;
if (para2 = = ″last″)
parentObject.src = ″Lplus. gif″;
else
parentObject.src = ″Tplus. gif″;
expandFolder.src = ″folderClosed. gif″;
} |
2.2 樹型表結(jié)構(gòu)設(shè)計(jì)
我們以數(shù)據(jù)庫(kù)為載體記錄節(jié)點(diǎn)的變化，樹型表結(jié)構(gòu)至少要有以下字段：節(jié)點(diǎn)的編號(hào)(CLASSID) ,對(duì)節(jié)點(diǎn)的描述(ClassName)，父節(jié)點(diǎn)的編號(hào)(ParentId)，這些是構(gòu)建樹結(jié)構(gòu)所必須的信息。同時(shí)引入節(jié)點(diǎn)的類別代碼（ClassCode），節(jié)點(diǎn)的級(jí)別（ClassLevel），是否葉子節(jié)點(diǎn) (Terminated)等輔助字段，記錄節(jié)點(diǎn)次序，實(shí)體關(guān)系圖如圖3所示。
 圖 3 樹型表結(jié)構(gòu)示意圖 |
樹遍歷的時(shí)間復(fù)雜度是O( n )，但是將樹信息存放到數(shù)據(jù)庫(kù)后，就不能按傳統(tǒng)的方式遍歷樹，必須使用SQL 語(yǔ)句訪問數(shù)據(jù)庫(kù)表的內(nèi)容，而一次性取的數(shù)據(jù)量越多，消耗的資源也越多，用戶等待的時(shí)間就越長(zhǎng)。如果將無序的數(shù)據(jù)從數(shù)據(jù)庫(kù)中讀出，在服務(wù)器端，必須將排序后的樹送到客戶端顯示。因此，最好從數(shù)據(jù)庫(kù)讀出已排好序的樹。
我們知道，字符串排序是按照字典序形式。結(jié)合SQL 語(yǔ)句的特點(diǎn)和樹結(jié)構(gòu)特點(diǎn)，數(shù)據(jù)庫(kù)表中，節(jié)點(diǎn)的類別代碼采用多級(jí)字符串形式，如AAABBBCCC，從樹根節(jié)點(diǎn)開始，每向下一級(jí)字符串就增加一級(jí)，并且子節(jié)點(diǎn)類別代碼以父節(jié)點(diǎn)類別代碼開始，再開始本級(jí)的類別代碼。同級(jí)的節(jié)點(diǎn)按照生成的順序編號(hào)，如節(jié)點(diǎn)類別代碼為AAA 的下一級(jí)孩子類別代碼為AAAAAA，AAAAAB 等，AAAAAB 的孩子節(jié)點(diǎn)為AAAAABAAA、AAAAABAAB等。每一級(jí)編號(hào)字符的寬度與實(shí)際的應(yīng)用關(guān)聯(lián)，如AAA～ZZZ 一級(jí)則有263 個(gè)節(jié)點(diǎn)，如果不夠用再增加一個(gè)字符用于編碼。該巧妙的編號(hào)方式。使得在執(zhí)行SQL 語(yǔ)句select * from tree_class order by classcode 后，一次獲得完整的先序樹。
2.3 業(yè)務(wù)邏輯層設(shè)計(jì)
2.3.1 動(dòng)態(tài)加載技術(shù)
如果一次性獲取完整的先序樹，構(gòu)造成xml提供給JavaScript解析，數(shù)據(jù)量越大，消耗的資源越多，客戶端響應(yīng)延遲時(shí)間就越長(zhǎng)，因此對(duì)于大數(shù)據(jù)量的樹，采用動(dòng)態(tài)加載方式，即每次單擊“+”圖片時(shí)，判斷是否已加載子節(jié)點(diǎn)數(shù)據(jù)，如果未加載則通過Ajax的XMLHTTP組件XMLHTTPRequest對(duì)象異步發(fā)送請(qǐng)求，連接服務(wù)器執(zhí)行SQL 語(yǔ)句“select * from tree_class where parent = ？order by classcode ”獲取節(jié)點(diǎn)數(shù)據(jù)。相關(guān)JavaScript 代碼如下：
/*判斷是否已經(jīng)加載數(shù)據(jù)，未加載則訪問服務(wù)器加載數(shù)據(jù)*/
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){//加載數(shù)據(jù)
try {
this.xmlDoc = new XMLHttpRequest();
/*通過GET方法異步連接到 url 加載數(shù)據(jù)*/
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);//true：異步；false：同步
this.xmlDoc.send(null);
}
return this.xmlDoc.responseXML;
} |
每次只取同一個(gè)父節(jié)點(diǎn)ParentId的子節(jié)點(diǎn)序列，按XML格式封裝成樹的文檔結(jié)構(gòu)，例如：
＜tree id="0"＞
＜leaf child=”1" name="國(guó)防科技大學(xué)" id="1" im0="leaf.gif" im1="folderOpen.gif" im2=" folderClosed.gif"/＞
＜/tree＞ |
提供給JavaScript的dhtmlTreeObject.prototype.insertItem（）解析并組織好html輸出節(jié)點(diǎn)；其中child：1表示有子節(jié)點(diǎn)，0表示沒有子節(jié)點(diǎn)；im0表示沒有子節(jié)點(diǎn)時(shí)的圖標(biāo)；im1表示有子節(jié)點(diǎn)并且打開節(jié)點(diǎn)時(shí)的圖標(biāo)；im2表示有子節(jié)點(diǎn)并且關(guān)閉時(shí)的圖標(biāo)；所以還可以在構(gòu)造XML時(shí)自定義圖標(biāo)。
2.3.2 樹型結(jié)構(gòu)的構(gòu)造
從數(shù)據(jù)庫(kù)中返回的是有序的先序樹，而XML是完整的樹型結(jié)構(gòu)文檔，所以將樹型數(shù)據(jù)構(gòu)造成預(yù)定義的XML格式，只需從根節(jié)點(diǎn)開始，遍歷一遍樹，即可將樹全部生成。相關(guān)JavaScript代碼如下：
/*動(dòng)態(tài)加載樹的構(gòu)造方法*/
dtmlXMLObject.prototype.constructTree=function(){
//采用動(dòng)態(tài)加載時(shí)獲取的xml數(shù)據(jù)，解析樹型數(shù)據(jù)
var node=this.XMLLoader.getXMLTopNode("tree");
var parentId=node.getAttribute("id");
for(var i=0;i＜node.childNodes.length;i++) { //逐個(gè)解析xml文件的leaf節(jié)點(diǎn)
if((node.childNodes[i].nodeType==1)&&(node.childNodes[i].tagName == "leaf")){
var name=node.childNodes[i].getAttribute("text");
…………
var temp=dhtmlObject.a0Find(parentId);//獲取父節(jié)點(diǎn)對(duì)象
temp.XMLload=1;//已加載
//構(gòu)造html輸出節(jié)點(diǎn)
dhtmlObject.insertItem(parentId,cId,name,im0,im1,im2,chd);
dhtmlObject.addDragger = this;//設(shè)置可拖放的對(duì)象
};
} |
2.3.3 樹型結(jié)構(gòu)的維護(hù)
在維護(hù)樹型結(jié)構(gòu)表時(shí),刪除節(jié)點(diǎn)較為簡(jiǎn)單，SQL 語(yǔ)句為: "delete from tree_class where classcode like′"+ classcode +"%′",即可將其節(jié)點(diǎn)和孩子一并刪除；增加節(jié)點(diǎn)時(shí),分為前插、后插、和插入子節(jié)點(diǎn)三種情況，前兩種情況需要更新遞歸更新類別代碼，后者只需找到父節(jié)點(diǎn)的孩子的最大類別代碼加1 后,作為增加節(jié)點(diǎn)的類別代碼；通過拖放來改變樹的結(jié)構(gòu)時(shí)，只需將拖動(dòng)節(jié)點(diǎn)的parentId更新為目標(biāo)節(jié)點(diǎn)的Classid即可，對(duì)應(yīng)的SQL語(yǔ)句為："update tree_class set parentId = "+ classidTo+" where classid = "+ classidFrom。
3、效率分析
對(duì)于樹的存儲(chǔ)一般有兩種形式：二維表和鏈表，遍歷方式一般也有深度遍歷和廣度遍歷兩種方式，遍歷的時(shí)間復(fù)雜度都是O( n )。用二維表存儲(chǔ)時(shí)，在內(nèi)存中用數(shù)組的下標(biāo)能準(zhǔn)確定位節(jié)點(diǎn)的父節(jié)點(diǎn)、兄弟節(jié)點(diǎn)所在的數(shù)組下標(biāo)。數(shù)據(jù)庫(kù)中節(jié)點(diǎn)的定位也是準(zhǔn)確的，但是將節(jié)點(diǎn)信息從數(shù)據(jù)庫(kù)中讀到內(nèi)存中時(shí)，如果無法通過內(nèi)存數(shù)組下標(biāo)定位節(jié)點(diǎn)信息，那么就必須遍歷一遍尋找一個(gè)節(jié)點(diǎn)，n 個(gè)節(jié)點(diǎn)中尋找一個(gè)節(jié)點(diǎn)的時(shí)間是O(n/2)，n 個(gè)節(jié)點(diǎn)排序的時(shí)間復(fù)雜度將是O( n 2/2)，這也是一般實(shí)現(xiàn)的B/S 模式的樹結(jié)構(gòu)效率低下的原因。本方案采用字典序編號(hào)方案，使得從數(shù)據(jù)庫(kù)中取得的樹是已經(jīng)排序的，直接遍歷生成客戶頁(yè)面程序，時(shí)間復(fù)雜度為O( n )。
4、結(jié) 論
本文討論了基于Ajax的動(dòng)態(tài)樹型結(jié)構(gòu)的實(shí)現(xiàn)方案，支持無刷新動(dòng)態(tài)維護(hù)樹的節(jié)點(diǎn)信息，支持拖放節(jié)點(diǎn)改變樹的節(jié)點(diǎn)結(jié)構(gòu)以及次序；同時(shí)采用數(shù)據(jù)庫(kù)存儲(chǔ)節(jié)點(diǎn)信息，保證了該方案有一定的通用性，此外結(jié)合XML描述樹的節(jié)點(diǎn)信息，使得任何按本方案預(yù)定的xml文檔描述的信息都可以通過樹來展現(xiàn)。本方案已經(jīng)應(yīng)用在我校的數(shù)字迎新系統(tǒng)以及老百姓大藥房信息系統(tǒng)中。 |
