路徑存儲(chǔ)法在生成樹形結(jié)構(gòu)中的應(yīng)用研究

唐青松

(四川文理學(xué)院計(jì)算機(jī)學(xué)院，四川 達(dá)州 635000)

0 引言

樹形結(jié)構(gòu)應(yīng)用十分廣泛，它不但可以為用戶隨時(shí)更改樹的結(jié)構(gòu)和隨意調(diào)整樹節(jié)點(diǎn)的層次關(guān)系帶來(lái)方便，而且以樹狀外觀展示給用戶，體現(xiàn)出一種簡(jiǎn)約美。現(xiàn)有的生成樹形結(jié)構(gòu)主要由以下技術(shù)實(shí)現(xiàn):(1)遍歷節(jié)點(diǎn)法，即使用樹的遍歷算法排列出數(shù)據(jù)庫(kù)中節(jié)點(diǎn)的訪問(wèn)順序，然后根據(jù)節(jié)點(diǎn)序列生成樹結(jié)構(gòu)。該方法在遍歷算法的執(zhí)行過(guò)程中，每個(gè)節(jié)點(diǎn)至少被訪問(wèn)2次，并且需要從數(shù)據(jù)庫(kù)中頻繁地檢索節(jié)點(diǎn)信息，當(dāng)節(jié)點(diǎn)數(shù)量較多的時(shí)候，其算法執(zhí)行的耗時(shí)比較長(zhǎng)，導(dǎo)致效率低下。(2)層點(diǎn)展開法，使用Javascript函數(shù)監(jiān)聽鼠標(biāo)對(duì)樹節(jié)點(diǎn)的單擊，觸發(fā)異步傳輸技術(shù)(AJAX)加載子節(jié)點(diǎn)的事件，以實(shí)現(xiàn)展開或隱藏子節(jié)點(diǎn)。該方法應(yīng)用比較廣泛，生成樹結(jié)構(gòu)的效率較高，由于該方法是逐層展開樹分支，因此在訪問(wèn)子樹節(jié)點(diǎn)方面存在不足。(3)多表存儲(chǔ)法，按照樹結(jié)構(gòu)的層次關(guān)系，分別為每一層的節(jié)點(diǎn)創(chuàng)建數(shù)據(jù)表并實(shí)現(xiàn)“一對(duì)多的關(guān)聯(lián)”，依次從各層的數(shù)據(jù)表中取出節(jié)點(diǎn)即可生成樹結(jié)構(gòu)。該技術(shù)由于數(shù)據(jù)表數(shù)量的限制，因此在樹的層次伸展方面受到了約束。

綜上多種實(shí)現(xiàn)樹形結(jié)構(gòu)方法存在的問(wèn)題，可通過(guò)路徑存儲(chǔ)法進(jìn)行改進(jìn)。該方法使用節(jié)點(diǎn)排序法為技術(shù)路線，在數(shù)據(jù)表中設(shè)置一個(gè)字段用于存儲(chǔ)樹節(jié)點(diǎn)的路徑，由數(shù)據(jù)庫(kù)排序檢索產(chǎn)生的節(jié)點(diǎn)序列來(lái)創(chuàng)建樹形結(jié)構(gòu)。

1 路徑存儲(chǔ)法創(chuàng)建樹結(jié)構(gòu)

1.1 相關(guān)定義及性質(zhì)

定義1 路徑存儲(chǔ)法是從樹根節(jié)點(diǎn)出發(fā)，樹中某一節(jié)點(diǎn)為終點(diǎn)，沿這一路徑中的線性結(jié)構(gòu)，把各節(jié)點(diǎn)依次組合而成的字符串存儲(chǔ)在數(shù)據(jù)表特定字段中的方法。例:在圖1中的節(jié)點(diǎn)I的路徑可以表示為A，B，F(xiàn)，I。

圖1 樹形結(jié)構(gòu)層次結(jié)構(gòu)關(guān)系

從數(shù)學(xué)的角度分析，路徑可以定義為一個(gè)集合對(duì):P=(V，E)，其中V是節(jié)點(diǎn)的非空有限集合，E是邊的集合，集合E的勢(shì)為節(jié)點(diǎn)的深度，記為。根據(jù)路徑存儲(chǔ)法的定義，結(jié)合樹形結(jié)構(gòu)，可以得出以下性質(zhì):

