樹遍歷的時間復雜度是O( n ),但是將樹信息存放到數據庫後,就不能按傳統的方式遍歷樹,必須使用SQL 語句訪問數據庫表的內容,而一次性取的數據量越多,消耗的資源也越多,用戶等待的時間就越長。如果將無序的數據從數據庫中讀出,在服務器端,必須將排序後的樹送到客戶端顯示。因此,最好從數據庫讀出已排好序的樹。
我們知道,字符串排序是按照字典序形式。結合SQL 語句的特點和樹結構特點,數據庫表中,節點的類別代碼采用多級字符串形式,如AAABBBCCC,從樹根節點開始,每向下一級字符串就增加一級,並且子節點類別代碼以父節點類別代碼開始,再開始本級的類別代碼。同級的節點按照生成的順序編號,如節點類別代碼為AAA 的下一級孩子類別代碼為AAAAAA,AAAAAB 等,AAAAAB 的孩子節點為AAAAABAAA、AAAAABAAB等。每一級編號字符的寬度與實際的應用關聯,如AAA~ZZZ 一級則有263 個節點,如果不夠用再增加一個字符用於編碼。該巧妙的編號方式。使得在執行SQL 語句select * from tree_class order by classcode 後,一次獲得完整的先序樹。
2.3 業務邏輯層設計
2.3.1 動態加載技術
如果一次性獲取完整的先序樹,構造成xml提供給JavaScript解析,數據量越大,消耗的資源越多,客戶端響應延遲時間就越長,因此對於大數據量的樹,采用動態加載方式,即每次單擊“+”圖片時,判斷是否已加載子節點數據,如果未加載則通過Ajax的XMLHTTP組件XMLHTTPRequest對象異步發送請求,連接服務器執行SQL 語句“select * from tree_class where parent = ?order by classcode ”獲取節點數據。相關JavaScript 代碼如下:
/*判斷是否已經加載數據,未加載則訪問服務器加載數據*/
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();
/*通過GET方法異步連接到 url 加載數據*/
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;
}
每次只取同一個父節點ParentId的子節點序列,按XML格式封裝成樹的文檔結構,例如:
<tree id="0">
<leaf child=”1" name="國防科技大學" id="1" im0="leaf.gif" im1="folderOpen.gif" im2=" folderClosed.gif"/>
</tree>
提供給JavaScript的dhtmlTreeObject.prototype.insertItem()解析並組織好html輸出節點;其中child:1表示有子節點,0表示沒有子節點;im0表示沒有子節點時的圖標;im1表示有子節點並且打開節點時的圖標;im2表示有子節點並且關閉時的圖標;所以還可以在構造XML時自定義圖標。
2.3.2 樹型結構的構造
從數據庫中返回的是有序的先序樹,而XML是完整的樹型結構文檔,所以將樹型數據構造成預定義的XML格式,只需從根節點開始,遍歷一遍樹,即可將樹全部生成。相關JavaScript代碼如下:
/*動態加載樹的構造方法*/
dtmlXMLObject.prototype.constructTree=function(){
//采用動態加載時獲取的xml數據,解析樹型數據
var node=this.XMLLoader.getXMLTopNode("tree");
var parentId=node.getAttribute("id");
for(var i=0;i<node.childNodes.length;i++) { //逐個解析xml文件的leaf節點
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;//已加載
//構造html輸出節點
dhtmlObject.insertItem(parentId,cId,name,im0,im1,im2,chd);
dhtmlObject.addDragger = this;//設置可拖放的對象
};
}
2.3.3 樹型結構的維護
在維護樹型結構表時,刪除節點較為簡單,SQL 語句為: "delete from tree_class where classcode like′"+ classcode +"%′",即可將其節點和孩子一並刪除;增加節點時,分為前插、後插、和插入子節點三種情況,前兩種情況需要更新遞歸更新類別代碼,後者只需找到父節點的孩子的最大類別代碼加1 後,作為增加節點的類別代碼;通過拖放來改變樹的結構時,只需將拖動節點的parentId更新為目標節點的Classid即可,對應的SQL語句為:"update tree_class set parentId = "+ classidTo+" where classid = "+ classidFrom。
3、效率分析
對於樹的存儲一般有兩種形式:二維表和鏈表,遍歷方式一般也有深度遍歷和廣度遍歷兩種方式,遍歷的時間復雜度都是O( n )。用二維表存儲時,在內存中用數組的下標能准確定位節點的父節點、兄弟節點所在的數組下標。數據庫中節點的定位也是准確的,但是將節點信息從數據庫中讀到內存中時,如果無法通過內存數組下標定位節點信息,那麼就必須遍歷一遍尋找一個節點,n 個節點中尋找一個節點的時間是O(n/2),n 個節點排序的時間復雜度將是O( n 2/2),這也是一般實現的B/S 模式的樹結構效率低下的原因。本方案采用字典序編號方案,使得從數據庫中取得的樹是已經排序的,直接遍歷生成客戶頁面程序,時間復雜度為O( n )。
4、結 論
本文討論了基於Ajax的動態樹型結構的實現方案,支持無刷新動態維護樹的節點信息,支持拖放節點改變樹的節點結構以及次序;同時采用數據庫存儲節點信息,保證了該方案有一定的通用性,此外結合XML描述樹的節點信息,使得任何按本方案預定的xml文檔描述的信息都可以通過樹來展現。本方案已經應用在我校的數字迎新系統以及老百姓大藥房信息系統中。