一、引言
在應用系統開發中，treeview是一種使用頻率很高的控件。它的主要特點是能夠比較清晰地實現分類、導航、瀏覽等功能。因而，它的使用方法與編程技巧也一直受到技術人員的關注。隨著應用需求的變化，在很多情況下我們需要實現數據顯示的權限控制，即用戶看到的數據是經過過濾的，或是連續值，或是一些離散的值。就treeview而言，原先可能顯示出來的是完整的具有嚴格父子關系得節點集，而經權限過濾后所要顯示的節點可能會變得離散，不再有完整的繼承關系。本文針對這一問題，通過對已有實現方法進行分析，提出改進算法。所附示例程序進一步解釋了算法設計思想。
二、三種常見生成方式的簡單分析
如文[2,3]所述，treeview的生成基本上有三種方式：
1. 界面設計時在treeview設計器或者代碼中直接填充treeview節點。
這種方式通過拖放控件的方式生成樹，應用范圍窄，是一種非編程方式；
2. 從xml文件中建立樹形結構。
這種方式通過xml文件(串)生成樹，從形式上來說，這種方式是比較直觀的。因為xml本身就是一棵“樹”，在.net 平臺下treeview的自動生成代碼中，treeview的實際內容也是由xml表示的。此外，基于xml文件生成樹對異構環境下的分布式應用具有重要意義。事實上，利用xml作為通用數據傳遞格式已得到普遍認可；
3. 從數據庫中得到數據（在.net中，我們可以理解為一個數據集），建立樹形結構。
這種方式通過父子關系遞歸生成樹，是最容易理解的一種編程實現方式。一般是自頂向下遞歸生成，得到廣泛應用。
這里，我們不妨舉一個實際的例子來說明一下，假設我們有這樣的數據集（可以看作是一個公司的部門列表）：
tagvalue
contentvalue
parentid
g01
行銷部
g02
顧問部
g03
研發部
g04
測試部
gs01
行銷一部
g01
gs02
行銷二部
g01
gs03
行銷三部
g01
gsl01
行銷一部北京辦
gs01
gsl02
行銷一部上海辦
gs01
gs04
顧問一部
g02
gs05
顧問二部
g02
gs06
研發一部
g03
gs07
研發二部
g03
gs08
測試一部
g04
gs09
測試二部
g04
gsl03
研發一部杭州分部
gs06
gsl04
研發一部西安分部
gs06
表1 示例數據集
其中，tagvalue是節點的實際值，contentvalue是用戶界面上節點顯示的值或者說標簽值，parentid是節點的父節點的tagvalue。若節點為根節點，一般設parentid為空或等于本身的tagvalue。
默認情況下，我們可以按照下面的算法把所有的節點裝配成一棵樹，
算法1：通過父子關系遞歸生成樹基本算法
l step 0：數據準備，給定數據集。
一般來說數據集遵循這樣的格式，即(tagvalue,contentvalue,parentid);
l step 1：給定待增加子節點的節點（初始時一般為根節點），記作curnode，以及待增加節點的parentid值（初始時為根節點的parentid），記作curparentid;
l step 2：在數據集中查找具有指定parentid值的所有節點，得到節點集objarr[]，
if (objarr == null)
return;
else
{
//遍歷節點集
for(int i=0; i<objarr.length;i++)
{
將objarr[i]添加為curnode的子節點，同時遞歸（即將objarr[i]作為curnode，objarr[i]的tagvalue作為curparentid，goto step 1）;
}
}
最終可以得到下圖所示的treeview：
圖1 treeview效果圖
這種方法的缺陷在于"由父節點及子節點"的遍歷順序意味著每個子節點的父節點必須存在，否則將搜索不到，即可能出現斷層現象。在很多實際應用中，我們發現這種實現方式不能完全奏效，最典型的情況就是當需要對眾節點所表征的實際值(比如機構列表，人員列表，資源列表等)進行權限控制時，這時往往從數據庫中篩選出來的數據集中節點會出現斷層現象。比如我們假設設定權限時給定數據如表2，即把第一行“行銷部”去掉（注：權限過濾操作已超出本文討論的范圍，這里假定數據集已準好），則運用算法1生成的treeview如圖2所示。
tagvalue
contentvalue
parentid
g02
顧問部
g03
研發部
g04
測試部
gs01
行銷一部
g01
gs02
行銷二部
g01
gs03
行銷三部
g01
gsl01
行銷一部北京辦
gs01
gsl02
行銷一部上海辦
gs01
gs04
顧問一部
g02
gs05
顧問二部
g02
gs06
研發一部
g03
gs07
研發二部
g03
gs08
測試一部
g04
gs09
測試二部
g04
gsl03
研發一部杭州分部
gs06
gsl04
研發一部西安分部
gs06
表2 給定數據集
圖2 treeview效果圖
可以看到，這里產生了節點遺漏現象。一般來說，我們可以從兩方面入手去解決問題，一方面可以修正數據集，另一方面則可以修改生成樹算法。顯然直接修正數據集是很復雜的，且會帶來效率問題。而單方面修改生成樹算法也是不是很好（即把遺漏的節點直接插到根節點下），因為這時會出現父輩和晚輩同級的現象。
三、通過深度編號遞歸生成樹算法
回顧到已有的一些方法（文[1~5]），其中基于節點深度生成樹的方法給我們一些啟發，我們在構造數據集時可以增加深度字段，但這里的深度不是簡單的層級號，是一個擴展了的概念，具體地說其實是一個深度編號，它與父輩編號存在一定的對應關系。比如表1所示的數據集可以作如下編號：
tagvalue
contentvalue
parentid
depthid
g01
行銷部
a001
g02
顧問部
a002
g03
研發部
a003
g04
測試部
a004
gs01
行銷一部
g01
a001001
gs02
行銷二部
g01
a001002
gs03
行銷三部
g01
a001003
gsl01
行銷一部北京辦
gs01
a001001001
gsl02
行銷一部上海辦
gs01
a001001002
gs04
顧問一部
g02
a002001
gs05
顧問二部
g02
a002002
gs06
研發一部
g03
a003001
gs07
研發二部
g03
a003002
gs08
測試一部
g04
a004001
gs09
測試二部
g04
a004002
gsl03
研發一部杭州分部
gs06
a003001001
gsl04
研發一部西安分部
gs06
a003001002
表3 帶深度編號的數據集
其中，depthid即是節點的深度編號。生成深度編號的過程其實也不復雜，首先我們可以制定編號的規則，比如層級編號的前綴、編碼長度、起始值等。當給某個節點編號時，只要找到所在層級的最大編號，然后增1。具體實現過程這里不再細述。
于是，我們很自然地想到借鑒算法1的思想設計基于深度編號的生成樹程序。這時，我們可以根據當前節點的深度編號尋找其后代節點集，但要給出一個最大跨度(可以理解為最高級與最低級間的間隔級數)，因為不可能無限制地找下去。這種方法可以部分程度上彌補"由父節點及子節點"的遍歷的缺陷，因為當出現斷層時會沿著編號繼續往后找。但是還是會可能漏掉，比如我們給定數據集（把“研發一部”過濾掉）：
tagvalue
contentvalue
parentid
depthid
g01
行銷部
a001
g02
顧問部
a002
g03
研發部
a003
g04
測試部
a004
gs01
行銷一部
g01
a001001
gs02
行銷二部
g01
a001002
gs03
行銷三部
g01
a001003
gsl01
行銷一部北京辦
gs01
a001001001
gsl02
行銷一部上海辦
gs01
a001001002
gs04
顧問一部
g02
a002001
gs05
顧問二部
g02
a002002
gs07
研發二部
g03
a003002
gs08
測試一部
g04
a004001
gs09
測試二部
g04
a004002
gsl03
研發一部杭州分部
gs06
a003001001
gsl04
研發一部西安分部
gs06
a003001002
表4 給定數據集
在生成樹過程中，當從“研發部”（a003）往下找子節點時，找到的應該是“研發二部”（a003002），因為它是最近的節點。而下面的順序就是沿著“研發二部”再往下找，顯然不可能找到“研發一部杭州分部”和“研發一部西安分部”，因為編號規則不一樣，這樣生成的樹同樣會漏掉節點。
我們提出一種新的算法，即打破傳統的遍歷順序，采用由底向上的遍歷順序。形象地說，傳統的方法是通過一個既有根節點或父節點來不斷衍生新的子節點（如圖3(a)所示），而新的算法是通過不斷聚集節點，形成子樹集，最后匯成一棵樹（如圖3(b)所示）。
圖3 treeview節點生成流程示意圖
算法2：由底向上按層次(深度)遍歷法生成樹算法
l step 0：數據準備，給定數據集(tagvalue,contentvalue,depthid), tagvalue是節點的實際值，contentvalue是節點顯示的值或者說標簽值，depthid是節點的深度編號。若節點為根節點，一般其depthid長度為最短。給定最大深度imaxdeplen和最小深度imindeplen。給定用于存儲當前子樹的hashtable;
l step 1：給定當前遍歷的層級長度icurdeplen，初始設為imaxdeplen;
l step 2：在數據集中根據給定icurdeplen查找滿足條件的層級，得到該層級的節點集objarr[]，
if (objarr == null)
return;
else
{
//遍歷節點集
for(int i=0; i<objarr.length;i++)
{
step 2.1 查找objarr[i]的父節點，若無父節點，直接加入，goto step 2.2;若有父節點，先查找父節點是否已在hashtable中。若有，將其從hashtable中移出并記為tempparnode；否則生成新節點tempparnode；goto step 2.3；
step 2.2 若當前節點objarr[i]不在hashtable中，在hashtable中添加objarr[i]；continue;
step 2.3 若當前節點objarr[i]不在hashtable中，根據objarr[i]生成節點tempnode；否則，將其從hashtable中移出，并記為tempnode；將tempnode插到tempparnode中，并將存入hashtable。
}
}
l step 3：若當前層級icurdeplen大于最小層級imindeplen，則繼續回溯，將icurdeplen減1并作為當前icurdeplen，goto step 2；否則goto step 4.
l step 4：在得到用hashtable存儲的節點表后(實際上是一子樹表)，遍歷hashtable，將各棵子樹插入treeview.
在該算法中，我們一開始便計算好數據集中節點深度編號的最小長度和最大長度，目的是為了不盲目搜索。但如果數據集中每一層級的深度編號是固定長的，則可以更簡化搜索過程。存放臨時子樹的hashtable的鍵值是當前子樹根節點的tag值，這樣的好處是查找相當方便，不需要在treeview中遍歷一個個節點。所以，每次處理上一層級的節點，只需看其父節點在不在hashtable中，若在將其插入子樹，否則增加hashtable項。
附錄示例程序實現了這一算法，這里介紹一下關鍵的幾個函數。
函數形式及其參數解釋
功能
populatecompletetree(ref system.windows.forms.treeview objtreeview,dataset dssource,string strtreecaption,int itagindex,int icontentindex,int idepthindex)
1. objtreeview是最終要生成的treeview；
2. dssource是給定數據集；
3. strtreecaption指定treeview根節點的名稱；
4. itagindex是數據集中tagvalue字段的列號；
5. icontentindex是數據集中contentvalue字段的列號；
6. idepthindex是數據集中depthid字段的列號；
1. 采用層次(深度)遍歷法生成樹主調函數；
2. 調用collectnodes(dataset dssource,int itagindex,int icontentindex,int idepthindex,int icurdeplen,int imindeplen,ref hashtable objarrnode)
collectnodes(dataset dssource,int itagindex,int icontentindex,int idepthindex,int icurdeplen,int imindeplen,ref hashtable objarrnode)
1. dssource，itagindex，icontentindex，idepthindex同上；
2. icurdeplen指當前層級深度編號長度；
3. imindeplen指最小深度即最頂層深度編號長度；
4. objarrnode指用于存放中間子樹的hashtable
1. 從底往上聚集節點;
2. 調用 lookupparentnode(dataset dssource,int idepthindex,string strsubdepth,int itagindex,int icontentindex)
lookupparentnode(dataset dssource,int idepthindex,string strsubdepth,int itagindex,int icontentindex)
1. dssource，itagindex，icontentindex，idepthindex同上；
2. strsubdepth指當前節點的深度編號（因為是遞歸查找）
1. 查找最近的上控層級，因為有可能父節點層級不存在。
此時若給定數據集（我們把“研發部”和“行銷一部”過濾掉），
tagvalue
contentvalue
parentid
depthid
g01
行銷部
a001
g02
顧問部
a002
g04
測試部
a004
gs02
行銷二部
g01
a001002
gs03
行銷三部
g01
a001003
gsl01
行銷一部北京辦
gs01
a001001001
gsl02
行銷一部上海辦
gs01
a001001002
gs04
顧問一部
g02
a002001
gs05
顧問二部
g02
a002002
gs07
研發二部
g03
a003002
gs08
測試一部
g04
a004001
gs09
測試二部
g04
a004002
gsl03
研發一部杭州分部
gs06
a003001001
gsl04
研發一部西安分部
gs06
a003001002
表5 給定數據集
則生成樹如下圖所示，
圖4 treeview效果圖
這正是我們需要的結果。
當然，有時為了結構的需要，我們還會采取所謂“中立”的方法。比如對于本文所提的treeview控件節點生成問題，如果不想再寫算法去生成深度編號，那么我們還可以通過給數據集增加標志位的方法，即用標志位來標識數據是否已被篩選。在運用傳統算法生成樹后，再檢查一下是否有未被篩選的數據，若有則查找其祖輩節點，將其插入祖輩節點。不過這里的“查找祖輩節點”是在treeview上進行的，當節點很多時其效率肯定沒有直接在數據集上搜索高。
另外，深度編號的引入不僅會給生成樹帶來方便，還可以讓權限設置更靈活。具體到我們的示例來說，一般如果我們要把某些部門過濾掉，那么會把這些部門一個一個挑出來，我們稱之為“離散值設置方式”。而當系統結構龐大時，我們更希望挑選一個區間，比如把一個部門及其下控的n級過濾掉，這是一個“連續值設置方式”，這時包含層級概念的深度編號可以很好地解決這個問題。實際的系統開發中，我們也發現采用這種方式是切實可行的。
四、其他treeview生成方式
前面提到treeview還可以通過xml文件(串)生成。這種方式實現的關鍵是構造出一個類似于treeview的xml文檔或字符串出來。其基本思想應該與前面討論的算法是相似的，只是在程序實現上稍微復雜一些（其中，xml節點的索引可以基于文檔對象模型(dom)來做）。另外還要注意的是，有很多的第三方treeview控件，他們所支持的xml文檔的格式是不盡相同的。限于篇幅，本文不詳細討論具體實現過程。
五、小結
本文主要討論了.net平臺下treeview控件節點生成程序設計，結合已有方法和實際需求，對設計方法進行了研究，給出了比較完整的解決方法。
在樹的具體應用中，除了生成樹之外，節點的增、刪、改、查甚至節點的升級和降級都是很常見的。本質上說，這些操作所涉及的是與業務相關的數據庫操作，所以在采用“由底向上按層次(深度)遍歷法”生成的treeview中，這些操作的實現與傳統方法是一致的，額外的操作無非是添加或修改深度編號。當然，實際需求是變化多端的，相應算法的設計與分析也是無止境的。
參考文獻（reference）:
[1] zane thomas. dataviewtree for windows forms，http://www.abderaware.com/whitepapers/ datatreeview.htm
[2] 李洪根. 樹形結構在開發中的應用, http://www.microsoft.com/china/community/column/ 21.mspx
[3] 李洪根. .net平臺下web樹形結構程序設計, http://www.microsoft.com/china/community/ column/30.mspx
[4] don schlichting. populating the treeview control from a database, http://www.15seconds. com/issue/030827.htm
[5] how to: populate a treeview control from a dataset in visual basic .net, http://support. microsoft.com/?kbid=320755
[6] scott mitchell. displaying xml data in the internet explorer treeview control，http://aspnet. 4guysfromrolla.com/articles/051403-1.aspx
-------------
source code:
using system;
using system.data;
using system.windows.forms;
using system.collections;
namespace poptreeview
{
/// <summary>
/// treeoperator 的摘要說明。
/// </summary>
public class treeoperator
{
public treeoperator()
{
//
// todo: 在此處添加構造函數邏輯
//
}
/// <summary>
/// 采用層次(深度)遍歷法生成樹
/// </summary>
/// <param name="objtreeview">目標樹</param>
/// <param name="dssource">數據集</param>
/// <param name="strtreecaption">樹顯示名</param>
/// <param name="itagindex">值索引</param>
/// <param name="icontentindex">內容索引</param>
/// <param name="idepthindex">層次索引</param>
public static void populatecompletetree(ref system.windows.forms.treeview objtreeview,dataset dssource,string strtreecaption,int itagindex,int icontentindex,int idepthindex)
{
//從底層開始遍歷，開辟一個hashtable(以tag值為關鍵字)，存放當前計算的節點
objtreeview.nodes.clear();
int imaxlen = getmaxdepthlen(dssource,idepthindex);
int iminlen = gettopdepthlen(dssource,idepthindex);
hashtable objarrnode = new hashtable();
collectnodes(dssource,itagindex,icontentindex,idepthindex,imaxlen,iminlen,ref objarrnode);
treenode objrootnode = new treenode(strtreecaption);
//在得到節點表后,插入樹
foreach(object objnode in objarrnode.values)
{
treenode objnewnode = new treenode();
objnewnode = (treenode)objnode;
objrootnode.nodes.add(objnewnode);
}
objtreeview.nodes.add(objrootnode);
}
/// <summary>
/// 從底往上聚集節點
/// </summary>
/// <param name="dssource"></param>
/// <param name="itagindex"></param>
/// <param name="icontentindex"></param>
/// <param name="idepthindex"></param>
/// <param name="icurdeplen"></param>
/// <param name="imindeplen"></param>
/// <param name="objarrnode"></param>
private static void collectnodes(dataset dssource,int itagindex,int icontentindex,int idepthindex,int icurdeplen,int imindeplen,ref hashtable objarrnode)
{
//收集節點
system.data.dataview dv;
system.windows.forms.treenode tempnode;
//查找給定層節點
int i=icurdeplen;
do
{
dv = new dataview(dssource.tables[0]);
string strexpr = "len(trim("+dssource.tables[0].columns[idepthindex].columnname+"))="+convert.tostring(i);
dv.rowfilter = strexpr;
i--;
}while(i>=imindeplen && dv.count<=0);
icurdeplen = i+1;
#region 逐層回溯，收集節點
foreach(system.data.datarowview drow in dv)
{
//查找父節點
string[] strarrparentinfo = lookupparentnode(dssource,idepthindex,drow[idepthindex].tostring().trim(),itagindex,icontentindex);
string strtagvalue = drow[itagindex].tostring().trim();
string strcontentvalue = drow[icontentindex].tostring();
//若無父節點，直接加入
if (strarrparentinfo == null)
{
//當前節點不在hashtable中
if (objarrnode[strtagvalue]==null)
{
//添加當前節點
tempnode = new treenode(strcontentvalue);
tempnode.tag = strtagvalue;
objarrnode.add(strtagvalue,tempnode);
}
}
else //有父節點，此時先查找父節點是否已在hashtable中
{
string strpartagvalue = strarrparentinfo[0].trim();
string strparcontentvalue = strarrparentinfo[1].trim();
//父節點已在hashtable中
if (objarrnode[strpartagvalue]!= null)
{
//當前節點不在hashtable中
if (objarrnode[strtagvalue]==null)
{
tempnode = new treenode(strcontentvalue);
tempnode.tag = strtagvalue;
}
else
{
//取出并移除該節點，然后插入父節點
tempnode = new treenode();
tempnode =(treenode)objarrnode[strtagvalue];
objarrnode.remove(strtagvalue);
}
//插入到父節點中
treenode tempparnode = new treenode();
tempparnode = (treenode)objarrnode[strpartagvalue];
tempparnode.nodes.add(tempnode);
objarrnode[strpartagvalue] = tempparnode;
}
else //父節點不在hashtable中
{
//當前節點不在hashtable中
if (objarrnode[strtagvalue]==null)
{
tempnode = new treenode(strcontentvalue);
tempnode.tag = strtagvalue;
}
else
{
//取出并移除該節點，然后插入父節點
tempnode = new treenode();
tempnode = (treenode)objarrnode[strtagvalue];
objarrnode.remove(strtagvalue);
}
//創建父節點并將當前節點插入到父節點中
treenode tempparnode = new treenode(strparcontentvalue);
tempparnode.tag = strpartagvalue;
tempparnode.nodes.add(tempnode);
objarrnode.add(strpartagvalue,tempparnode);
}
}
}
#endregion
//還有未遍歷的層
if (icurdeplen>imindeplen)
{
collectnodes(dssource,itagindex,icontentindex,idepthindex,icurdeplen-1,imindeplen,ref objarrnode);
}
}
/// <summary>
/// 查找父親節點
/// </summary>
/// <param name="dssource"></param>
/// <param name="idepthindex"></param>
/// <param name="strsubdepth"></param>
/// <param name="itagindex"></param>
/// <param name="icontentindex"></param>
/// <returns>找到返回由tag值，內容值和深度值組成的字符串數組，否則返回null</returns>
private static string[] lookupparentnode(dataset dssource,int idepthindex,string strsubdepth,int itagindex,int icontentindex)
{
system.data.dataview dv;
int isublen = strsubdepth.length;
if (isublen<=1)
{
return null;
}
int i=1;
do
{
dv = new dataview(dssource.tables[0]);
string strexpr ="trim("+dssource.tables[0].columns[idepthindex].columnname+") = '"+strsubdepth.substring(0,isublen-i)+"'";
dv.rowfilter = strexpr;
i++;
}while(i<isublen && dv.count<=0);
if (dv.count<=0)
{
return null;
}
else
{
string[] strarr = {dv[0][itagindex].tostring(),dv[0][icontentindex].tostring(),dv[0][idepthindex].tostring()};
return strarr;
}
}
/// <summary>
/// 得到最大深度值(深度的長度)
/// </summary>
/// <param name="dssource">數據集</param>
/// <param name="idepthindex">深度索引(列號)</param>
/// <returns>最大深度值</returns>
private static int getmaxdepthlen(dataset dssource,int idepthindex)
{
datarowcollection objrowcol = dssource.tables[0].rows;
int imax = objrowcol[0][idepthindex].tostring().trim().length;
foreach(datarow objrow in objrowcol)
{
int icurlen = objrow[idepthindex].tostring().trim().length;
if (imax<icurlen)
{
imax = icurlen;
}
}
return imax;
}
/// <summary>
/// 得到最小深度值(深度的長度)
/// </summary>
/// <param name="dssource">數據集</param>
/// <param name="idepthindex">深度索引(列號)</param>
/// <returns>最小深度值</returns>
private static int gettopdepthlen(dataset dssource,int idepthindex)
{
datarowcollection objrowcol = dssource.tables[0].rows;
int imin = objrowcol[0][idepthindex].tostring().trim().length;
foreach(datarow objrow in objrowcol)
{
int icurlen = objrow[idepthindex].tostring().trim().length;
if (imin>icurlen)
{
imin = icurlen;
}
}
return imin;
}
}
}
-----------
memo: 本文最初我想在刊物上發表的，篇幅很長，這里有所刪節。歡迎指正、交流！