性質(zhì) 1 在一棵樹 T={P1，P2，…，Pi，…，Pn}中，對(duì)?Vi和 Vj(i，j=1，2，3，…，n 且 i≠j)，有 Vi∩Vj≠?。

證明 由樹結(jié)構(gòu)的定義，在一棵樹中，所有節(jié)點(diǎn)是樹根節(jié)點(diǎn) Pk的后裔，又 Pi∈T，Pj∈T，則有 vk∈Vi，vk∈Vj，因此至少存在集合{vk}，使得 Vi∩Vj={vk}，命題得證。

推論 V1∩V2=?，則節(jié)點(diǎn)P1和P2不在同一棵樹中。

性質(zhì) 2 在樹 T={P1，P2，…，Pi，…，Pn}中，節(jié)點(diǎn)P1，P2，若 V1∩V2=V1，則 P1是 P2的先驅(qū)節(jié)點(diǎn)。

證明 由定義1可知，每一個(gè)樹的節(jié)點(diǎn)路徑由其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)直到樹根節(jié)點(diǎn)所組成的一個(gè)集合，再由樹結(jié)構(gòu)的定義，一棵樹的節(jié)點(diǎn)只能有一個(gè)父節(jié)點(diǎn)，因此，后裔節(jié)點(diǎn)必然按照其先驅(qū)節(jié)點(diǎn)進(jìn)行展開，所以，后裔節(jié)點(diǎn)路徑中的元素一定有前驅(qū)節(jié)點(diǎn)元素組成的集合，由此可得V1∩V2=V1，則P1是P2的先驅(qū)節(jié)點(diǎn)，反之，若P1是P2的先驅(qū)節(jié)點(diǎn)，則V1∩V2=V1。

定義2(葉子節(jié)點(diǎn)) 在一棵樹 T={P1，P2，…，Pi，…，Pn}中，對(duì)?Vi(i=1，2，…，n)，有 Vj?Vi(j≤n，i≠j)，則節(jié)點(diǎn) Pi是葉子節(jié)點(diǎn)。

定義3(樹的深度) 在一棵樹 T={P1，P2，…，Pi，…，Pn}中，樹的深度為 max(|Ei|)，其中 i≤n。

定義4(節(jié)點(diǎn)深度) 節(jié)點(diǎn)Pi(i≤n)的深度為。

定義5(樹根節(jié)點(diǎn)) 在樹 T={P1，P2，…，Pi，…，Pn}中，滿足條件|Ei|=1的節(jié)點(diǎn)是樹根節(jié)點(diǎn)。

1.2 設(shè)計(jì)存儲(chǔ)節(jié)點(diǎn)的關(guān)系表

生成動(dòng)態(tài)樹結(jié)構(gòu)，需要有提供樹節(jié)點(diǎn)信息的數(shù)據(jù)支撐。根據(jù)路徑存儲(chǔ)法的定義，在數(shù)據(jù)庫(kù)中設(shè)計(jì)一個(gè)關(guān)系數(shù)據(jù)表，用于存放各節(jié)點(diǎn)的信息，其結(jié)構(gòu)如表1所示。

表1 存放樹節(jié)點(diǎn)信息的數(shù)據(jù)表結(jié)構(gòu)

數(shù)據(jù)表中節(jié)點(diǎn)編號(hào)(id)為主鍵，根據(jù)節(jié)點(diǎn)編號(hào)值在數(shù)據(jù)表中的唯一性這一特點(diǎn)，因此在存儲(chǔ)樹節(jié)點(diǎn)信息時(shí)，設(shè)置路徑信息由節(jié)點(diǎn)編號(hào)值組成，各編號(hào)之間逗號(hào)分隔，并將這些編號(hào)和逗號(hào)連接成字符串，存儲(chǔ)到節(jié)點(diǎn)路徑字段中。這種方式組成的路徑值，可以保證節(jié)點(diǎn)路徑的準(zhǔn)確性。

1.3 生成動(dòng)態(tài)樹結(jié)構(gòu)的原理

