基于編碼的ＴｒｅｅＶｉｅｗ控件節點生成算法

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

關鍵詞：TreeView；生成樹；編碼

中圖分類號：TP312 文獻標識碼：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 引言

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

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

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

因此，我們提出了一種基于編碼的TreeView控件節點樹生成算法來改進傳統的生成樹算法。

2 基于編碼的TreeView控件節點生成算法

2.1 編碼

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

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

2.2 基于編碼的TreeView控件節點生成算法的基本思想

在管理信息系統開發過程中，為了解決TreeView控件節點生成算法中的遞歸算法存在的問題對程序性能帶來的負面影響，我們利用編碼提出了新的算法，即基于編碼的TreeView控件節點生成算法。該算法的結構圖如圖1。

基于編碼的TreeView控件節點生成算法的基本思想主要體現在：

1) 根據過濾條件，通過數據讀取器DataReader，將數據庫中的樹節點記錄取出；

2) 使用ADO.NET組件中的DataSet來存儲取出的樹節點記錄；

3) 采用基于編碼的TreeView控件節點生成算法將數據集中的節點信息構建樹。

采用此算法的優越性在于：通過線性遍歷數據集去生成樹節點，不用遞歸算法，進而大大提高了數據的查找效率和程序的執行效率。

2.3 基于編碼的TreeView控件節點生成算法設計

2.3.1 數據庫設計

靜態樹形圖是由開發人員根據系統數據結構的需要在編寫代碼時生成，若樹形圖的結構發生改變，則需修改系統的源代碼，將對系統的維護帶來麻煩。為此，借助數據庫來保存樹形圖的節點信息，借助TreeView控件實現動態樹形圖，當節點信息發生改變時，只須維護數據庫而無須修改源代碼。當然，這種節點信息數據庫的結構需精心設計才能滿足需要，數據庫的設計對目錄樹的生成起著至關重要的作用， 數據庫設計的合理與否， 直接影響到生成算法的復雜度。

為此，我們設定數據庫中節點信息表結構如表1（用SQL Server2005 對數據庫進行設計）。

對應的節點信息表示例如表2。

其中ID的值域遵守“編碼”規范。

2.3.2 算法思想

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

定義2：NodeDataSet是樹節點記錄的全集，設樹節點記錄ri（0≤i≤n-1）是NodeDataSet集合中的元素，即樹結點集合中的第i條紀錄，則有?坌ri（ri∈NodeDataSet）

定義3：Count是樹節點記錄的全集NodeDataSet中的記錄個數的總數，則第i條紀錄ri 中的i的取值范圍是：0≤i≤Count-1。

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

定義5：P表示 TreeView 控件中的節點，是一個節點變量，用于暫存父節點。

定義6：Length（Name（P））是節點P的名字的長度，簡記為L（Name（P））。

算法流程圖如圖2所示。

2.3.3 算法設計

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

1）連接數據庫ConnetionDatabase（）：建立雙向通信機制，使數據能從數據庫中引入應用程序，并且也能更改發回數據庫。

2）Parameter（contion，key）：初始化數據檢索參數，使數據可以按關鍵字key升序排列。

3）GetNode（Parameter）：根據參數從數據庫讀取樹節點信息。

4）NodeDataSet（GetNode）：把讀取到樹節點信息存入數據集中。

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

3 測試與分析

3.1 算法復雜度分析

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

3.2 算法優越性

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

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

4 結束語

本文分析了現有TreeView控件節點生成算法，提出了一種基于編碼的TreeView控件樹節點生成算法模型，給出了基于編碼的TreeView控件樹節點生成算法。通過實驗證明，利用基于編碼的TreeView控件樹節點生成算法可以很好的降低節點生成時間，進而提高代碼的執行效率。

參考文獻：

[1] 馮玉才.數據庫系統基礎[M].武漢:華中理工大學出版社，1993.

[2] 李昭原，羅曉沛.數據庫技術新進展[M].北京: 清華大學出版社，1997:1-5.

[3] 陳松喬.算法與數據結構(C與C++描述)[M].清華大學出版社，2002.

[4] 王喜珍，陳步云. 基于樹形結構的地震數據庫系統設計方法[J].地震學報，2005，27(1):96-101.

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

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

[7] 崔曉陽.用Treeview控件實現樹形管理信息系統[J].農業網絡信息，2007(11):47-48.