基于XML鏈式結構的研究

在數據結構中，樹型結構是一種非常重要的非線性結構，樹形結構是結點之間有分支，并具有層次關系的結構。它非常類似于自然界中的樹。樹結構在客觀世界中是大量存在的，例如家譜、行政組織機構都可用樹形象地表示。樹在計算機領域中也有著廣泛的應用，例如在編譯程序中，用樹來表示源程序的語法結構；在數據庫系統中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執行過程。這里可以充分利用其優點進行系統管理。

XML(Extensible Markup Language，可擴展的標記語言)。XML是一套定義語義標記的規則，這些標記將文檔分成許多部件并對這些部件加以標識。它也是元標記語言，即定義了用于定義其他與特定領域有關的、語義的、結構化的標記語言的句法語言。其起源于SGML(Stand-ard Generalized Markup Language)，是SGML的一個子集合，即SGML的一個簡化版本，它非常適合于在Web上或其他多種數據源問進行數據的交換。XML非常適合表達樹的層次邏輯，為此將XML與數據庫技術結合起來，實現樹的顯示和維護。

2 二叉鏈表的結構

在計算機中存儲一棵樹，不僅要存儲樹中每個結點的數值，而且還要存儲結點與結點之間的關系。二叉樹(Binary Tree)是n(n≥0)個結點的有限集，它或者是空集(n=0)，或者由1個根結點及2棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。

3 樹形結構的具體實現

3.1 二叉鏈表結構的設計

給出一個二叉樹接點的Java接口，稱之為BinNode。BinNode類中存儲指向Object類的引用。創建二叉樹時，可以根據需要而采用實際的數據類型。成員函數包括返回元素的值，返回左、XML右節點指針，設置元素的值，判斷該結點是否為葉結點。

3.2 將數據庫中樹的信息轉化成XML

初始條件：樹T存在，id是樹中某個結點編號。操作目的：將以id為根結點的子樹轉化為XML格式。算法思想：根據當前根結點找出左孩子和右兄弟，添加當前結點信息到XML中，然后遞歸以左孩子為根結點的子樹，最后在遞歸以右兄弟為根結點的子樹。還要注意如果當前結點為該樹的根結點，則不能遞歸以它的右兄弟為根結點的子樹。

算法描述：

3.3 解析XML顯示樹形結構

將數據庫中以二叉鏈表結構存儲的樹的信息通過上述方法轉化為所需的XML后，現在就可以通過操作XML文檔對象模型將數據島顯示在瀏覽器端。

初始條件：XML形式的數據島。操作目的：通過JavaScript解析XML并以HTML的形式在瀏覽器端顯示樹。算法思想：將數據島加載到DOM對象后，向瀏覽器添加根結點的HTML代碼，對DOM對象根結點的所有一級子結點，再遞歸調用顯示其下一級子結點的HTML代碼。

算法描述：

3.4 基于樹形結構的維護

從數據庫中提取樹的信息后，在瀏覽器端樹上設置JavaScript事件，通過它們我們可以對該樹進行維護，包括插入、刪除、更新、移動等操作。維護的時候，JavaScript事件將用戶對樹的維護情況記錄到XML對象中。

其他刪除、更新、移動結點操作需要對XML增加的信息與此相似。用戶維護結束，將該XML對象提交到服務器，后臺負責根據設置的插入、刪除等操作標志解析上述XML對象，就可以生成相應的插入、刪除、更新的SQL語句，最后提交到數據庫。另外需要注意的是，由于數據庫中存儲的二叉鏈表形式的各結點相互間有關聯，所以對其進行插入、刪除、移動操作時候還必須考慮因此操作而引起的相關結點的信息的更新，比如當刪除一個結點時，除了需要刪除該結點外，還可能要修改其父結點的左孩子指針的值，或者需要修改其上一個兄弟結點的右兄弟指針的值。

4 結 語

軟件設計中數據結構的選擇十分重要。對目前應用非常廣泛的樹形結構做了比較深入的研究，發現應用XML技術和二叉鏈表的存儲結構相結合能夠非常方便穩定地存儲、顯示、維護樹，并且此種存儲結構應用于支持遞歸SQL的Oracle數據庫時更能體現其方便性，如獲取該樹的一個子樹，以及取得某結點的父結點等都可以通過1條簡潔的遞歸SQL語句實現，為該樹的可擴展性和可通用性提供了必要的條件。