在J2EE工程中創(chuàng)建Java類，使之與節(jié)點(diǎn)信息建立對(duì)象關(guān)系映射(ORM)，然后在工程中設(shè)計(jì)出數(shù)據(jù)事務(wù)處理類，用于對(duì)節(jié)點(diǎn)信息實(shí)現(xiàn)在數(shù)據(jù)表中添加、修改、刪除和檢索節(jié)點(diǎn)信息等方法，在類中創(chuàng)建一個(gè)返回值為節(jié)點(diǎn)對(duì)象集合的函數(shù)，函數(shù)中使用以路徑為排序依據(jù)的數(shù)據(jù)庫(kù)查詢語(yǔ)句，查詢結(jié)果的每一個(gè)數(shù)據(jù)項(xiàng)對(duì)節(jié)點(diǎn)對(duì)象進(jìn)行初始化，并按照結(jié)果的序列將對(duì)象添加到集合中，用于為生成樹結(jié)構(gòu)的程序提供數(shù)據(jù)。

生成樹形結(jié)構(gòu)的過(guò)程中，依次取出底層數(shù)據(jù)事務(wù)對(duì)象提供的節(jié)點(diǎn)信息，依據(jù)節(jié)點(diǎn)路徑中的逗號(hào)數(shù)量，計(jì)算出該節(jié)點(diǎn)在樹中的深度，由此控制節(jié)點(diǎn)在樹形圖中的縮進(jìn)位置。根據(jù)節(jié)點(diǎn)的相關(guān)定義和性質(zhì)，判定得出節(jié)點(diǎn)名稱前的顯示圖標(biāo)。

為呈現(xiàn)樹形圖和實(shí)現(xiàn)樹節(jié)點(diǎn)的展開和收縮狀態(tài)，可以在HTML中使用表格嵌套的方式裝載樹節(jié)點(diǎn)(見圖2)，設(shè)計(jì)出對(duì)節(jié)點(diǎn)名稱前的圖標(biāo)添加鼠標(biāo)點(diǎn)擊的JS事件，當(dāng)點(diǎn)擊圖標(biāo)時(shí)觸發(fā)JS函數(shù)，調(diào)用函數(shù)執(zhí)行后，以實(shí)現(xiàn)隱藏或顯示裝載子樹的表格。

圖2 網(wǎng)頁(yè)中表格嵌套布局設(shè)計(jì)

2 應(yīng)用實(shí)例

在MyEclipse開發(fā)平臺(tái)上，結(jié)合MySQL數(shù)據(jù)庫(kù)，為某高校開發(fā)學(xué)生學(xué)籍卡管理系統(tǒng)，設(shè)計(jì)要求系統(tǒng)能直觀展示出二級(jí)學(xué)院、專業(yè)、年級(jí)、班級(jí)等層次信息，操作中點(diǎn)擊節(jié)點(diǎn)信息能顯示出相應(yīng)的學(xué)生信息。需求中的教學(xué)組織機(jī)構(gòu)就是一個(gè)樹結(jié)構(gòu)，為此，設(shè)計(jì)了教學(xué)機(jī)構(gòu)信息表(機(jī)構(gòu)編號(hào)N(4)，機(jī)構(gòu)名稱C(50)，路徑信息C(50))和學(xué)生信息數(shù)據(jù)表(學(xué)號(hào)C(12)，姓名C(10)，性別C(2)，…，機(jī)構(gòu)編號(hào) N(4))，使用教學(xué)機(jī)構(gòu)數(shù)據(jù)表中的機(jī)構(gòu)編號(hào)與學(xué)生信息表的機(jī)構(gòu)編號(hào)建立一對(duì)多的聯(lián)系，圖3顯示了教學(xué)機(jī)構(gòu)信息表和學(xué)生信息表的部分?jǐn)?shù)據(jù)和它們的關(guān)系。

圖3 教學(xué)機(jī)構(gòu)表和學(xué)生信息表之間的關(guān)系圖

2.1 創(chuàng)建節(jié)點(diǎn)信息類

在J2EE工程中創(chuàng)建節(jié)點(diǎn)信息類(NodeInfo)，該類的對(duì)象由機(jī)構(gòu)信息表中的數(shù)據(jù)進(jìn)行初始化，用于生成樹結(jié)構(gòu)的事務(wù)中為程序提供數(shù)據(jù)支持，其屬性主要有節(jié)點(diǎn)編號(hào)、節(jié)點(diǎn)名稱、節(jié)點(diǎn)深度等，并設(shè)置各屬性的Set和Get方法，用于提取對(duì)象的屬性值。以下程序給出了節(jié)點(diǎn)信息對(duì)象的初始化方法:

以上程序中，實(shí)現(xiàn)了節(jié)點(diǎn)信息類的構(gòu)造函數(shù)，其中的路徑參數(shù)用于取節(jié)點(diǎn)的深度，由定義3得之，該節(jié)點(diǎn)的深度為路徑中的逗號(hào)的數(shù)量。

