陳惠娟馮月春陳亮

摘 要：在Web系統(tǒng)開發(fā)過程中，如何更直觀顯示具有層級關(guān)系的信息備受關(guān)注。樹型結(jié)構(gòu)因其結(jié)構(gòu)性強(qiáng)、層次性好、使用方便等特點(diǎn)在Web系統(tǒng)開發(fā)中得到了廣泛應(yīng)用。介紹了樹型結(jié)構(gòu)原理和樹型結(jié)構(gòu)在關(guān)系型數(shù)據(jù)庫中的表示，闡述了一種基于單表結(jié)構(gòu)的Web動(dòng)態(tài)樹設(shè)計(jì)與實(shí)現(xiàn)。這種樹型結(jié)構(gòu)簡單、直觀、易于數(shù)據(jù)組織，簡化了數(shù)據(jù)庫的設(shè)計(jì)過程，在Web系統(tǒng)開發(fā)中效果良好。

關(guān)鍵詞：樹型結(jié)構(gòu)；關(guān)系數(shù)據(jù)庫；層次關(guān)系；Web動(dòng)態(tài)樹

DOIDOI：10.11907/rjdk.161997

中圖分類號：TP391

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：16727800（2016）011017003

0 引言

樹型結(jié)構(gòu)是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，具有結(jié)構(gòu)清晰、層次分明、操作方便等優(yōu)點(diǎn)，在系統(tǒng)開發(fā)中應(yīng)用廣泛，如：Windows的資源管理器、文件系統(tǒng)中的文件管理、數(shù)據(jù)庫中的索引等，都采用了樹型結(jié)構(gòu)[1]。隨著互聯(lián)網(wǎng)的迅速發(fā)展，樹型結(jié)構(gòu)在B/S結(jié)構(gòu)系統(tǒng)開發(fā)中得到越來越廣泛的應(yīng)用。在Web頁面上實(shí)現(xiàn)樹型目錄，既可簡化創(chuàng)建、管理和維護(hù)工作，又可為瀏覽站點(diǎn)用戶帶來方便，將信息以更直觀的層次結(jié)構(gòu)展現(xiàn)給用戶，充分利用了計(jì)算機(jī)屏幕空間。

目前在互聯(lián)網(wǎng)上廣泛應(yīng)用的樹型結(jié)構(gòu)有兩種：靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)結(jié)構(gòu)。靜態(tài)結(jié)構(gòu)使用最多，實(shí)現(xiàn)簡單，但它不能根據(jù)信息的變化改變樹的結(jié)構(gòu)和內(nèi)容，因此無法反映信息變化，所以靜態(tài)結(jié)構(gòu)主要用于系統(tǒng)功能層次或固定組織結(jié)構(gòu)表達(dá)中；而動(dòng)態(tài)結(jié)構(gòu)中樹節(jié)點(diǎn)可以根據(jù)信息變化需要進(jìn)行動(dòng)態(tài)增刪操作，可以展現(xiàn)動(dòng)態(tài)的數(shù)據(jù)分類、組織機(jī)構(gòu)等，但是實(shí)現(xiàn)相對復(fù)雜。

在動(dòng)態(tài)樹型結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)表達(dá)中，多數(shù)系統(tǒng)采用的是父子關(guān)系表的多表結(jié)構(gòu)存儲，表達(dá)動(dòng)態(tài)樹節(jié)點(diǎn)信息。這種方法雖然能不限層次地增加節(jié)點(diǎn)，但由于在進(jìn)行統(tǒng)計(jì)分析等計(jì)算操作時(shí)，必須使用遞歸過程[2]致使計(jì)算過程十分復(fù)雜。本文將詳細(xì)介紹使用單表結(jié)構(gòu)來實(shí)現(xiàn)多級動(dòng)態(tài)樹[3]方法。

1 樹型結(jié)構(gòu)原理

