-.z多叉樹結合JavaScript樹形控件實現無限級樹形菜單〔一種構建多級有序樹形構造JSON〔或*ML〕數據源的方法〕一、問題研究的背景和意義在Web應用程序開發領域，基于AJA*技術的JavaScript樹形控件已經被廣泛使用，它用來在Html頁面上展現具有層次構造的數據項。目前市場上常見的JavaScript框架及組件庫中均包含自己的樹形控件，例如JQuery、Dojo、UI、E*tJS等，還有一些獨立的樹形控件，例如dhtml*tree等，這些樹形控件完美的解決了層次數據的展示問題。展示離不開數據，樹形控件主要利用AJA*技術從效勞器端獲取數據源，數據源的格式主要包括JSON、*ML等，而這些層次數據一般都存儲在數據庫中。“無限級樹形菜單〞，顧名思義，沒有級別的限制，它的數據通常來自數據庫中的無限級層次數據，這種數據的存儲表通常包括id和parentId這兩個字段，以此來表示數據之間的層次關系。現在問題來了，既然樹形控件的數據源采用JSON或*ML等格式的字符串來組織層次數據，而層次數據又存儲在數據庫的表中，則如何建立起樹形控件與層次數據之間的關系，換句話說，如何將數據庫中的層次數據轉換成對應的層次構造的JSON或*ML格式的字符串，返回給客戶端的JavaScript樹形控件.這就是我們要解決的關鍵技術問題。本文將以目前市場上比較熾熱的E*tJS框架為例，講述實現無限級樹形菜單的方法，該方法同樣適用于其它類似的JS樹形控件。E*tJS框架是富客戶端開發中出類拔萃的框架之一。在E*t的UI控件中，樹形控件無疑是最為常用的控件之一，它用來實現樹形構造的菜單。TreeNode用來實現靜態的樹形菜單，AsyncTreeNode用來實現動態的異步加載樹形菜單，后者最為常用，它通過接收效勞器端返回來的JSON格式的數據，動態生成樹形菜單節點。動態生成樹有兩種思路：一種是一次性生成全部樹節點，另一種是逐級加載樹節點〔利用AJA*，每次點擊節點時查詢下一級節點〕。對于大數據量的菜單節點來說，逐級加載是比較適宜的選擇，但是對于小數據量的菜單來說，一次性生成全部節點應該是最為合理的方案。在實際應用開發中，一般不會遇到特別大數據量的場景，所以一次性生成全部菜單節點是我們重點研究的技術點，也就是本文要解決的關鍵技術問題。本文以基于E*tJS的應用系統為例，講述如何將數據庫中的無限級層次數據一次性在界面中生成全部菜單節點〔例如在界面中以樹形方式一次性展示出銀行所有分支機構的信息〕，同時對每一個層次的菜單節點按照*一屬性和規則排序，展示出有序的菜單樹。解決一次性構造無限級樹形菜單的問題，可以拓展出更多的應用場景，例如樹形構造表格TreeGrid，一次性生成樹形表格，對樹形表格進展完整分頁，對表格列進展全排序；或者可以利用本文的思路擴展出其他的更復雜的應用場景。先看兩個圖例，有個直觀上的認識：圖一，銀行分支機構樹形構造菜單圖二，樹形構造表格二、詳細設計方案讓我們先看兩段代碼片段：文件一，branchTree.html〔E*t樹形控件頁面〕E*t.onReady( function(){ vartree=newE*t.tree.TreePanel({height:300,width:400,animate:true,enableDD:true,containerScroll:true,rootVisible:false,frame:true,//getBranch.do請求效勞器返回多級樹形構造的JSON字符串loader:newE*t.tree.TreeLoader({dataUrl:'getBranch.do'}),root:newE*t.tree.AsyncTreeNode({id:'0',te*t:'根結點'})});tree.e*pandAll();});文件二，branchTreeJSON.jsp〔接收getBranch.do請求，返回多級樹形構造的JSON字符串〕<%//讀取銀行分支機構的層次數據Listresult=DataAccess.getBankInfoList();//將層次數據轉換為多叉樹對象〔本文下面會詳細介紹該數據構造的實現方法〕Noderoot=E*tTreeHelper.createE*tTree(result);%>[<%=root.toString()%><!--以JSON的形式返回響應數據，E*t.tree.TreeLoader會根據此數據生成樹形菜單-->]以上兩個程序文件是一次性生成無限級樹形菜單所必須的，其中最為關鍵的局部就是如何生成一個無限級的樹形構造JSON字符串，返回給客戶端的E*t樹形控件。對于銀行分支機構來說，需要返回類似如下的JSON串：{ id:'100000', te*t:'**銀行總行', children:[ { id:'110000', te*t:'**分行', children:[ { id:'113000', te*t:'**銀行開發區支行', leaf:true },{ id:'112000', te*t:'**銀行解放道支行', children:[ { id:'112200', te*t:'**銀行三大街支行', leaf:true }, { id:'112100', te*t:'**銀行廣陽道支行', leaf:true } ] }, { id:'111000', te*t:'**銀行金光道支行', leaf:true } ] } ]}同時還需要對樹中每一個層次的節點按照*一屬性〔比方分支機構編號〕進展排序，以展示出有序的樹形菜單。現在可以把問題概括為：把數據庫中的層次數據轉換成多級樹形構造的JSON格式的字符串對樹中每一個層次的節點按照*一屬性〔比方分支機構編號〕進展排序下面介紹解決問題的思路：在數據構造這門課中，我們都學過樹，無限級樹形菜單就可以抽象成一種多叉樹構造，即每個節點下包含多個子節點的樹形構造，首先就需要把數據庫中的層次數據轉換成多叉樹構造的對象樹，也就是構造出一棵多叉樹。有了數據構造，還要實現相應的算法，我們需要實現兩種算法：1、兄弟節點橫向排序算法，對隸屬于同一個父節點下面的所有直接子節點按照*一節點屬性和規則進展排序，保持兄弟節點橫向有序；2、先序遍歷算法，遞歸打印出無限級JSON字符串。概括起來分為三步：構造無序的多叉樹構造實現兄弟節點橫向排序方法實現先序遍歷方法，打印出JSON字符串如下列圖：我們給這棵樹起個名字吧，就叫做multipletree

，簡稱M-Tree。三、源代碼實現〔Java語言版〕實現這樣一顆樹，需要設計三個類：樹類〔MultipleTree.java〕、節點類〔Node.java〕、孩子列表類〔Children.java〕；為了方便演示，還需要構造一些假的層次數據，因此還需要建一個構造假數據的類〔VirtualDataGenerator.java〕，以下代碼拷貝出來之后可直接運行測試：packagetest;importjava.util.ArrayList;importjava.util.parator;importjava.util.HashMap;importjava.util.Iterator;importjava.util.List;importjava.util.Map;importjava.util.Set;importjava.util.Collections;/***多叉樹類*/publicclassMultipleTree{ publicstaticvoidmain(String[]args){ //讀取層次數據結果集列表 ListdataList=VirtualDataGenerator.getVirtualResult(); //節點列表〔散列表，用于臨時存儲節點對象〕 HashMapnodeList=newHashMap(); //根節點 Noderoot=null; //根據結果集構造節點列表〔存入散列表〕 for(Iteratorit=dataList.iterator();it.hasNe*t();){ MapdataRecord=(Map)it.ne*t(); Nodenode=newNode(); node.id=(String)dataRecord.get("id"); node.te*t=(String)dataRecord.get("te*t"); node.parentId=(String)dataRecord.get("parentId"); nodeList.put(node.id,node); } //構造無序的多叉樹 SetentrySet=nodeList.entrySet(); for(Iteratorit=entrySet.iterator();it.hasNe*t();){ Nodenode=(Node)((Map.Entry)it.ne*t()).getValue(); if(node.parentId==null||node.parentId.equals(")){ root=node; }else{ ((Node)nodeList.get(node.parentId)).addChild(node); } } //輸出無序的樹形菜單的JSON字符串 System.out.println(root.toString()); //對多叉樹進展橫向排序 root.sortChildren(); //輸出有序的樹形菜單的JSON字符串 System.out.println(root.toString()); //程序輸出結果如下〔無序的樹形菜單〕〔格式化后的結果〕： // { // id:'100000', // te*t:'**銀行總行', // children:[ // { // id:'110000', // te*t:'**分行', // children:[ // { // id:'113000', // te*t:'**銀行開發區支行', // leaf:true // }, // { // id:'111000', // te*t:'**銀行金光道支行', // leaf:true // }, // { // id:'112000', // te*t:'**銀行解放道支行', // children:[ // { // id:'112200', // te*t:'**銀行三大街支行', // leaf:true // }, // { // id:'112100', // te*t:'**銀行廣陽道支行', // leaf:true // } // ] // } // ] // } // ] // } //程序輸出結果如下〔有序的樹形菜單〕〔格式化后的結果〕： // {// id:'100000', // te*t:'**銀行總行', // children:[ // { // id:'110000', // te*t:'**分行', // children:[ // { // id:'111000', // te*t:'**銀行金光道支行', // leaf:true // }, // { // id:'112000', // te*t:'**銀行解放道支行', // children:[ // { // id:'112100', // te*t:'**銀行廣陽道支行', // leaf:true // }, // { // id:'112200', // te*t:'**銀行三大街支行', // leaf:true // } // ] // }, // { // id:'113000', // te*t:'**銀行開發區支行', // leaf:true // } // ] // } // ] // } }}/***節點類*/classNode{ /** *節點編號 */ publicStringid; /** *節點內容 */ publicStringte*t; /** *父節點編號 */ publicStringparentId; /** *孩子節點列表 */ privateChildrenchildren=newChildren(); //先序遍歷，拼接JSON字符串 publicStringtoString(){ Stringresult="{" +"id:'"+id+"'" +",te*t:'"+te*t+"'"; if(children!=null&&children.getSize()!=0){ result+=",children:"+children.toString(); }else{ result+=",leaf:true"; } returnresult+"}"; } //兄弟節點橫向排序 publicvoidsortChildren(){ if(children!=null&&children.getSize()!=0){ children.sortChildren(); } } //添加孩子節點 publicvoidaddChild(Nodenode){ this.children.addChild(node); }}/***孩子列表類*/classChildren{ privateListlist=newArrayList(); publicintgetSize(){ returnlist.size(); } publicvoidaddChild(Nodenode){ list.add(node); } //拼接孩子節點的JSON字符串 publicStringtoString(){ Stringresult="["; for(Iteratorit=list.iterator();it.hasNe*t();){ result+=((Node)it.ne*t()).toString(); result+=","; } result=result.substring(0,result.length()-1); result+="]"; returnresult; } //孩子節點排序 publicvoidsortChildren(){ //對本層節點進展排序 //可根據不同的排序屬性，傳入不同的比較器，這里傳入ID比較器 Collections.sort(list,newNodeIDparator()); //對每個節點的下一層節點進展排序 for(Iteratorit=list.iterator();it.hasNe*t();){ ((Node)it.ne*t()).sortChildren(); } }}/***節點比較器*/classNodeIDparatorimplementsparator{ //按照節點編號比較 publicintpare(Objecto1,Objecto2){intj1=Integer.parseInt(((Node)o1).id); intj2=Integer.parseInt(((Node)o2).id);return(j1<j2?-1:(j1==j2?0:1)); } }/***構造虛擬的層次數據*/classVirtualDataGenerator{ //構造無序的結果集列表，實際應用中，該數據應該從數據庫中查詢獲得； publicstaticListgetVirtualResult(){ ListdataList=newArrayList(); HashMapdataRecord1=newHashMap(); dataRecord1.put("id","112000"); dataRecord1.put("te*t","**銀行解放道支行"); dataRecord1.put("parentId","110000"); HashMapdataRecord2=newHashMap(); dataRecord2.put("id","112200"); dataRecord2.put("te*t","**銀行三大街支行"); dataRecord2.put("parentId","112000"); HashMapdataRecord3=newHashMap(); dataRecord3.put("id","112100"); dataRecord3.put("te*t","**銀行廣陽道支行"); dataRecord3.put("parentId","112000"); HashMapdataRecord4=newHashMap(); dataRecord4.put("id","113000"); dataRecord4.put("te*t","**銀行開發區支行"); dataRecord4.put("parentId","110000"); HashMapdataRecord5=newHashMap(); dataRecord5.put("id","100000"); dataRecord5.put("te*t","**銀行總行"); dataRecord5.put("parentId","); HashMapdataRecord6=newHashMap(); dataRecord6.put("id","110000"); dataRecord6.put("te*t","**分行"); dataRecord6.put("parentId","100000"); HashMapdataRecord7=newHashMap(); dataRecord7.put("id","111000"); dataRecord7.put("te*t","**銀行金光道支行"); 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); returndataList; } }好了，通過上面的代碼，就可以實現多叉樹的兄弟節點橫向排序和先序遍歷了，實現了將層次數據轉換為有序無限級樹形構造JSON字符串的目的。在實際的工程中，可以把上面的有效代碼融入其中，或者在此根底上進展一些擴展：實現對指定層次的排序〔例如只排序第一層的節點，或者只排序*一父節點下的所有子節點〕遍歷輸出樹形構造時可以參加判斷條件過濾掉*些節點實現節點的刪除功能在節點類中增加一個父節點的引用，就可以計算出*一節點所處的級別在不支持層次查詢〔hieraricalretrival〕的數據庫應用系統中使用該算法實現一樣的效果四、思考與總結這篇文章的重點是如何構造有序的無限級的樹形構造JSON字符串，一次性生成樹形菜單，而不是利用AJA*的方式，反復向效勞器端發送請求，一級接一級的加載樹節點。既然可以構造無限級的JSON字符串，則也可以根據這個思路構造無限級的*ML字符串，或者構造具有層次構造的UL–LI組合〔用UL-LI來展示樹形構造〕，或者構造具有層次構造的TABLE〔用TABLE來展示樹形構造〕。如下所示：〔1〕*ML層次構造<menuGroupid="100000"name="**銀行總行"> <menuGroupid="110000"name="**分行"> <menuid="113000"name="**銀行開發區支行"> </menu> <menuid="111000"name="**銀行金光道支行"> </menu> <menuGroupid="112000"name="**銀行解放道支行"> <menuid="112200"name="**銀行三大街支行"> </menu> <menuid="112100"name="**銀行廣陽道支行"> </menu> </menuGroup> </menuGroup></menuGroup>〔2〕UL-LI層次構造<ul> <li>**銀行總行</li> <ul> <li>**分行<