2.2 教學(xué)機(jī)構(gòu)節(jié)點(diǎn)排序的實(shí)現(xiàn)

使用路徑存儲(chǔ)的方式存儲(chǔ)樹節(jié)點(diǎn)信息，可以由路徑升序的查詢方式，快速地檢索出數(shù)據(jù)表中存放的節(jié)點(diǎn)信息，并且檢索出的結(jié)果節(jié)點(diǎn)序列符合生成樹結(jié)構(gòu)的條件。

設(shè)計(jì)SQL查詢語(yǔ)句為“select*from dept_info order by path asc”，該語(yǔ)句實(shí)現(xiàn)對(duì)節(jié)點(diǎn)信息的排序檢索，程序執(zhí)行查詢后，得到圖4所示的結(jié)果。

圖4 樹節(jié)點(diǎn)排序檢索結(jié)果圖

在J2EE工程中創(chuàng)建與數(shù)據(jù)庫(kù)連接的環(huán)境，通過(guò)JDBC實(shí)現(xiàn)對(duì)數(shù)據(jù)的訪問(wèn)，在程序中定義節(jié)點(diǎn)信息類的集合(List＜NodeInfo＞)，在查詢的結(jié)果中依次取出每一條數(shù)據(jù)，該數(shù)據(jù)初始化節(jié)點(diǎn)信息對(duì)象后，添加到集合中，實(shí)現(xiàn)了對(duì)樹節(jié)點(diǎn)信息的排序。

2.3 樹形教學(xué)機(jī)構(gòu)的實(shí)現(xiàn)

按照節(jié)點(diǎn)信息集合的序列，依次取出集合中的對(duì)象，并將該對(duì)象的信息裝載到網(wǎng)頁(yè)元素中，通過(guò)Web服務(wù)器對(duì)動(dòng)態(tài)網(wǎng)頁(yè)的解析，生成相應(yīng)的HTML，從而在客戶端瀏覽器中可以直觀查看到樹形結(jié)構(gòu)。實(shí)現(xiàn)樹結(jié)構(gòu)的主要程序代碼如下:

2.4 使用路徑存儲(chǔ)法的優(yōu)勢(shì)分析

在學(xué)生學(xué)籍卡管理系統(tǒng)中應(yīng)用路徑存儲(chǔ)法，生成高校教學(xué)機(jī)構(gòu)的樹形圖，通過(guò)系統(tǒng)的開發(fā)與運(yùn)行，表現(xiàn)出的優(yōu)勢(shì)主要體現(xiàn)在以下方面:

(1)優(yōu)化了數(shù)據(jù)庫(kù)的設(shè)計(jì)。傳統(tǒng)的多表關(guān)聯(lián)技術(shù)，在設(shè)計(jì)數(shù)據(jù)表時(shí)，根據(jù)層次信息，需要用到存儲(chǔ)二級(jí)學(xué)院信息、專業(yè)信息、年級(jí)信息和班級(jí)信息等4張數(shù)據(jù)表，并且在學(xué)生信息表中需要添加這4個(gè)表的主鍵字段與之建立關(guān)聯(lián)。從圖3的結(jié)構(gòu)可以看出，使用樹結(jié)構(gòu)的方式存儲(chǔ)機(jī)構(gòu)信息，用2張數(shù)據(jù)表就可以滿足要求。

(2)提高了檢索子樹節(jié)點(diǎn)的效率。結(jié)合圖3中的數(shù)據(jù)可以看出，若要顯示計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生信息，只需要執(zhí)行以下SQL查詢操作就可以得到學(xué)生數(shù)據(jù):

select*from學(xué)生信息表where id in(select id from機(jī)構(gòu)信息表 where path like‘1，2，%’)

其中的“select id from機(jī)構(gòu)信息表where path like‘1，2，%’”子句，實(shí)現(xiàn)了快速查找到該節(jié)點(diǎn)的所有子樹節(jié)點(diǎn)。該方式與自關(guān)聯(lián)方式的數(shù)據(jù)表存儲(chǔ)樹節(jié)點(diǎn)的方式相比，在自關(guān)聯(lián)數(shù)據(jù)表的存儲(chǔ)結(jié)構(gòu)中，查找子樹節(jié)點(diǎn)需要使用樹的遍歷算法，算法執(zhí)行中則要頻繁地執(zhí)行查詢子節(jié)點(diǎn)或兄弟節(jié)點(diǎn)信息的操作，容易得知，當(dāng)樹節(jié)點(diǎn)數(shù)量較大的時(shí)候，其耗時(shí)較長(zhǎng)。由此，該技術(shù)在查找子樹節(jié)點(diǎn)方面也有著明顯的優(yōu)勢(shì)。

