通用树集合

• 下载库 - 14.4 Kb
• 下载源代码 - 9.43 Kb
• 下载演示应用程序 - 35.2 Kb
• 下载演示源代码 - 72.1 Kb

目录

• 引言
• 结构
  • 接口
  • Data
  • 节点结构
  • 树结构
  • 术语
• 快速入门
• 文档
  • 实例化
  • 转换
  • 计数
  • 关系
  • 布尔属性
  • 添加元素
  • 添加树
  • 移动节点
  • Copying
  • 操作子树
  • 使用元素
  • 枚举器
  • 序列化
  • 事件
• 关注点
  • 序列化
  • 事件
• 结论
• 历史

引言

我去年为 .NET 1.1 编写了一个树集合 - 一个树集合 [^]。事实证明这很受欢迎，所以我决定使用泛型为 .NET 2.0 编写一个。我重用了许多代码，但我不得不从头开始编写许多新的接口，尤其是枚举器。我再次不知道为什么微软没有在框架中包含这种基本集合的实现。这个实现填补了这一空白，并且可以直接使用。

我建议首先阅读结构部分，但如果您只想使用此代码，请查看快速入门部分。

结构

此代码最初是作为复合模式出现的。然而，我很快意识到我不需要两个类，因为一个节点就是一棵树，一棵树也是一个节点。所以我将它们合并为一个名为 NodeTree 的类。这可能以前有人做过，但对我来说似乎是个好主意。

接口

尽管只使用一个类 NodeTree 来建模树，但消费者不会直接使用它。他们通过两个接口操作集合：INode 和 ITree。NodeTree 类派生自这两个接口。

partial class NodeTree<T> : ITree<T>, INode<T>

因此，NodeTree 是节点和树的内部表示。然而，这两个接口只声明了对特定观点有意义的成员。这两个接口之间有相当多的等效行为；例如，它们都声明了 InsertChild 方法。总的来说，INode 接口更大，尽管 ITree 确实声明了一些独有的成员，如 Clear。

Data

集合的目的是保存数据。在这个集合中，数据保存在 NodeTree 类中的私有字段 _Data 中。通过 INode 接口访问此对象，该接口声明了一个属性 Data。

partial interface INode<T>
{
    T Data { get; set; }
}

ITree 不声明此属性，因为我们稍后会看到它没有意义。

节点结构

每个节点都有以下结构

图 1：节点结构

树结构

节点连接在一起形成具有以下结构的树

图 2：树结构

术语

Root 节点定义了一棵树。您不能用它来存储数据 - 它只是一个占位符。Top 节点定义了树的用户部分。您可以有多个 Top 节点，但这不是必需的。您负责根据您的要求构建您的树。分支是公共 Parent 的 Children 的节点集合，并通过 Previous 和 Next 属性连接。分支开头的节点称为 First 节点。类似地，分支末尾的节点称为 Last 节点。父节点的 Child 节点是其分支中的 First 节点。

快速入门

本节将让您在最短的时间内开始。示例显示了一棵数据类型为 Element 的树。

首先，您必须创建您的树

ITree<Element> tree = NodeTree<Element>.NewTree();

接下来，创建一个顶层节点

INode<Element> top = tree.AddChild( new Element() );

请注意，您添加了数据类型的实例，并且为您创建并插入了一个节点到树中。

然后添加叶节点

INode<Element> leaf1 = top.AddChild(new Element());
INode<Element> leaf2 = top.AddChild( new Element() );

您现在可以遍历您的树

foreach( INode<Element> node in tree.All.Nodes )
    DoSomething( node.Data );

或

foreach( Element element in tree.All.Values )
    DoSomething( element );

文档

本节详细介绍了集合的功能。

实例化

这些 static 方法创建新树

partial class NodeTree<T>
{
    public static ITree<T> NewTree() { ... }
    public static ITree<T> 
       NewTree(IEqualityComparer<T> dataComparer) { ... }
}

第一个方法使用默认的 DataComparer 创建一棵新树，该 DataComparer 使用 EqualityComparer<T>.Default。如果 T 实现了 IEquatable，则它使用该实现。否则，它使用 Equals 方法。

第二个方法允许您指定要使用的 IEqualityComparer<T>。

