基于編碼的ＴｒｅｅＶｉｅｗ控件節(jié)點(diǎn)生成算法

摘要：針對TreeView控件節(jié)點(diǎn)生成算法的現(xiàn)狀，該文分析了現(xiàn)有TreeView控件節(jié)點(diǎn)動態(tài)生成算法中的遞歸算法，提出一種基于編碼的TreeView控件樹節(jié)點(diǎn)生成算法，并解決了TreeView控件節(jié)點(diǎn)動態(tài)生成算法中可能出現(xiàn)的斷層現(xiàn)象和遞歸算法效率低下的問題。

關(guān)鍵詞：TreeView；生成樹；編碼

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2009)04-0847-02

Node Generating Algorithm of TreeView Control Basing on Code

LI Jun-feng， FANG Ming

(School of Computer Science， Xi'an Shiyou University， Xi'an 710065)

Abstract: According to the Node Generating Algorithm of TreeView Control at present， this article analyzes the current Recursive algorithm of Node Generating Algorithm of TreeView Control，puts forward the Node Generating Algorithm of TreeView Control basing on code，and solves the low rate of Recursive algorithm or the node loss which may exists in the Node Generating Algorithm of TreeView Control.

Keywords: treeView; generating tree; code

1 引言

樹形結(jié)構(gòu)是數(shù)據(jù)理論中用來描述復(fù)雜的層次關(guān)系時使用的一個重要概念，TreeView(樹形控件)則是其在高級開發(fā)語言中的表現(xiàn)形式。Windows窗體TreeView 控件以類似于在 Windows 操作系統(tǒng)的 Windows 資源管理器左窗格中顯示文件和文件夾的方式顯示節(jié)點(diǎn)的層次結(jié)構(gòu)。TreeView 控件的主要特點(diǎn)是能夠比較清晰地實(shí)現(xiàn)分類、導(dǎo)航、瀏覽等功能。因而，樹形結(jié)構(gòu)的設(shè)計(jì)就成了軟件開發(fā)人員一個永恒的話題，它的使用方法與編程技巧也一直受到技術(shù)人員的關(guān)注。一般來講，我們的應(yīng)用程序多數(shù)是基于數(shù)據(jù)庫的。采用這種方式，增加、修改、刪除一顆樹的節(jié)點(diǎn)很方便，只要操作數(shù)據(jù)庫中的數(shù)據(jù)就可以了。而且，這種方式可以和數(shù)據(jù)庫中的其它表做關(guān)聯(lián)、查詢和匯總，通過設(shè)計(jì)視圖或存儲過程，很容易查詢出你想要的相關(guān)數(shù)據(jù)。傳統(tǒng)的樹形結(jié)構(gòu)的展示方式的主要思想是：從數(shù)據(jù)庫中得到數(shù)據(jù)（在.NET中，我們可以理解為一個數(shù)據(jù)集），建立樹形結(jié)構(gòu)。這種方式通過父子關(guān)系遞歸生成樹，是最容易理解的一種編程實(shí)現(xiàn)方式。一般是自頂向下遞歸生成，得到廣泛應(yīng)用。然而，采用這種方式展示樹型結(jié)構(gòu)會出現(xiàn)兩個比較明顯的缺點(diǎn)：

1）由于采用遞歸算法編寫的程序，運(yùn)行時需要占用系統(tǒng)堆棧，所以內(nèi)存消耗要比非遞歸代碼要大很多，循環(huán)是O(1)的空間復(fù)雜度，而對于遞歸（不考慮尾遞歸優(yōu)化的情況），每次函數(shù)調(diào)用都要壓棧，那么空間復(fù)雜度是O(n)，和遞歸次數(shù)呈線性關(guān)系，如果遞歸深度太大，可能系統(tǒng)撐不住，因此遞歸的效率就低下了。

2）“由父節(jié)點(diǎn)及子節(jié)點(diǎn)”的遍歷順序意味著每個子節(jié)點(diǎn)的父節(jié)點(diǎn)必須存在，否則將搜索不到，即可能出現(xiàn)斷層現(xiàn)象。

因此，我們提出了一種基于編碼的TreeView控件節(jié)點(diǎn)樹生成算法來改進(jìn)傳統(tǒng)的生成樹算法。

2 基于編碼的TreeView控件節(jié)點(diǎn)生成算法

2.1 編碼

編碼是由n（n≥0）個阿拉伯?dāng)?shù)字組成的有限序列。編碼一般記作S=“S0， S1，…， Sn-1”其中S稱為編碼名，n稱為編碼的長度，雙引號括起來的數(shù)字序列稱為編碼的值，每個數(shù)字Si（0≤i＜n）可以是任意的阿拉伯?dāng)?shù)字。

子孫編碼，對于一個編碼Sp（Sp=“S0， S1，…， Sn-1”），如果編碼Sc（Sc=“S0， S1，…， Sm-1”）是Sp的子孫編碼，則Sc中S0 S1… Si（i

