一、引言

在应用系统开发中，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