多叉樹

多叉樹結合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樹形控制項頁面）

文件二，branchTreeJSON.jsp （接收getBranch.do請求，返回多級樹形結構的JSON字元串）

以上兩個程序文件是一次性生成無限級樹形結構所必須的，其中最為關鍵的部分就是如何生成一個無限級的樹形結構JSON字元串，返回給客戶端的Ext樹形控制項。對於銀行分支機構來說，需要返回類似如下的JSON串：

同時還需要對樹中每一個層次的節點按照某一屬性（比如分支機構編號）進行排序，以展示出有序的樹形結構。

現在可以把問題概括為：

1、把資料庫中的層次數據轉換成多級樹形結構的JSON格式的字元串

2、對樹中每一個層次的節點按照某一屬性（比如分支機構編號）進行排序

下面介紹解決問題的思路：

在數據結構這門課中，我們都學過樹，無限級樹形結構就可以抽象成一種多叉樹結構，即每個節點下包含多個子節點的樹形結構，首先就需要把資料庫中的層次數據轉換成多叉樹結構的對象樹，也就是構造出一棵多叉樹。

有了數據結構，還要實現相應的演演算法，我們需要實現兩種演演算法：

1、兄弟節點橫向排序演演算法，對隸屬於同一個父節點下面的所有直接子節點按照某一節點屬性和規則進行排序，保持兄弟節點橫向有序；

2、先序遍歷演演算法，遞歸列印出無限級JSON字元串。

概括起來分為三步：

1、構造無序的多叉樹結構

2、實現兄弟節點橫向排序方法

3、實現先序遍歷方法，列印出JSON字元串

如圖所示：

好了，通過上面的代碼，就可以實現多叉樹的兄弟節點橫向排序和先序遍歷了，實現了將層次數據轉換為有序無限級樹形結構JSON字元串的目的。

在實際的項目中，可以把上面的有效代碼融入其中，或者在此基礎上進行一些擴展：

1、實現對指定層次的排序（例如只排序第一層的節點，或者只排序某一父節點下的所有子節點）

2、遍歷輸出樹形結構時可以加入判斷條件過濾掉某些節點

3、實現節點的刪除功能

4、在節點類中增加一個父節點的引用，就可以計算出某一節點所處的級別

5、在不支持層次查詢的資料庫應用系統中使用該演演算法實現相同的效果

這篇文章的重點是如何構造有序的無限級的樹形結構JSON字元串，一次性生成樹形結構，而不是利用Ajax的方式，反覆向伺服器端發送請求，一級接一級的載入樹節點。

既然可以構造無限級的JSON字元串，那麼也可以根據這個思路構造無限級的XML字元串，或者構造具有層次結構的UL – LI組合（用UL - LI來展示樹形結構），或者構造具有層次結構的TABLE（用TABLE來展示樹形結構）。如下所示：

另外對TreeGrid樹形表格也有一定的價值：

1、一次性構造樹形表格，實現數據分級展示

2、通過更換比較器，實現對不同表格列的全排序（全排序指的是對所有頁的數據進行排序，而不是只對當前頁的數據排序；排序規則與Oracle資料庫中的層次查詢類似，即兄弟節點橫向排序）

3、實現對樹形表格的完整分頁（每次分頁時，只取固定數目的第一層節點，之後調用toString方法，展示出完整條數的分級數據，即每頁的記錄條數是不固定的，但必須是完整的樹形結構）