2.2 基于編碼的TreeView控件節(jié)點(diǎn)生成算法的基本思想

在管理信息系統(tǒng)開發(fā)過程中，為了解決TreeView控件節(jié)點(diǎn)生成算法中的遞歸算法存在的問題對程序性能帶來的負(fù)面影響，我們利用編碼提出了新的算法，即基于編碼的TreeView控件節(jié)點(diǎn)生成算法。該算法的結(jié)構(gòu)圖如圖1。

基于編碼的TreeView控件節(jié)點(diǎn)生成算法的基本思想主要體現(xiàn)在：

1) 根據(jù)過濾條件，通過數(shù)據(jù)讀取器DataReader，將數(shù)據(jù)庫中的樹節(jié)點(diǎn)記錄取出；

2) 使用ADO.NET組件中的DataSet來存儲取出的樹節(jié)點(diǎn)記錄；

3) 采用基于編碼的TreeView控件節(jié)點(diǎn)生成算法將數(shù)據(jù)集中的節(jié)點(diǎn)信息構(gòu)建樹。

采用此算法的優(yōu)越性在于：通過線性遍歷數(shù)據(jù)集去生成樹節(jié)點(diǎn)，不用遞歸算法，進(jìn)而大大提高了數(shù)據(jù)的查找效率和程序的執(zhí)行效率。

2.3 基于編碼的TreeView控件節(jié)點(diǎn)生成算法設(shè)計(jì)

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

靜態(tài)樹形圖是由開發(fā)人員根據(jù)系統(tǒng)數(shù)據(jù)結(jié)構(gòu)的需要在編寫代碼時生成，若樹形圖的結(jié)構(gòu)發(fā)生改變，則需修改系統(tǒng)的源代碼，將對系統(tǒng)的維護(hù)帶來麻煩。為此，借助數(shù)據(jù)庫來保存樹形圖的節(jié)點(diǎn)信息，借助TreeView控件實(shí)現(xiàn)動態(tài)樹形圖，當(dāng)節(jié)點(diǎn)信息發(fā)生改變時，只須維護(hù)數(shù)據(jù)庫而無須修改源代碼。當(dāng)然，這種節(jié)點(diǎn)信息數(shù)據(jù)庫的結(jié)構(gòu)需精心設(shè)計(jì)才能滿足需要，數(shù)據(jù)庫的設(shè)計(jì)對目錄樹的生成起著至關(guān)重要的作用， 數(shù)據(jù)庫設(shè)計(jì)的合理與否， 直接影響到生成算法的復(fù)雜度。

為此，我們設(shè)定數(shù)據(jù)庫中節(jié)點(diǎn)信息表結(jié)構(gòu)如表1（用SQL Server2005 對數(shù)據(jù)庫進(jìn)行設(shè)計(jì)）。

對應(yīng)的節(jié)點(diǎn)信息表示例如表2。

其中ID的值域遵守“編碼”規(guī)范。

2.3.2 算法思想

定義1：Parameter（contion（key））是數(shù)據(jù)庫查詢的參數(shù)初始化方法，簡記P（contion（key）），其中，contion為以關(guān)鍵字key升序排序數(shù)據(jù)紀(jì)錄的參數(shù)初始化方法，則以P（contion（key））初始化參數(shù)后查詢的數(shù)據(jù)集合是以關(guān)鍵字key升序排列的。

定義2：NodeDataSet是樹節(jié)點(diǎn)記錄的全集，設(shè)樹節(jié)點(diǎn)記錄ri（0≤i≤n-1）是NodeDataSet集合中的元素，即樹結(jié)點(diǎn)集合中的第i條紀(jì)錄，則有?坌ri（ri∈NodeDataSet）

定義3：Count是樹節(jié)點(diǎn)記錄的全集NodeDataSet中的記錄個數(shù)的總數(shù)，則第i條紀(jì)錄ri 中的i的取值范圍是：0≤i≤Count-1。

定義4：Lengthi（key）是第i條紀(jì)錄中關(guān)鍵字為key的字段的值的字符串的長度，則0≤Lengthi（key）≤n，Lengthi（key）簡記為Li（key）。

定義5：P表示 TreeView 控件中的節(jié)點(diǎn)，是一個節(jié)點(diǎn)變量，用于暫存父節(jié)點(diǎn)。

定義6：Length（Name（P））是節(jié)點(diǎn)P的名字的長度，簡記為L（Name（P））。

算法流程圖如圖2所示。

2.3.3 算法設(shè)計(jì)

根據(jù)算法思想，從算法中抽取出的方法有：連接數(shù)據(jù)庫ConnetionDatabase（），初始化參數(shù)，根據(jù)參數(shù)讀取樹節(jié)點(diǎn)信息，把樹節(jié)點(diǎn)信息存入NodeDataSet，遍歷NodeDataSet，并把NodeDataSet中的節(jié)點(diǎn)數(shù)據(jù)根據(jù)算法添加到數(shù)控件TreeView中。