樹型結(jié)構(gòu)主要由根節(jié)點(diǎn)、葉子節(jié)點(diǎn)和分支節(jié)點(diǎn)組成。任何沒有上一級節(jié)點(diǎn)即沒有父輩節(jié)點(diǎn)的節(jié)點(diǎn)是根節(jié)點(diǎn)；任何沒有下一級節(jié)點(diǎn)即沒有子女節(jié)點(diǎn)的節(jié)點(diǎn)是葉子節(jié)點(diǎn)；既不是葉子節(jié)點(diǎn)也不是根節(jié)點(diǎn)的為分支節(jié)點(diǎn)。一棵樹只有一個(gè)根節(jié)點(diǎn)，分支節(jié)點(diǎn)可以有下一級分支節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)所有子樹中的節(jié)點(diǎn)為該節(jié)點(diǎn)的子孫節(jié)點(diǎn)。樹型結(jié)構(gòu)中每個(gè)節(jié)點(diǎn)包含以下信息[4]：①節(jié)點(diǎn)自身信息；②雙親節(jié)點(diǎn)信息；③孩子節(jié)點(diǎn)信息，見圖1。

由上述定義可看出：在樹型結(jié)構(gòu)中，樹由多個(gè)子樹構(gòu)成，子樹由一些更小的子樹構(gòu)成。總而言之，一個(gè)節(jié)點(diǎn)可以有0、1個(gè)或多個(gè)子節(jié)點(diǎn)，除根節(jié)點(diǎn)沒有父節(jié)點(diǎn)[5]外，其余節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)。

關(guān)系數(shù)據(jù)庫[6]（Relational Database ，簡稱RDB）已成為數(shù)據(jù)庫產(chǎn)品的主流。關(guān)系數(shù)據(jù)庫是將數(shù)據(jù)按表結(jié)構(gòu)形式組織，而樹型結(jié)構(gòu)是一種非線性的數(shù)據(jù)結(jié)構(gòu)。顯然，樹與表格在結(jié)構(gòu)上有很大差別，若把具有樹結(jié)構(gòu)的數(shù)據(jù)簡單線性排列起來，就不能體現(xiàn)數(shù)據(jù)間的父子關(guān)系（層次關(guān)系），意味著信息的丟失。因此，在關(guān)系型數(shù)據(jù)庫中需要解決如何把非線性數(shù)據(jù)線性化排列且保留數(shù)據(jù)間的原有關(guān)系問題。

在關(guān)系型數(shù)據(jù)庫中通常采用下面幾種表示樹的方法[7]：①字段表示法；②代碼表示法；③靜態(tài)指針表示法。

本文采用一種新的表示法，這種表示法是對代碼表示法的一種變型。代碼段的寬度根據(jù)樹的層次不同而不同（根結(jié)點(diǎn)一般是一個(gè)全局結(jié)構(gòu)描述的節(jié)點(diǎn)，可以用一個(gè)靜態(tài)節(jié)點(diǎn)表示，本文使用靜態(tài)節(jié)點(diǎn)處理）。

例如：某樹的層次結(jié)構(gòu)是** *** *** *** ***，用空格來區(qū)分樹型結(jié)構(gòu)層次，用*表示每個(gè)層次的代碼段寬度。這個(gè)層次結(jié)構(gòu)有4個(gè)空格，說明這個(gè)樹型結(jié)構(gòu)層次是5層。第一層代碼段的寬度是2，第二層代碼段的寬度是3，第三層代碼段的寬度是4，依此類推可以得出每一層代碼段的寬度。為了更好地表示樹型結(jié)構(gòu)的層次關(guān)系，本文把當(dāng)前層次節(jié)點(diǎn)以上的層次節(jié)點(diǎn)代碼寬度都加到當(dāng)前層次代碼寬度上，修改后的層級代碼寬度為：第一層代碼寬度是2，第二層代碼寬度是5，第三層代碼寬度是8，第四層代碼寬度是11，第五層代碼寬度是14。

根據(jù)這個(gè)層次結(jié)構(gòu)，第一級節(jié)點(diǎn)可以用01表示，第二級節(jié)點(diǎn)可以用01001表示（前兩位01表示當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)），第三級節(jié)點(diǎn)可以用01001001表示（前五位01001表示當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)），以此類推。這樣不僅可以更直觀地表示父節(jié)點(diǎn)、子節(jié)點(diǎn)及當(dāng)前節(jié)點(diǎn)結(jié)構(gòu)，還可以直觀表示出樹的層次關(guān)系。下面以部門為例對這種表示法進(jìn)行說明。

2 動(dòng)態(tài)樹實(shí)現(xiàn)

2.1 數(shù)據(jù)庫設(shè)計(jì)

為了記錄節(jié)點(diǎn)變化，本文以數(shù)據(jù)庫為載體。數(shù)據(jù)庫中數(shù)據(jù)表至少要有以下字段：節(jié)點(diǎn)編號、節(jié)點(diǎn)名稱、節(jié)點(diǎn)說明、節(jié)點(diǎn)代碼，這些是構(gòu)建樹結(jié)構(gòu)所必須的信息。建立數(shù)據(jù)表如表1所示。

