一个树集合
4.74/5 (41投票s)
C# 中树集合的实现。
引言
我之前需要一个树集合来实现某个功能。我在 CP 上找不到，所以决定自己写一个——毕竟，能有多难呢？写了 2000 行代码之后……我希望我的经验能帮到你，至少能将此代码作为起点。我包含了我认为需要的一切，包括一套详细的事件集。
背景
这段代码最初是作为一个 Composite（组合）模式实现的。然而，我很快意识到我不需要两个类，因为一个节点就是一个树，而一个树也是一个节点。所以我将它们合并成了一个名为 NodeTree 的类。这可能以前有人做过，但对我来说，这似乎是个好主意。
你可以从 NodeTree 派生一个类来提供特定数据类型的专门化，但你也可以不这样做。如果你乐于依赖运行时类型检查和异常，那么你可以通过提供静态构造函数中的数据类型来创建一个强类型树。
ITree tree = NodeTree.NewTree( typeof( Element ) );
使用代码
我编写了一个测试应用程序，在编写代码时对其进行检查。这个应用程序几乎和集合一样长。它是了解我打算如何使用集合的最佳资源。我将在接下来的部分详细阐述各个方面。
接口
尽管只有一个类 NodeTree 用于建模树，但用户并不直接使用它。他们通过两个接口来操作集合：INode 和 ITree。NodeTree 类同时派生自这两个接口。
[Serializable]
internal class NodeTree : INode, ITree, ISerializable
所以，NodeTree 是节点和树的内部表示。但是，这两个接口只声明了对该特定视角有意义的成员。两个接口之间存在相当多的等效行为；例如，它们都声明了 InsertChild 方法。总的来说，INode 接口更大，尽管 ITree 声明了一些独有的成员，例如 Clear。
转换
每个接口都有一个属性允许转换为另一个。
INode 声明了一个 Tree 属性，它获取对节点根节点的引用，类型为 ITree。
ITree 声明了一个 Root 属性，它获取对树根节点的引用，类型为 INode。
Data
集合的目的是存储数据。在这个集合中，数据存储在 NodeTree 类的一个私有字段 _Data 中。对这个对象的访问是通过 INode 接口进行的，该接口声明了一个公共属性 Data。
object Data { get; set; }
ITree 没有声明此属性，因为稍后我们会看到，它没有意义。
许多成员操作的是数据对象而不是节点。例如，一个 InsertChild 方法的声明如下：
INode InsertChild( object o )
它接受数据对象作为参数，创建一个节点包装器，返回新的 INode。实际上，尝试插入 INode 是一个错误，尽管你可以插入一个 ITree，我们稍后会看到。
Copying
有两种方法可以复制由 NodeTree 定义的子树：Copy 和 DeepCopy。
Copy 创建新的树节点，但将每个新节点的 data 属性设置为引用与原始节点相同的数据实例。
DeepCopy 也会尝试复制数据。我定义了一个名为 IDeepCopy 的接口，如下所示：
internal interface IDeepCopy
{
object CreateDeepCopy();
}
如果数据对象支持此接口，那么将从正在复制的每个节点调用数据上的 CreateDeepCopy。
如果数据不支持此接口，那么将尝试实例化一个与数据对象相同类型的新对象，使用复制构造函数。
Activator.CreateInstance( data.GetType(), new object[] { data } );
如果也不存在复制构造函数，那么 DeepCopy 将放弃并仅复制对数据的引用。
异常
我广泛使用异常来检查无效操作。这反映了我（至少在这个集合中）偏好运行时类型检查。
特别是，在许多地方，如果你传递一个未包装的节点而不是一个树，就会抛出异常。
结构
通过 INode 访问的树与通过 ITree 访问的树之间存在结构差异。ITree 的 NodeTree 在根部有一个额外的节点，其数据对象是一个 RootObject 对象。这是一个受保护的类，嵌套在 NodeTree 中，因此你无法实例化它。这是为了确保只有一个节点的数据是 RootObject，那就是 ITree 的根节点。它也被证明是存储树数据对象类型的便捷位置。
因此，INode 和 ITree 之间存在固有的差异。如果你尝试将 INode 传递给接受 ITree 的方法，将会引发异常。这是设计使然。通常，你大部分时间使用 ITree，只有在引用 ITree 中包含的特定节点时才使用 INode。
这听起来很复杂，但实际上在你习惯之后会非常直观。
例如，如果你想将一个节点从树的一个位置移动到另一个位置，你可以使用以下方法：
void Move( INode source, INode destination )
{
ITree temp = source.Cut();
destination.InsertChild( temp );
}
请注意，Cut 方法返回的是 ITree，而不是 INode。同样，InsertChild 方法接受的是 ITree，而不是 INode。
详细说明
我现在将详细介绍这些接口。其中大部分是显而易见的，但值得一览或作为参考。
导航
这些属性返回 INode，因为它们引用树内的节点。
INode Parent { get; }
INode Previous { get; }
INode Next { get; }
INode Child { get; }
INode Root { get; }
INode Top { get; }
INode First { get; }
INode Last { get; }
INode LastChild { get; }
子节点属性引用节点的第一个子节点。
在树中，有一个隐藏在用户视线之外的根 NodeTree。这个根节点的直接子节点是“顶层”节点。
布尔属性。
这些属性获取有关节点周围结构的信息。
bool IsTree { get; }
bool IsRoot { get; }
bool IsTop { get; }
bool HasParent { get; }
bool HasPrevious { get; }
bool HasNext { get; }
bool HasChild { get; }
bool IsFirst { get; }
bool IsLast { get; }
IsTree 属性检查是否存在 RootObject 作为节点的数据。如果存在，则返回 true。
IsRoot 属性仅检查是否存在父节点。
搜索
这些方法对当前节点下方的子树执行线性搜索，查找具有指定数据的节点。
INode this[ object o ] { get; }
bool Contains( object o );
插入对象。
这些方法围绕指定的 数据对象创建一个包装的 NodeTree，将其插入树中，并返回新节点。
INode InsertPrevious( object o );
INode InsertNext ( object o );
INode InsertChild ( object o );
INode Add ( object o );
INode AddChild ( object o );
插入节点。
这些方法只是抛出异常，因为向树添加节点是非法的——你必须添加一个新对象或一个完整的树。
void InsertPrevious( INode node );
void InsertNext ( INode node );
void InsertChild ( INode node );
void Add ( INode node );
void AddChild ( INode node );
插入树。
这些方法将指定的树插入到当前树中。
void InsertPrevious( ITree tree );
void InsertNext ( ITree tree );
void InsertChild ( ITree tree );
void Add ( ITree tree );
void AddChild ( ITree tree );
剪切、复制、移除节点。
这些方法操作节点。
ITree Cut ();
ITree Copy ();
ITree DeepCopy ();
void Remove ();
剪切、复制、移除数据。
这些方法操作遇到的第一个数据为指定对象的节点。
ITree Cut ( object o );
ITree Copy ( object o );
ITree DeepCopy ( object o );
void Remove ( object o );
更多布尔属性。
这些属性返回值，指示相应的成员是否有效。
bool CanMoveToParent { get; }
bool CanMoveToPrevious { get; }
bool CanMoveToNext { get; }
bool CanMoveToChild { get; }
bool CanMoveToFirst { get; }
bool CanMoveToLast { get; }
移动。
这些方法对当前节点执行常见的移动操作。
void MoveToParent ();
void MoveToPrevious ();
void MoveToNext ();
void MoveToChild ();
void MoveToFirst ();
void MoveToLast ();
计数。
此方法返回节点直接子节点的数量。
int DirectChildCount { get; }
集合。
INode 和 ITree 都派生自 IValuesCollection，后者派生自 ICollection，而 ICollection 又派生自 IEnumerable，因此它们本身都可以作为枚举器。我添加了这四个额外的集合，它们操作此 NodeTree 的子节点。
IValuesCollection Nodes { get; }
IValuesCollection AllChildren { get; }
IValuesCollection DirectChildren { get; }
IValuesCollection DirectChildrenInReverse { get; }Nodes 集合与 DirectChildren 集合完全相同。IValuesCollection 接口只是向 ICollection 添加了 Values 属性。这意味着你可以访问所有集合的此属性，以获取返回节点中数据的集合，而不是节点本身。这意味着你可以直接用如下代码访问数据对象：
foreach ( Element o in node.DirectChildren.Values )
DataType
此属性仅在 ITree 接口中声明。它检索树中存储的数据对象的类型。
Type DataType { get; }
Clear
此方法仅在 ITree 接口中声明。它只是清空一棵树。
void Clear();
事件
NodeTree 类提供了以下事件：
event NodeTreeDataEventHandler Validate;
event EventHandler Clearing;
event EventHandler Cleared;
event NodeTreeDataEventHandler Setting;
event NodeTreeDataEventHandler SetDone;
event NodeTreeInsertEventHandler Inserting;
event NodeTreeInsertEventHandler Inserted;
event EventHandler Cutting;
event EventHandler CutDone;
event NodeTreeNodeEventHandler Copying;
event NodeTreeNodeEventHandler Copied;
event NodeTreeNodeEventHandler DeepCopying;
event NodeTreeNodeEventHandler DeepCopied;
你可以从节点或树级别附加事件。每个事件都会针对当前节点引发，然后针对包含它的树引发。我曾考虑为当前节点的每个父节点引发事件，但这似乎有点多余。
用户可能只会在树的 Validate 事件上附加，但也有选项可以在每个节点的每个事件上附加。
默认的 Validate 处理程序会检查数据对象的类型，如果与树构造函数中设置的类型不匹配，则会抛出异常。
请参阅“Points of Interest”，其中解释了如何使用 EventHandlerList 对象来最小化如此多事件的空间开销。
序列化
通过实现 ISerializable，我添加了序列化支持。如果你想持久化一棵树，或者想将一棵树复制到剪贴板，这将非常有用。
我在第 4 版中添加了对 XmlSerialization 的支持。
ICollection
两个接口都派生自 ICollection，因此也派生自 IEnumerable。
关注点
序列化
注意 ISerializable 的使用，以及版本号的持久化，以帮助使序列化过程具有未来的兼容性。
默认的序列化实现不够灵活，但这两种操作在很大程度上弥补了其不足。
我编写了几个适配器类来支持 XmlSerialization - 请参阅 Form1.cs 的底部。
你可以通过移动序列化和反序列化按钮处理程序中的注释行来选择要使用的格式化程序。
事件
我提供了大量的事件——可能比测试应用程序之外的任何人所需要的都多。这会导致 NodeTree 类在空间需求上增加不可接受的开销，所以我使用了一个 EventHandlerList 对象来最小化影响。基本上，与在类中为每个事件维护一个集合不同，你只有一个集合用于所有事件，并使用键对象来仅记录已附加的事件。因此，NodeTree 的每个实例只有一个 EventHandlerList 实例，并且它只记录已附加的事件。这使得引发事件的过程稍微复杂一些，但不会太复杂。
结论
这个集合并非万能。它以功能为重，效率相对较低，因此体积较大。然而，它确实填补了 .NET Framework 的一个空白，而且肯定比使用不可见的 TreeView 要好。我在此将其作为添加到你的工具箱中的一个选项。
历史
- 2005 年 2 月 25 日：版本 5：将所有枚举升级为集合。请参阅 Collections。
- 2004 年 6 月 7 日：版本 4：添加了对 XmlSerialization 的支持。
- 2004 年 4 月 19 日：版本 3：枚举现在能正确地抛出异常。
- 2004 年 3 月 30 日：版本 2：修复了命名约定。
- 2004 年 3 月 30 日：版本 1。