本文通過一種構造樹形JSON的方法來講述多叉樹的概念和用途。
基本介紹
- 中文名：多叉樹
- 所屬學科：計算機科學
相關介紹,概念,套用,意義,類型,示例,設計方案,代碼書寫,運用,總結,原始碼實現,代碼的書寫,代碼的擴展,思考與總結,節點,XML層次結構,UL - LI 層次結構,TABLE層次結構,利用價值,
相關介紹
概念
多叉樹結合JavaScript樹形控制項實現無限級樹形結構（一種構建多級有序樹形結構JSON（或XML）數據源的方法）
套用
樹形控制項套用：在Web應用程式開發領域，基於Ajax技術的JavaScript樹形控制項已經被廣泛使用，它用來在Html頁面上展現具有層次結構的數據項。目前市場上常見的JavaScript框架及組件庫中均包含自己的樹形控制項，例如jQuery、Ext JS等，還有一些獨立的樹形控制項，例如dhtmlxTree等，這些樹形控制項完美的解決了層次數據的展示問題。展示離不開數據，樹形控制項主要利用Ajax技術從伺服器端獲取數據源，數據源的格式主要包括JSON、XML等，而這些層次數據一般都存儲在資料庫中。
意義
無限級樹形結構：“無限級樹形結構”，顧名思義，沒有級別的限制，它的數據通常來自資料庫中的無限級層次數據，這種數據的存儲表通常包括id和parentId這兩個欄位，以此來表示數據之間的層次關係。現在問題來了，既然樹形控制項的數據源採用JSON或XML等格式的字元串來組織層次數據，而層次數據又存儲在資料庫的表中，那么如何建立起樹形控制項與層次數據之間的關係，換句話說，如何將資料庫中的層次數據轉換成對應的層次結構的JSON或XML格式的字元串，返回給客戶端的JavaScript樹形控制項？這就是我們要解決的關鍵技術問題。本文將以目前市場上比較知名的Ext JS框架為例，講述實現無限級樹形結構的方法，該方法同樣適用於其它類似的JavaScript樹形控制項。
類型
Ext JS框架：Ext JS框架是富客戶端開發中出類拔萃的框架之一。在Ext的UI控制項中，樹形控制項無疑是最為常用的控制項之一，它用來實現樹形結構的視圖。TreeNode用來實現靜態的樹形結構，AsyncTreeNode用來實現動態的異步載入樹形結構，後者最為常用，它通過接收伺服器端返回來的JSON格式的數據，動態生成樹形結構節點。動態生成樹有兩種思路：一種是一次性生成全部樹節點，另一種是逐級載入樹節點（利用Ajax，每次點擊節點時查詢下一級節點）。對於大數據量的樹節點來說，逐級載入是比較合適的選擇，但是對於小數據量的樹節點來說，一次性生成全部節點應該是最為合理的方案。在實際套用開發中，一般不會遇到特別大數據量的場景，所以一次性生成全部樹節點是我們重點研究的技術點，也就是本文要解決的關鍵技術問題。本文以基於Ext JS的套用系統為例，講述如何將資料庫中的無限級層次數據一次性在界面中生成全部樹節點（例如在界面中以樹形方式一次性展示出銀行所有分支機構的信息），同時對每一個層次的節點按照某一屬性和規則排序，展示出有序的樹形結構。
解決一次性構造無限級樹形結構的問題，可以拓展出更多的套用場景，例如樹形結構表格TreeGrid，一次性生成樹形表格，對樹形表格進行完整分頁，對表格列進行全排序；或者可以利用本文的思路擴展出其他的更複雜的套用場景。
示例
銀行分支機構樹形結構
先看兩個圖例，有個直觀上的認識：
圖一，銀行分支機構樹形結構
圖一，銀行分支機構樹形結構
樹形結構表格
圖二，樹形結構表格
設計方案
代碼書寫
讓我們先看兩段代碼片段：
檔案一，branchTree.html （Ext樹形控制項頁面）
檔案一，branchTree.html （Ext樹形控制項頁面）
Ext.onReady( function(){ var tree = new Ext.tree.TreePanel({ height: 300, width: 400, animate:true, enableDD:true, containerScroll: true, rootVisible: false, frame: true, // getBranch.do請求伺服器返回多級樹形結構的JSON字元串 loader: new Ext.tree.TreeLoader({dataUrl:'getBranch.do'}), root : new Ext.tree.AsyncTreeNode({id:'0',text:'根結點'}) }); tree.expandAll(); });檔案二，branchTreeJSON.jsp （接收getBranch.do請求，返回多級樹形結構的JSON字元串）
<%// 讀取銀行分支機構的層次數據List result = DataAccess.getBankInfoList();// 將層次數據轉換為多叉樹對象（本文下面會詳細介紹該數據結構的實現方法）Node root = ExtTreeHelper.createExtTree(result); %> [<%=root.toString()%> <!-- 以JSON的形式返迴響應數據，Ext.tree.TreeLoader會根據此數據生成樹形結構 -->]
以上兩個程式檔案是一次性生成無限級樹形結構所必須的，其中最為關鍵的部分就是如何生成一個無限級的樹形結構JSON字元串，返回給客戶端的Ext樹形控制項。對於銀行分支機構來說，需要返回類似如下的JSON串：
{ id: '100000', text: '廊坊銀行總行', children: [ { id: '110000', text: '廊坊分行', children: [ { id: '113000', text: '廊坊銀行開發區支行', leaf: true }, { id: '112000', text: '廊坊銀行解放道支行', children: [ { id: '112200', text: '廊坊銀行三大街支行', leaf: true }, { id: '112100', text: '廊坊銀行廣陽道支行', leaf: true } ] }, { id: '111000', text: '廊坊銀行金光道支行', leaf: true } ] } ]}同時還需要對樹中每一個層次的節點按照某一屬性（比如分支機構編號）進行排序，以展示出有序的樹形結構。
運用
現在可以把問題概括為：
1、把資料庫中的層次數據轉換成多級樹形結構的JSON格式的字元串
2、對樹中每一個層次的節點按照某一屬性（比如分支機構編號）進行排序
1、把資料庫中的層次數據轉換成多級樹形結構的JSON格式的字元串
2、對樹中每一個層次的節點按照某一屬性（比如分支機構編號）進行排序
下面介紹解決問題的思路：
在數據結構這門課中，我們都學過樹，無限級樹形結構就可以抽象成一種多叉樹結構，即每個節點下包含多個子節點的樹形結構，首先就需要把資料庫中的層次數據轉換成多叉樹結構的對象樹，也就是構造出一棵多叉樹。
在數據結構這門課中，我們都學過樹，無限級樹形結構就可以抽象成一種多叉樹結構，即每個節點下包含多個子節點的樹形結構，首先就需要把資料庫中的層次數據轉換成多叉樹結構的對象樹，也就是構造出一棵多叉樹。
有了數據結構，還要實現相應的算法，我們需要實現兩種算法：
1、兄弟節點橫向排序算法，對隸屬於同一個父節點下面的所有直接子節點按照某一節點屬性和規則進行排序，保持兄弟節點橫向有序；
2、先序遍歷算法，遞歸列印出無限級JSON字元串。
1、兄弟節點橫向排序算法，對隸屬於同一個父節點下面的所有直接子節點按照某一節點屬性和規則進行排序，保持兄弟節點橫向有序；
2、先序遍歷算法，遞歸列印出無限級JSON字元串。
總結
概括起來分為三步：
1、構造無序的多叉樹結構
2、實現兄弟節點橫向排序方法
3、實現先序遍歷方法，列印出JSON字元串
1、構造無序的多叉樹結構
2、實現兄弟節點橫向排序方法
3、實現先序遍歷方法，列印出JSON字元串
如圖所示：
原始碼實現
代碼的書寫
package test;
import java.util.ArrayList;import java.util.Comparator;import java.util.HashMap;import java.util.Iterator;import java.util.List;import java.util.Map;import java.util.Set;import java.util.Collections;
/** * 多叉樹類 */public class Tree { public static void main(String[] args) { // 讀取層次數據結果集列表 List dataList = VirtualDataGenerator.getVirtualResult(); // 節點列表（映射表，用於臨時存儲節點對象） HashMap nodeList = new HashMap(); // 根節點 Node root = null; // 將結果集存入映射表（後面將藉助映射表構造多叉樹） for (Iterator it = dataList.iterator(); it.hasNext();) { Map dataRecord = (Map) it.next(); Node node = new Node(); node.id = (String) dataRecord.get("id"); node.text = (String) dataRecord.get("text"); node.parentId = (String) dataRecord.get("parentId"); nodeList.put(node.id, node); } // 構造無序的多叉樹 Set entrySet = nodeList.entrySet(); for (Iterator it = entrySet.iterator(); it.hasNext();) { Node node = (Node) ((Map.Entry) it.next()).getValue(); if (node.parentId == null || node.parentId.equals("")) { root = node; } else { ((Node) nodeList.get(node.parentId)).addChild(node); } } // 輸出無序的樹形結構的JSON字元串 System.out.println(root); // 對多叉樹進行橫向排序 root.sortChildren(); // 輸出有序的樹形結構的JSON字元串 System.out.println(root); // 程式輸出結果如下: // // 無序的樹形結構（格式化後的結果）: // { // id : '100000', // text : '廊坊銀行總行', // children : [ // { // id : '110000', // text : '廊坊分行', // children : [ // { // id : '113000', // text : '廊坊銀行開發區支行', // leaf : true // }, // { // id : '111000', // text : '廊坊銀行金光道支行', // leaf : true // }, // { // id : '112000', // text : '廊坊銀行解放道支行', // children : [ // { // id : '112200', // text : '廊坊銀行三大街支行', // leaf : true // }, // { // id : '112100', // text : '廊坊銀行廣陽道支行', // leaf : true // } // ] // } // ] // } // ] // } // 有序的樹形結構（格式化後的結果）： // { // id : '100000', // text : '廊坊銀行總行', // children : [ // { // id : '110000', // text : '廊坊分行', // children : [ // { // id : '111000', // text : '廊坊銀行金光道支行', // leaf : true // }, // { // id : '112000', // text : '廊坊銀行解放道支行', // children : [ // { // id : '112100', // text : '廊坊銀行廣陽道支行', // leaf : true // }, // { // id : '112200', // text : '廊坊銀行三大街支行', // leaf : true // } // ] // }, // { // id : '113000', // text : '廊坊銀行開發區支行', // leaf : true // } // ] // } // ] // } }
}
/** * 節點類 */class Node { /** * 節點編號 */ public String id;/** * 節點內容 */ public String text;
/** * 父節點編號 */ public String parentId;
/** * 孩子節點列表 */ private List children = new ArrayList();
// 添加孩子節點 public void addChild(Node node) { children.add(node); } // 先序遍歷，拼接JSON字元串 public String toString() { String result = "{" + "id : '" + id + "'" + ", text : '" + text + "'"; if (children.size() != 0) { result += ", children : ["; for (int i = 0; i < children.size(); i++) { result += ((Node) children.get(i)).toString() + ","; } result = result.substring(0, result.length() - 1); result += "]"; } else { result += ", leaf : true"; } return result + "}"; } // 兄弟節點橫向排序 public void sortChildren() { if (children.size() != 0) { // 對本層節點進行排序（可根據不同的排序屬性，傳入不同的比較器，這裡 傳入ID比較器） Collections.sort(children, new NodeIDComparator()); // 對每個節點的下一層節點進行排序 for (int i = 0; i < children.size(); i++) { ((Node) children.get(i)).sortChildren(); } } }}
/** * 節點比較器 */class NodeIDComparator implements Comparator { // 按照節點編號比較 public int compare(Object o1, Object o2) { int j1 = Integer.parseInt(((Node) o1).id); int j2 = Integer.parseInt(((Node) o2).id); return (j1 < j2 ? -1 : (j1 == j2 ? 0 : 1)); }}/** * 構造虛擬的層次數據 */class VirtualDataGenerator { // 構造無序的結果集列表，實際套用中，該數據應該從資料庫中查詢獲得； public static List getVirtualResult() { List dataList = new ArrayList(); HashMap dataRecord1 = new HashMap(); dataRecord1.put("id", "112000"); dataRecord1.put("text", "廊坊銀行解放道支行"); dataRecord1.put("parentId", "110000"); HashMap dataRecord2 = new HashMap(); dataRecord2.put("id", "112200"); dataRecord2.put("text", "廊坊銀行三大街支行"); dataRecord2.put("parentId", "112000"); HashMap dataRecord3 = new HashMap(); dataRecord3.put("id", "112100"); dataRecord3.put("text", "廊坊銀行廣陽道支行"); dataRecord3.put("parentId", "112000"); HashMap dataRecord4 = new HashMap(); dataRecord4.put("id", "113000"); dataRecord4.put("text", "廊坊銀行開發區支行"); dataRecord4.put("parentId", "110000"); HashMap dataRecord5 = new HashMap(); dataRecord5.put("id", "100000"); dataRecord5.put("text", "廊坊銀行總行"); dataRecord5.put("parentId", ""); HashMap dataRecord6 = new HashMap(); dataRecord6.put("id", "110000"); dataRecord6.put("text", "廊坊分行"); dataRecord6.put("parentId", "100000"); HashMap dataRecord7 = new HashMap(); dataRecord7.put("id", "111000"); dataRecord7.put("text", "廊坊銀行金光道支行"); 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);
return dataList; }}
好了，通過上面的代碼，就可以實現多叉樹的兄弟節點橫向排序和先序遍歷了，實現了將層次數據轉換為有序無限級樹形結構JSON字元串的目的。
代碼的擴展
在實際的項目中，可以把上面的有效代碼融入其中，或者在此基礎上進行一些擴展：
1、實現對指定層次的排序（例如只排序第一層的節點，或者只排序某一父節點下的所有子節點）
2、遍歷輸出樹形結構時可以加入判斷條件過濾掉某些節點
3、實現節點的刪除功能
4、在節點類中增加一個父節點的引用，就可以計算出某一節點所處的級別
5、在不支持層次查詢的資料庫套用系統中使用該算法實現相同的效果
1、實現對指定層次的排序（例如只排序第一層的節點，或者只排序某一父節點下的所有子節點）
2、遍歷輸出樹形結構時可以加入判斷條件過濾掉某些節點
3、實現節點的刪除功能
4、在節點類中增加一個父節點的引用，就可以計算出某一節點所處的級別
5、在不支持層次查詢的資料庫套用系統中使用該算法實現相同的效果
思考與總結
節點
這篇文章的重點是如何構造有序的無限級的樹形結構JSON字元串，一次性生成樹形結構，而不是利用Ajax的方式，反覆向伺服器端傳送請求，一級接一級的載入樹節點。
既然可以構造無限級的JSON字元串，那么也可以根據這個思路構造無限級的XML字元串，或者構造具有層次結構的UL – LI組合（用UL - LI來展示樹形結構），或者構造具有層次結構的TABLE（用TABLE來展示樹形結構）。如下所示：
XML層次結構
<nodeGroup id="100000" name="廊坊銀行總行"> <nodeGroup id="110000" name="廊坊分行"> <node id="113000" name="廊坊銀行開發區支行"> </node> <node id="111000" name="廊坊銀行金光道支行"> </node> <nodeGroup id="112000" name="廊坊銀行解放道支行"> <node id="112200" name="廊坊銀行三大街支行"> </node> <node id="112100" name="廊坊銀行廣陽道支行"> </node> </nodeGroup> </nodeGroup></nodeGroup>
UL - LI 層次結構
<ul> <li>廊坊銀行總行</li> <ul> <li>廊坊分行</li> <ul> <li>廊坊銀行開發區支行</li> <li>廊坊銀行解放道支行</li> <ul> <li>廊坊銀行三大街支行</li> <li>廊坊銀行廣陽道支行</li> </ul> <li>廊坊銀行金光道支行</li> </ul> </ul> </ul>
TABLE層次結構
<table><tr><td>廊坊銀行總行</td></tr><tr><td> 廊坊分行</td></tr><tr><td> 廊坊銀行開發區支行</td></tr><tr><td> 廊坊銀行解放道支行</td></tr><tr><td> 廊坊銀行三大街支行</td></tr><tr><td> 廊坊銀行廣陽道支行</td></tr><tr><td> 廊坊銀行金光道支行</td></tr></table>
利用價值
另外對TreeGrid樹形表格也有一定的價值：
1、一次性構造樹形表格，實現數據分級展示
2、通過更換比較器，實現對不同表格列的全排序（全排序指的是對所有頁的數據進行排序，而不是只對當前頁的數據排序；排序規則與Oracle資料庫中的層次查詢類似，即兄弟節點橫向排序）
3、實現對樹形表格的完整分頁（每次分頁時，只取固定數目的第一層節點，之後調用toString方法，展示出完整條數的分級數據，即每頁的記錄條數是不固定的，但必須是完整的樹形結構）
1、一次性構造樹形表格，實現數據分級展示
2、通過更換比較器，實現對不同表格列的全排序（全排序指的是對所有頁的數據進行排序，而不是只對當前頁的數據排序；排序規則與Oracle資料庫中的層次查詢類似，即兄弟節點橫向排序）
3、實現對樹形表格的完整分頁（每次分頁時，只取固定數目的第一層節點，之後調用toString方法，展示出完整條數的分級數據，即每頁的記錄條數是不固定的，但必須是完整的樹形結構）