2.2 創(chuàng)建樹型結(jié)構(gòu)流程

根據(jù)數(shù)據(jù)表設(shè)計(jì)，得到創(chuàng)建樹型結(jié)構(gòu)流程，如圖2所示。

2.3 樹的實(shí)現(xiàn)

為了對動(dòng)態(tài)樹構(gòu)建有一個(gè)更清楚的理解，下面以部門樹為例介紹實(shí)現(xiàn)過程。本示例采用Netbeans 6.1開發(fā)工具開發(fā)，服務(wù)器采用Netbeans 6.1自帶的tomact，界面使用JSF進(jìn)行設(shè)計(jì)[89]。

首先定義一個(gè)全局常量Levelno，設(shè)置樹的層級結(jié)構(gòu)假定為**** **** **** **** **結(jié)構(gòu)，在實(shí)現(xiàn)動(dòng)態(tài)樹構(gòu)建過程中定義幾個(gè)函數(shù)：

public int getnodesize（String levelno，String sno）：根據(jù)樹的層級結(jié)構(gòu)levelno來判斷給出的節(jié)點(diǎn)sno是第幾層，如0001是第一級節(jié)點(diǎn)，00010001是第二級節(jié)點(diǎn)。

public int getFamtString（int i，String levelno，String sno）：根據(jù)樹的層級結(jié)構(gòu)levelno，把給出的節(jié)點(diǎn)sno轉(zhuǎn)換為長度為i的數(shù)組，如000100010001轉(zhuǎn)換為長度為3的數(shù)據(jù){0001，00010001，000100010001}。

public int getChildNode（TreeNode PNode，String Cnum）：判斷節(jié)點(diǎn)PNode的子節(jié)點(diǎn)中有沒有節(jié)點(diǎn)值等于Cnum，如果有，返回當(dāng)前節(jié)點(diǎn)，否則返回空節(jié)點(diǎn)。

public int getNode（String[]nodes）：在樹結(jié)構(gòu)中找到一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)是數(shù)組nodes中nodes[nodes.length-1]所對應(yīng)節(jié)點(diǎn)的父節(jié)點(diǎn)，這個(gè)過程需要調(diào)用getChildNode（TreeNode PNode，String Cnum）方法進(jìn)行輔助查找。

public int TreeNode_action（）：點(diǎn)擊一個(gè)樹節(jié)點(diǎn)時(shí)要觸發(fā)的事件，如增加節(jié)點(diǎn)、修改節(jié)點(diǎn)、刪除節(jié)點(diǎn)等事件處理代碼。

按照動(dòng)態(tài)樹的構(gòu)建流程進(jìn)行設(shè)計(jì)。首先將無序數(shù)據(jù)從數(shù)據(jù)庫中讀出，在服務(wù)器端必須將排序后的數(shù)據(jù)發(fā)送到客戶端顯示。本文把數(shù)據(jù)按照節(jié)點(diǎn)代碼順序一次從數(shù)據(jù)庫讀出，執(zhí)行代碼select * from departments order by departLevelno。這種排序可以保證當(dāng)添加到一個(gè)子節(jié)點(diǎn)時(shí)直接得到它的父節(jié)點(diǎn)（已經(jīng)添加到樹中了）。接著讀第一條記錄，把這條記錄中的代碼段與定義的全局變量進(jìn)行比較，得到這條記錄層次。如果層次是1，則說明是根節(jié)點(diǎn)，直接加到樹型結(jié)構(gòu)中，讀下一條記錄；如果層次不是1，則根據(jù)當(dāng)前節(jié)點(diǎn)的代碼段獲取當(dāng)前節(jié)點(diǎn)的直接父節(jié)點(diǎn)，添加到它的直接父節(jié)點(diǎn)下，讀下一條記錄。記錄全部讀完時(shí)，在Web頁面（本文采用的是JSF）加載這部分代碼，這樣樹型結(jié)構(gòu)就構(gòu)建成功了。具體代碼如下：

//讀第一條記錄的sno

String leveno = this.getApplicationBean1（）.getLevelno（）；//得到前面定義的全局//變量

int i = this.getnodesize（leveno，sno）；

String[]childStr = this.getFamtString（i，leveno，sno）；