转换

每个接口都有一个允许相互转换的属性

partial interface ITree<T>
{
    INode<T> Root { get; }
}

partial interface INode<T>
{
    ITree<T> Tree { get; }
}

计数

可获取有关树或节点的各种指标

partial interface ITree<T>
{
    int Count { get; }
    int DirectChildCount { get; }
}

partial interface INode<T>
{
    int Count { get; }
    int DirectChildCount { get; }

    int Depth { get; }
    int BranchIndex { get; }
    int BranchCount { get; }
}

Count 返回当前节点下的节点数 + 1（针对当前节点）。根节点不计数。DirectChildCount 仅返回当前节点的直接子节点数。节点的 Depth 是其父节点的数量，不包括根节点。因此，顶层节点的深度为 0，顶层子节点的深度为 1，依此类推。分支是同级节点的集合。BranchCount 是同级节点的数量，BranchIndex 是当前节点在其分支中的基于零的索引。

关系

这些属性提供了对树中其他节点的访问

partial interface ITree<T>
{
}

partial interface INode<T>
{
    INode<T> Parent { get; }
    INode<T> Previous { get; }
    INode<T> Next { get; }
    INode<T> Child { get; }

    INode<T> Root { get; }
    INode<T> Top { get; }
    INode<T> First { get; }
    INode<T> Last { get; }

    INode<T> LastChild { get; }
}

Parent、Previous、Next 和 Child 属性允许您浏览节点的直接关系。更远的关系可以通过节点的 Root、Top、First、Last 和 LastChild 属性进行访问。

布尔属性

这些属性提供了有关节点关系的信息

partial interface ITree<T>
{
}

partial interface INode<T>
{
    bool IsTree { get; }
    bool IsRoot { get; }

    bool IsTop { get; }
    bool IsFirst { get; }
    bool IsLast { get; }

    bool HasParent { get; }
    bool HasPrevious { get; }
    bool HasNext { get; }
    bool HasChild { get; }
}

IsTree 属性仅对树底部的根节点为 true。IsRoot 属性对于任何没有父节点的节点为 true。这应该仅对于树底部的根节点为 true，因为节点不能存在于树之外。IsTop、IsFirst 和 IsLast 属性提供了有关节点在树中位置的信息。HasParent、HasPrevious、HasNext 和 HasChild 属性提供了有关节点的直接关系的信息。

添加元素

这些方法允许您填充您的树

partial interface ITree<T>
{
    INode<T> InsertChild( T o );

    INode<T> AddChild( T o );
}

partial interface INode<T>
{
    INode<T> InsertPrevious( T o );
    INode<T> InsertNext( T o );
    INode<T> InsertChild( T o );

    INode<T> Add( T o );
    INode<T> AddChild( T o );
}

这些方法将给定元素包装在一个新节点中，并将此节点插入或添加到树中。InsertChild 方法将节点插入子分支的开头，AddChild 方法将节点添加到子分支的末尾。Add 方法将节点添加到当前分支的末尾。

添加树

这些方法适用于完整的树

partial interface ITree<T>
{
    void InsertChild( ITree<T> tree );

    void AddChild( ITree<T> tree );
}

partial interface INode<T>
{
    void InsertPrevious( ITree<T> tree );
    void InsertNext( ITree<T> tree );
    void InsertChild( ITree<T> tree );

    void Add( ITree<T> tree );
    void AddChild( ITree<T> tree );
}

这些方法的运行方式与添加元素相同，但作用于完整的树。

移动节点

这些方法允许您在树中移动节点

partial interface ITree<T>
{
}

partial interface INode<T>
{
    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();
}

Can 属性指示特定操作是否可能。这些方法实际执行移动节点（及其子节点）的工作。

Copying

有两种复制 NodeTree 定义的子树的方法：Copy 和 DeepCopy。Copy 创建新的树节点，但将每个新节点的数据属性设置为引用与原始节点相同的数据实例。DeepCopy 尝试同时复制数据。我已经定义了一个接口 IDeepCopy 如下：

public interface IDeepCopy
{
    object CreateDeepCopy();
}