3 結(jié)束語(yǔ)

本文分析了多種生成樹形結(jié)構(gòu)的方法，以樹節(jié)點(diǎn)在關(guān)系數(shù)據(jù)庫(kù)的存儲(chǔ)方式為視角，給出了樹節(jié)點(diǎn)的性質(zhì)和相關(guān)定義，提出使用路徑存儲(chǔ)的方式將樹節(jié)點(diǎn)保存在數(shù)據(jù)庫(kù)中，并將該技術(shù)應(yīng)用在某高校學(xué)生學(xué)籍卡管理系統(tǒng)的學(xué)生組織機(jī)構(gòu)模塊。學(xué)籍卡系統(tǒng)運(yùn)行結(jié)果表明，路徑存儲(chǔ)法能在超大量節(jié)點(diǎn)存儲(chǔ)狀態(tài)中，快速檢索教學(xué)組織機(jī)構(gòu)的子樹節(jié)點(diǎn)，并根據(jù)搜索到的結(jié)果快速查找到學(xué)生信息。該方法實(shí)施起來(lái)簡(jiǎn)單容易，對(duì)現(xiàn)有B/S系統(tǒng)的樹結(jié)構(gòu)模塊改進(jìn)具有一定的實(shí)用性。

［1］陳潔，張燕平，趙姝.一種結(jié)構(gòu)化描述方法:保序性與或圖［J］.南京大學(xué)學(xué)報(bào):自然科學(xué)版，2013，49(2):235-243.

［2］張嘉惠，崔超艷.樹形WBS在科研項(xiàng)目管理系統(tǒng)中的應(yīng)用［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2012，21(4):23-26.

［3］呂剛，蔣勇銘，王軍.基于關(guān)系型數(shù)據(jù)庫(kù)的樹形結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)光盤軟件與應(yīng)用，2112(17):224-225.

［4］魏斌，馬繼輝，?；?基于遞歸算法的樹型結(jié)構(gòu)圖的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)應(yīng)用與軟件，2011，28(1):96-98.

［5］李俊飛，陳皓，趙衛(wèi)東.樹形結(jié)構(gòu)數(shù)據(jù)輸入輸出控件的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，32(9):3054-3058.

［6］張華興，孫毅，單繼宏.網(wǎng)頁(yè)樹形結(jié)構(gòu)自動(dòng)生成研究［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2009，18(7):61-66.

［7］李睿，曾俊瑀，周四望.基于局部標(biāo)簽樹匹配的改進(jìn)網(wǎng)頁(yè)聚類算法［J］.計(jì)算機(jī)應(yīng)用，2010，30(3):818-820.

［8］魏紀(jì)東，王昭順，戴桂蘭，等.樹形結(jié)構(gòu)數(shù)據(jù)幀解析和處理［J］.小型微型計(jì)算機(jī)系統(tǒng)，2010，31(12):2252-2254.

［9］Marco Di Summa，Andrea Grosso，Marco Locatelli.Complexity of the critical node problem over trees［J］.Computers＆ Operations Research，2011，38(12):1766-1774.

［10］Coudert David，Huc Florian，Mazauric Dorian.A distributed algorithm for computing the node search number in trees［J］.Algorithmica，2012，63(2):158-190.

［11］Dunren Che.An efficient algorithm for tree pattern query minimization under broad integrity constraints［J］.International Journal of Web Information Systems，2007，24(3):103-118.

［12］Yuge T，Tagami K，Yanagi S.Calculating top event probability of a fault tree with many repeated events［J］.Journal of Quality in Maintenance Engineering，2006，33(4):1126-1153.

［13］Han K，F(xiàn)eng Y T，Owen D R J.Performance comparisons of tree-based and cell-based contact detection algorithms［J］.Engineering Computations，2007，30(2):247-261.

［14］Alfred V Aho，John E Hopcroft，Jeffrey D Ullman.The Design and Analysis of Computer Algorithms［M］.Addison Wesley/Pearson，2005.