1）連接數(shù)據(jù)庫ConnetionDatabase（）：建立雙向通信機(jī)制，使數(shù)據(jù)能從數(shù)據(jù)庫中引入應(yīng)用程序，并且也能更改發(fā)回?cái)?shù)據(jù)庫。

2）Parameter（contion，key）：初始化數(shù)據(jù)檢索參數(shù)，使數(shù)據(jù)可以按關(guān)鍵字key升序排列。

3）GetNode（Parameter）：根據(jù)參數(shù)從數(shù)據(jù)庫讀取樹節(jié)點(diǎn)信息。

4）NodeDataSet（GetNode）：把讀取到樹節(jié)點(diǎn)信息存入數(shù)據(jù)集中。

5）BuildTree（NodeDataSet）：按照流程圖中的方法遍歷數(shù)據(jù)集，生成樹。

3 測試與分析

3.1 算法復(fù)雜度分析

該算法利用數(shù)據(jù)集與樹結(jié)點(diǎn)順序的一致性， 對數(shù)據(jù)庫進(jìn)行一次查詢，一次遍歷，對數(shù)據(jù)集進(jìn)行逐條讀取， 逐條添加。在程序中只存在一個循環(huán)，時間復(fù)雜度為O(n)。該算法實(shí)現(xiàn)了對數(shù)據(jù)表進(jìn)行一次遍歷即可添加所有結(jié)點(diǎn)。

3.2 算法優(yōu)越性

由于SQL 語句的執(zhí)行效率很高，可以把一些復(fù)雜的工作交給SQL 去執(zhí)行，例如權(quán)限的判斷等，而應(yīng)用程序的執(zhí)行效率就沒有這么高了。因此應(yīng)該盡量減少由應(yīng)用程序去執(zhí)行SQL 的次數(shù)，縮短執(zhí)行的時間。 基于編碼的TreeView控件節(jié)點(diǎn)生成算法就很好的解決了這一問題。 傳統(tǒng)的遞歸算法需要進(jìn)行與結(jié)點(diǎn)個數(shù)相同次數(shù)的數(shù)據(jù)庫查詢和遞歸調(diào)用，而基于編碼的TreeView控件節(jié)點(diǎn)生成算法只需執(zhí)行一次SQL 語句對查詢結(jié)果進(jìn)行一次遍歷就可以添加所有樹結(jié)點(diǎn)，大大縮短了生成樹的時間。而且程序的流程也非常清晰， 不需要用到遞歸調(diào)用， 增加了程序的可讀性。

針對遞歸算法和基于編碼的TreeView控件節(jié)點(diǎn)樹生成算法分別對含有100、200、300、400、500、1000個測試節(jié)點(diǎn)的情況進(jìn)行樹生成過程的執(zhí)行時間的測試，對實(shí)驗(yàn)結(jié)果求平均值，得到以下結(jié)果，參見表3。

4 結(jié)束語

本文分析了現(xiàn)有TreeView控件節(jié)點(diǎn)生成算法，提出了一種基于編碼的TreeView控件樹節(jié)點(diǎn)生成算法模型，給出了基于編碼的TreeView控件樹節(jié)點(diǎn)生成算法。通過實(shí)驗(yàn)證明，利用基于編碼的TreeView控件樹節(jié)點(diǎn)生成算法可以很好的降低節(jié)點(diǎn)生成時間，進(jìn)而提高代碼的執(zhí)行效率。

參考文獻(xiàn)：

[1] 馮玉才.數(shù)據(jù)庫系統(tǒng)基礎(chǔ)[M].武漢:華中理工大學(xué)出版社，1993.

[2] 李昭原，羅曉沛.數(shù)據(jù)庫技術(shù)新進(jìn)展[M].北京: 清華大學(xué)出版社，1997:1-5.

[3] 陳松喬.算法與數(shù)據(jù)結(jié)構(gòu)(C與C++描述)[M].清華大學(xué)出版社，2002.

[4] 王喜珍，陳步云. 基于樹形結(jié)構(gòu)的地震數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)方法[J].地震學(xué)報，2005，27(1):96-101.

[5] 向隅.Delphi7中Treeview控件的應(yīng)用[J].武漢船舶職業(yè)技術(shù)學(xué)院學(xué)報，2008(1):11-12.

[6] 王志國.在.NET環(huán)境下用Treeview遍歷活動目錄[J].電腦編程技巧與維護(hù)，2008(2):13-15.

[7] 崔曉陽.用Treeview控件實(shí)現(xiàn)樹形管理信息系統(tǒng)[J].農(nóng)業(yè)網(wǎng)絡(luò)信息，2007(11):47-48.