如果数据对象支持此接口，则对正在复制的每个节点的数据调用 CreateDeepCopy。如果数据不支持此接口，则尝试 ICloneable。如果此接口也未实现，则尝试通过反射使用复制构造函数实例化与数据对象相同类型的新对象。如果不存在复制构造函数，则 DeepCopy 放弃并仅复制对数据的引用。

操作子树

这些方法允许您从节点及其子节点创建一棵新树

partial interface ITree<T>
{
    ITree<T> Copy();
    ITree<T> DeepCopy();
}

partial interface INode<T>
{
    ITree<T> Cut();
    ITree<T> Copy();
    ITree<T> DeepCopy();
    void Remove();
}

这些方法作用于一个节点以生成一棵树。

使用元素

这些方法查找包含指定元素的节点，然后对该节点进行操作

partial interface ITree<T>
{
    INode<T> this[ T item ] { get; }

    bool Contains( INode<T> node );
    bool Contains( T item );

    ITree<T> Cut( T item );
    ITree<T> Copy( T item );
    ITree<T> DeepCopy( T item );
    bool Remove( T item );
}

partial interface INode<T>
{
    INode<T> this[ T item ] { get; }

    bool Contains( INode<T> node );
    bool Contains( T item );

    ITree<T> Cut( T item );
    ITree<T> Copy( T item );
    ITree<T> DeepCopy( T item );
    bool Remove( T item );
}

indexer 属性使用树的 DataComparer 返回具有指定数据元素的第一个节点。这些方法使用 indexer 查找所需的节点，然后对该节点进行操作。

枚举器

这些接口和成员允许您执行枚举

public interface IEnumerableCollection<T> : IEnumerable<T>, 
                                                ICollection
{
    bool Contains( T item );
}

public interface IEnumerableCollectionPair<T>
{
    IEnumerableCollection<INode<T>> Nodes { get; }
    IEnumerableCollection<T> Values { get; }
}

partial interface ITree<T> : IEnumerableCollectionPair<T>
{
    IEnumerableCollectionPair<T> All { get; }
    IEnumerableCollectionPair<T> AllChildren { get; }
    IEnumerableCollectionPair<T> DirectChildren { get; }
    IEnumerableCollectionPair<T> DirectChildrenInReverse { get; }
}

partial interface INode<T> : IEnumerableCollectionPair<T>
{
    IEnumerableCollectionPair<T> All { get; }
    IEnumerableCollectionPair<T> AllChildren { get; }
    IEnumerableCollectionPair<T> DirectChildren { get; }
    IEnumerableCollectionPair<T> DirectChildrenInReverse { get; }
}

IEnumerableCollection<T> 接口是所有枚举器的基础。IEnumerableCollectionPair<T> 接口提供 EnumerablePair 的两种视图：Nodes 和 Values 枚举。ITree 和 INode 都实现了 IEnumerableCollectionPair<T>；这些实现返回 All EnumerablePair。

返回 EnumerablePair 的四个属性提供了对树的不同部分或节点下的子树的访问。

序列化

此实现支持二进制或 XML 流的序列化

partial interface ITree<T>
{
    void XmlSerialize( Stream stream );
}

[ Serializable ]
partial class NodeTree<T> : ITree<T>, 
                            INode<T>, ISerializable
{
    public static ITree<T> XmlDeserialize( Stream stream )
}

二进制序列化通过 ISerializable 接口提供。要使用此方法，您将编写如下代码：

private void BinarySerialize()
{
    using ( Stream stream = File.Open( Filename, 
                      FileMode.Create, FileAccess.Write ) )
    {
        IFormatter f = new BinaryFormatter();

        ITree<Element> tree = CurrentNode.Copy();

        f.Serialize( stream, tree );
    }
}
private ITree<Element> BinaryDeserialize()
{
    using ( Stream stream = File.Open( Filename, 
                         FileMode.Open, FileAccess.Read ) )
    {
        IFormatter f = new BinaryFormatter();

        return ( ITree<Element> ) f.Deserialize( stream );
    }
}

要使用二进制序列化，您的元素数据类型必须用 Serializable 属性标记。

XML 序列化由 ITree 接口和 NodeTree 类中公开的方法提供。要使用这些方法，您将编写如下代码：

