基于單表結(jié)構(gòu)的Web動態(tài)樹設(shè)計與實現(xiàn)

陳惠娟馮月春陳亮

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

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

DOIDOI：10.11907/rjdk.161997

中圖分類號：TP391

文獻標識碼：A 文章編號文章編號：16727800（2016）011017003

0 引言

樹型結(jié)構(gòu)是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，具有結(jié)構(gòu)清晰、層次分明、操作方便等優(yōu)點，在系統(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頁面上實現(xiàn)樹型目錄，既可簡化創(chuàng)建、管理和維護工作，又可為瀏覽站點用戶帶來方便，將信息以更直觀的層次結(jié)構(gòu)展現(xiàn)給用戶，充分利用了計算機屏幕空間。

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

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

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

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

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

關(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é)點一般是一個全局結(jié)構(gòu)描述的節(jié)點，可以用一個靜態(tài)節(jié)點表示，本文使用靜態(tài)節(jié)點處理）。

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

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

2 動態(tài)樹實現(xiàn)

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

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

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

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

2.3 樹的實現(xiàn)

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

參考文獻：

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

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

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

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

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

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

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

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

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

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

（責任編輯：杜能鋼）