TreeNode childNode = new TreeNode（）；

if （i == 1） {

childNode.setId（"a" + sno）；

childNode.setText（departname）；

childNode.setImageURL（"/resources/tree_document.gif"）；

ExpressionFactory exFactory = this.getApplication（）.getExpressionFactory（）；

ELContext elContext = getFacesContext（）.getELContext（）； childNode.setActionExpression（exFactory.createMethodExpression（elContext，"#{HrResourceTree.TreeNode_action}"，String.class，new Class<？>[0]））；

child.add（childNode）；

}

else {

childNode = this.getNode（childStr）；

TreeNode addChildNode = new TreeNode（）；

addChildNode.setId（"a" + sno）；

addChildNode.setText（departname）；

addChildNode.setImageURL（"/resources/tree_document.gif"）；

ExpressionFactory exFactory = this.getApplication（）.getExpressionFactory（）；

ELContext elContext = getFacesContext（）.getELContext（）；

addChildNode.setActionExpression（exFactory.createMethodExpression（elContext，"#{HrResourceTree.tripNode_action}"，String.class，new Class<？>[0]））；

childNode.getChildren（）.add（addChildNode）；

}

//讀下一條記錄，直到最后一條記錄

2.4 樹的顯示效果

本文對人力資源部門進(jìn)行樹型結(jié)構(gòu)設(shè)計(jì)[10]，生產(chǎn)部、車間一、第一車段這3部分顯示不同的層次關(guān)系，選定一個(gè)節(jié)點(diǎn)后可以進(jìn)行其它相關(guān)操作（在TreeNode_action中添加相應(yīng)事件代碼），效果如圖3所示。

3 結(jié)語

樹型結(jié)構(gòu)適合表達(dá)具有層次結(jié)構(gòu)的信息，在數(shù)據(jù)庫應(yīng)用程序開發(fā)中經(jīng)常用它表示對象之間的層次關(guān)系，便于用戶操作和使用。本文通過一個(gè)樹型結(jié)構(gòu)例子，說明了層次關(guān)系數(shù)據(jù)在數(shù)據(jù)表中的存儲方式和樹型結(jié)構(gòu)的構(gòu)建方式，并把這種存儲方式和構(gòu)建方式應(yīng)用于人力資源管理系統(tǒng)開發(fā)中。通過分析和實(shí)例驗(yàn)證，使用這種方式不僅能直觀顯示信息，而且能顯示出信息的層次關(guān)系。

參考文獻(xiàn)：

[1] 唐青松.路徑存儲法在生成樹形結(jié)構(gòu)中的應(yīng)用研究[J].計(jì)算機(jī)與現(xiàn)代化，2014（14）：178181.

[2] 張維國，孫效玉，周沖.樹形結(jié)構(gòu)數(shù)據(jù)在數(shù)字礦山中的存儲管理與應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展，2015，25（3）：150153.

[3] 特日根，李巍，李雄飛.動(dòng)態(tài)有序樹存儲模型與實(shí)現(xiàn)方法[J].計(jì)算機(jī)研究與發(fā)展，2013，50（50）：969985.

[4] 呂剛，蔣勇銘，王軍.基于關(guān)系型數(shù)據(jù)庫的樹形結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)光盤軟件與應(yīng)用，2112（17）：224225.

[5] 張雨佳，蘇中濱，吳華瑞，等.半結(jié)構(gòu)化數(shù)據(jù)的動(dòng)態(tài)樹存儲模型研究[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28（5）：8690.

[6] 李恒新，韓堅(jiān)華.關(guān)系型數(shù)據(jù)庫數(shù)據(jù)的高效判重[J].華南師范大學(xué)學(xué)報(bào)，2015（47）：121126.

[7] 施伯樂，丁寶康，樓榮生.數(shù)據(jù)庫系統(tǒng)導(dǎo)論[M].北京：高等教育出版社，2008.

[8] 李俊飛，陳皓，趙衛(wèi)東.樹形結(jié)構(gòu)數(shù)據(jù)輸入輸出控件的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011（32）：30543058.

[9] 陳志平，徐錫山，陳玉教.一種基于Ajax的動(dòng)態(tài)樹型結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)[C].2007中國控制與決策學(xué)術(shù)年會(huì)論文集，2007：735742.

[10] 吳珊珊.某企業(yè)辦公自動(dòng)化系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].廈門：廈門大學(xué)，2013.

（責(zé)任編輯：杜能鋼）