基于XML鏈式結構的研究

　　簡(jiǎn)介：在數據結構中，樹(shù)型結構是一種非常重要的非線(xiàn)性結構，樹(shù)形結構是結點(diǎn)之間有分支，并具有層次關(guān)系的結構。XML非常適合表達樹(shù)的層次邏輯，為此將XML與數據庫技術(shù)結合起來(lái)，實(shí)現樹(shù)的顯示和維護。

　　1 二叉鏈表的結構

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

　　2 樹(shù)形結構的具體實(shí)現

　　2.1 二叉鏈表結構的設計

　　給出一個(gè)二叉樹(shù)接點(diǎn)的Java接口，稱(chēng)之為BinNode。BinNode類(lèi)中存儲指向Object類(lèi)的引用。創(chuàng )建二叉樹(shù)時(shí)，可以根據需要而采用實(shí)際的數據類(lèi)型。成員函數包括返回元素的值，返回左、XML右節點(diǎn)指針，設置元素的值，判斷該結點(diǎn)是否為葉結點(diǎn)。

　　2.2 將數據庫中樹(shù)的信息轉化成XML

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

　　算法描述：

　　2.3 解析XML顯示樹(shù)形結構

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

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

　　算法描述：

　　2.4 基于樹(shù)形結構的維護

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

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