一、引言
在应用系统开发中，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: 本文最初我想在刊物上发表的，篇幅很长，这里有所删节。欢迎指正、交流！