private void XMLSerialize()
{
    using ( Stream stream = File.Open( Filename, 
                     FileMode.Create, FileAccess.Write ) )
    {
        ITree<Element> tree = CurrentNode.Copy();

        tree.XmlSerialize( stream );
    }
}

private ITree<Element> XMLDeserialize()
{
    using ( Stream stream = File.Open( Filename, 
                        FileMode.Open, FileAccess.Read ) )
    {
        return NodeTree<Element>.XmlDeserialize( stream );
    }
}

要使用 XML 序列化，您的元素数据类型必须支持标准 XML 序列化。默认情况下，XML 序列化器序列化所有 public 字段和带有 get 和 set 访问器的 public 属性，这可能不是您想要的。请参阅 MSDN 中 XmlSerializer 类的文档。

事件

ITree 和 INode 这两个接口都公开了许多事件。

partial interface ITree<T>
{
    event EventHandler<NodeTreeDataEventArgs<T>> Validate;
    event EventHandler Clearing;
    event EventHandler Cleared;
    event EventHandler<NodeTreeDataEventArgs<T>> Setting;
    event EventHandler<NodeTreeDataEventArgs<T>> SetDone;
    event EventHandler<NodeTreeInsertEventArgs<T>> Inserting;
    event EventHandler<NodeTreeInsertEventArgs<T>> Inserted;
    event EventHandler Cutting;
    event EventHandler CutDone;
    event EventHandler<NodeTreeNodeEventArgs<T>> Copying;
    event EventHandler<NodeTreeNodeEventArgs<T>> Copied;
    event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopying;
    event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopied;
}

partial interface INode<T>
{
    event EventHandler<NodeTreeDataEventArgs<T>> Validate;
    event EventHandler<NodeTreeDataEventArgs<T>> Setting;
    event EventHandler<NodeTreeDataEventArgs<T>> SetDone;
    event EventHandler<NodeTreeInsertEventArgs<T>> Inserting;
    event EventHandler<NodeTreeInsertEventArgs<T>> Inserted;
    event EventHandler Cutting;
    event EventHandler CutDone;
    event EventHandler<NodeTreeNodeEventArgs<T>> Copying;
    event EventHandler<NodeTreeNodeEventArgs<T>> Copied;
    event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopying;
    event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopied;
}

您可以在节点或树级别附加到事件。每个事件都会为当前节点触发，然后为包含树触发。我曾考虑为当前节点的每个父节点触发事件，但这似乎有点太多了。默认的 Validate 处理程序检查数据对象的类型，如果与树元素类型不匹配，则抛出异常。

请参阅兴趣点，其中解释了如何使用 EventHandlerList 对象来最大程度地减少这么多事件的空间开销。

关注点

序列化

请注意 ISerializable 的使用，以及版本号的持久化，以帮助未来化序列化过程。默认的序列化实现不够灵活，但这两个操作在很大程度上缓解了其缺陷。您可能希望使用 SerializationBinder 在反序列化先前版本的类型时返回当前类型。

事件

我提供了许多事件——可能比任何人在测试应用程序之外实际需要的都多。这会使 NodeTree 类的空间需求增加到不可接受的程度，因此我使用了 EventHandlerList 对象来最大程度地减少影响。基本上，您不是在类中为每个事件都设置一个集合，而是只为所有事件设置一个集合，并使用键对象只记录已附加的事件。因此，NodeTree 的每个实例都只有一个 EventHandlerList 实例，并且它只记录已附加的事件。这使得触发事件稍微复杂一些，但并没有复杂太多。

版本 2：EventHandlerList 现在只在事件被挂钩时创建。这在没有事件被挂钩时，每个节点节省了大约 16 字节。

结论

这个集合并非万能药。它偏爱功能而非效率，这使得它变得相当臃肿。然而，它确实填补了 .NET 框架中的一个空白，并且肯定比使用不可见的 TreeView 要好。我在这里将其作为另一个选项添加到您的工具箱中。

历史

• 2005年11月20日：版本 1
  • 首次发布。
• 2005年11月24日：版本 2
  • 现在仅为具有事件处理程序的节点创建 EventHandlerList。
  • 每个节点的空间开销现在为 28 字节（没有事件）。
  • 添加了“内存”选项卡以显示基本性能指标。