基于XML鏈?zhǔn)浇Y(jié)構(gòu)的研究

在數(shù)據(jù)結(jié)構(gòu)中，樹型結(jié)構(gòu)是一種非常重要的非線性結(jié)構(gòu)，樹形結(jié)構(gòu)是結(jié)點(diǎn)之間有分支，并具有層次關(guān)系的結(jié)構(gòu)。它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀世界中是大量存在的，例如家譜、行政組織機(jī)構(gòu)都可用樹形象地表示。樹在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系統(tǒng)中，可用樹來(lái)組織信息；在分析算法的行為時(shí)，可用樹來(lái)描述其執(zhí)行過(guò)程。這里可以充分利用其優(yōu)點(diǎn)進(jìn)行系統(tǒng)管理。

XML(Extensible Markup Language，可擴(kuò)展的標(biāo)記語(yǔ)言)。XML是一套定義語(yǔ)義標(biāo)記的規(guī)則，這些標(biāo)記將文檔分成許多部件并對(duì)這些部件加以標(biāo)識(shí)。它也是元標(biāo)記語(yǔ)言，即定義了用于定義其他與特定領(lǐng)域有關(guān)的、語(yǔ)義的、結(jié)構(gòu)化的標(biāo)記語(yǔ)言的句法語(yǔ)言。其起源于SGML(Stand-ard Generalized Markup Language)，是SGML的一個(gè)子集合，即SGML的一個(gè)簡(jiǎn)化版本，它非常適合于在Web上或其他多種數(shù)據(jù)源問(wèn)進(jìn)行數(shù)據(jù)的交換。XML非常適合表達(dá)樹的層次邏輯，為此將XML與數(shù)據(jù)庫(kù)技術(shù)結(jié)合起來(lái)，實(shí)現(xiàn)樹的顯示和維護(hù)。

2 二叉鏈表的結(jié)構(gòu)

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

3 樹形結(jié)構(gòu)的具體實(shí)現(xiàn)

3.1 二叉鏈表結(jié)構(gòu)的設(shè)計(jì)

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

3.2 將數(shù)據(jù)庫(kù)中樹的信息轉(zhuǎn)化成XML

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

算法描述：

3.3 解析XML顯示樹形結(jié)構(gòu)

將數(shù)據(jù)庫(kù)中以二叉鏈表結(jié)構(gòu)存儲(chǔ)的樹的信息通過(guò)上述方法轉(zhuǎn)化為所需的XML后，現(xiàn)在就可以通過(guò)操作XML文檔對(duì)象模型將數(shù)據(jù)島顯示在瀏覽器端。

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

算法描述：

3.4 基于樹形結(jié)構(gòu)的維護(hù)

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

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

4 結(jié) 語(yǔ)

軟件設(shè)計(jì)中數(shù)據(jù)結(jié)構(gòu)的選擇十分重要。對(duì)目前應(yīng)用非常廣泛的樹形結(jié)構(gòu)做了比較深入的研究，發(fā)現(xiàn)應(yīng)用XML技術(shù)和二叉鏈表的存儲(chǔ)結(jié)構(gòu)相結(jié)合能夠非常方便穩(wěn)定地存儲(chǔ)、顯示、維護(hù)樹，并且此種存儲(chǔ)結(jié)構(gòu)應(yīng)用于支持遞歸SQL的Oracle數(shù)據(jù)庫(kù)時(shí)更能體現(xiàn)其方便性，如獲取該樹的一個(gè)子樹，以及取得某結(jié)點(diǎn)的父結(jié)點(diǎn)等都可以通過(guò)1條簡(jiǎn)潔的遞歸SQL語(yǔ)句實(shí)現(xiàn)，為該樹的可擴(kuò)展性和可通用性提供了必要的條件。