可枚举、可序列化的抽象树
4.95/5 (21投票s)
本文演示了如何使用所描述的构造，以深度优先和广度优先的方式简单地枚举任何泛型树。树可以二进制序列化（使用 BinaryFormatter）、自定义二进制序列化和 XML 序列化。
引言
首先：本文适用于中级到高级程序员。如果您不理解泛型类或如何实现非泛型基类，那么您要么需要先学习它，要么尝试理解本文（因为我不会过多解释泛型模式的工作原理）。同样适用于序列化、XML 和二进制读写等内容。
不过，您可以下载并使用源代码。如果您使用它，请提及本文，但这不是强制性的。欢迎随意使用这些类，它应该提供您所需的一切，并且非常容易扩展。
数组、列表、堆栈、队列和树都有一个共同点：它们存储数据并可以被枚举。与前四种不同，树没有线性的、一维的数据结构。每个元素可以有多个子元素。一维、线性集合的枚举很简单。本文将介绍基本抽象树中的枚举。我将使用的实现是抽象且简单的，远非完美的解决方案。但这是一个很好的起点，可以根据项目需要轻松扩展。自版本 3起，我还实现了ISerializable和一个将树序列化/反序列化为 XML 文件的自定义方法，这两个方法都适用于各种实现。自版本 4起，还存在一个自定义的二进制反序列化/序列化实现，其工作原理与 XML 完全相同。与传统的二进制序列化相比，此实现提高了性能和输出大小。为了兼容性，实现了传统序列化，但在您看过文章底部的性能比较后，您可能希望避免使用它。
整个系统由以下 8 个轻量级类组成
TreeTree<T>TreeBranchDepthTreeEnumeratorDepthTreeEnumerator<T>BreadthTreeEnumeratorBreadthTreeEnumerator<T>
TreeEnumerationModeDepthFirstBreadthFirst
本文基于 .NET 4.5 和 C# 6 语言特性。由于使用了 4.5 中首次引入的 IReadOnlyList<T>，因此代码不向下兼容旧版 .NET。
目录
Tree
我们将实现的树不基于接口。大多数实现都绑定到接口，但我个人更喜欢提供一些对任何特定树都有用的功能的基类。
首先，我们创建一个名为 Tree 的类。就这么简单。这个类将包含最基本的功能，从而保持更通用的实现简洁。这个类遵循一些非常简单的约定
- 树有一个基类型为
TreeBranch的根元素Root。 - 树允许通过两种方法添加和删除元素：
AddBranch(TreeBranch)和bool RemoveBranch(TreeBranch)。 - 树实现了
IEnumerable<TreeBranch>用于枚举。 - 树实现了
ISerializable用于二进制序列化。- 树实现了一个
protected序列化构造函数：.ctor(SerializationInfo, StreamingContext)，所有派生自Tree的类都必须继承它。 - 树实现了
SerializableAttribute。
- 树实现了一个
- 树实现了用于写入和解析其自身 XML 文件的方法。
- 树实现了一个
WriteXml(string)方法，该方法将树序列化为 XML 文件。此方法是固定的，不会被任何派生类型覆盖。 - 树实现了一个
static方法ParseXml(string)，允许从 XML 文件重新创建任何树。
- 树实现了一个
- 树实现了用于写入和解析其自身二进制文件的方法。
- 树实现了一个
WriteBinary(string, Encoding)方法，该方法将树序列化为二进制文件。此方法是固定的，不会被任何派生类型覆盖。 - 树实现了一个
static方法ParseBinary(string, Encoding)，允许从二进制文件重新创建任何树。
- 树实现了一个
- 树有一个
EnumerationMode属性，允许切换枚举模式。 - （可选）出于调试原因（也可能是其他实际应用），它有一个
Dump(string)方法，允许创建整个树的文本转储。
[Serializable]
public abstract class Tree : IEnumerable<TreeBranch>, ISerializable
{
private readonly TreeBranch _rootBranch;
public TreeBranch Root => _rootBranch;
public TreeEnumerationMode EnumerationMode { get; set; }
protected Tree(TreeBranch rootBranch, TreeEnumerationMode mode = TreeEnumerationMode.DepthFirst)
{
if (rootBranch == null) throw new ArgumentNullException(nameof(rootBranch));
_rootBranch = rootBranch;
rootBranch.Tree = this;
EnumerationMode = mode;
}
protected Tree(SerializationInfo info, StreamingContext context)
{
EnumerationMode = (TreeEnumerationMode) info.GetValue("EnumerationMode", typeof (TreeEnumerationMode));
_rootBranch = (TreeBranch) info.GetValue("Root", typeof (TreeBranch));
_rootBranch.Tree = this;
}
public void AddBranch(TreeBranch branch)
{
Root.AddBranch(branch);
}
public bool RemoveBranch(TreeBranch branch)
{
return Root.RemoveBranch(branch);
}
public virtual void Dump(string file)
{
using (FileStream fs = new FileStream(file, FileMode.OpenOrCreate))
{
using (StreamWriter writer = new StreamWriter(fs))
{
Root.Dump(writer, 0);
}
}
}
public IEnumerator<TreeBranch> GetEnumerator()
{
return EnumerationMode == TreeEnumerationMode.DepthFirst
? new DepthTreeEnumerator(Root, null)
: (IEnumerator<TreeBranch>) new BreadthTreeEnumerator(Root, null);
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
[SecurityPermission(SecurityAction.Demand, SerializationFormatter = true)]
public void GetObjectData(SerializationInfo info, StreamingContext context)
{
info.AddValue("EnumerationMode", EnumerationMode);
info.AddValue("Root", Root);
}
public void WriteXml(string file)
{
XmlDocument document = new XmlDocument();
XmlElement docElement = document.CreateElement("Tree");
docElement.SetAttribute("Type", GetType().FullName);
docElement.SetAttribute("BranchType", Root.GetType().FullName);
docElement.SetAttribute("Mode", ((int) EnumerationMode).ToString());
document.AppendChild(docElement);
Root.WriteXml(document, docElement);
using (FileStream fs = new FileStream(file, FileMode.Create))
document.Save(fs);
}
public static Tree ParseXml(string file)
{
XmlDocument document = new XmlDocument();
using (FileStream fs = new FileStream(file, FileMode.Open))
document.Load(fs);
Type treeType = Type.GetType(document.DocumentElement?.GetAttribute("Type") ?? "", true);
Type branchType = Type.GetType(document.DocumentElement?.GetAttribute("BranchType") ?? "", true);
TreeEnumerationMode mode =
(TreeEnumerationMode) int.Parse(document.DocumentElement?.GetAttribute("Mode") ?? "");
TreeBranch branch = (TreeBranch) Activator.CreateInstance(branchType);
Tree tree = (Tree) Activator.CreateInstance(treeType, branch);
XmlElement rootElement = document.DocumentElement?.ChildNodes[0] as XmlElement;
branch.ParseXml(rootElement, null);
return tree;
}
public static TTree ParseXml<TTree>(string file) where TTree : Tree
{
return (TTree) ParseXml(file);
}
public void WriteBinary(string file, Encoding textEncoding = null)
{
using (FileStream fs = new FileStream(file, FileMode.Create, FileAccess.Write, FileShare.None))
{
BinaryWriter writer = new BinaryWriter(fs, textEncoding ?? Encoding.Unicode);
writer.Write(GetType().FullName);
writer.Write(Root.GetType().FullName);
writer.Write((byte) EnumerationMode);
Root.WriteBinary(writer);
}
}
public static Tree ParseBinary(string file, Encoding textEncoding = null)
{
Tree tree;
using (FileStream fs = new FileStream(file, FileMode.Open, FileAccess.Read, FileShare.Read))
{
BinaryReader reader = new BinaryReader(fs, textEncoding ?? Encoding.Unicode);
Type treeType = Type.GetType(reader.ReadString(), true);
Type branchType = Type.GetType(reader.ReadString(), true);
TreeEnumerationMode mode = (TreeEnumerationMode) reader.ReadByte();
TreeBranch branch = (TreeBranch) Activator.CreateInstance(branchType);
tree = (Tree) Activator.CreateInstance(treeType, branch);
tree.EnumerationMode = mode;
branch.ParseBinary(reader, null);
}
return tree;
}
public static TTree ParseBinary<TTree>(string file, Encoding textEncoding = null) where TTree : Tree
{
return (TTree) ParseBinary(file, textEncoding);
}
}
因为我们希望我们的非泛型 Tree 能够等效于任何泛型版本，所以我们需要定义这些基本内容。泛型 Tree<TBranch> 类只会覆盖那些使用 TreeBranch 作为类型的属性和方法。使用 EnumerationMode 属性是必要的，因为 foreach 循环总是调用 IEnumerable.GetEnumerator()。这无法阻止，也无法直接为其提供 IEnumerator<T>。所以我们使用这个属性，当调用 IEnumerable.GetEnumerator() 时，它会返回相应的 IEnumerator<T>。
序列化魔术
我们的目标是实现一种接受任何树类型（而不仅仅是特定类型）的序列化逻辑。因此，我们的 WriteXml(string) 方法会创建一个 XmlDocument，其第一个元素按约定命名为 Tree。此元素有两个属性：Type（树类型的完整名称）和 BranchType（此树中使用的分支类型的完整名称）。这些是我们在 static 方法 ParseXml(string) 中重新创建树所必需的。之后，它会在我们的根分支上调用相同的方法。WriteXml(XmlDocument, XmlElement) 方法将在文章的下一部分中介绍。
相反，对于 ParseXml(string)，它会加载一个 XmlDocument。读取文档节点的属性，实例化一个新的 TreeBranch 和一个 Tree。这些当然是实际实现的树和分支。它调用 ParseXml(XmlElement, TreeBranch) 并提供根分支对应的 XmlElement。关于 ParseXml(XmlElement, TreeBranch) 方法的更多信息将在文章的下一部分中介绍。
我们对二进制文件也实现了同样的功能。使用 WriteBinary(string, Encoding) 和 ParseBinary(string, Encoding)，我们简单地创建一个 BinaryWriter 并将树序列化/反序列化到/从二进制文件。
自文章版本 4.1 起，我还实现了两个更简洁的解析器方法：泛型版本 ParseXml<TTree>(...) 和 ParseBinary<TTree>(...)。这些是最简单和最好用的方法。因为我们定义 TTree 必须是 Tree 类型，所以我们确保您只能反序列化特定的树实现（因为 Tree 和 Tree<T> 是抽象的，因此不能直接使用）。
为了能够使用 BinaryFormatter 序列化树，从而使用 .NET 提供的序列化工具，我们需要三件事
- 该类必须实现
ISerializable，这使得我们需要 - 该类必须实现一个
GetObjectData(SerializationInfo, StreamingContext)方法，用于写入数据，以及一个序列化构造函数.ctor(SerializationInfo, StreamingContext)，用于读取数据。GetObjectData(...)方法必须用SecurityPermission属性标记。有关更详细的解释，请参阅 MSDN 文章中关于自定义序列化的部分。 - 该类必须使用
SerializableAttribute标记，才能序列化此类的实例。
在我们的序列化构造函数中，我们简单地读取使用的枚举模式和根节点。因为我们的 TreeBranch 将实现相同的内容，所以我们可以简单地通过使用 info.GetValue(string, Type) 读取一个。在我们的写入方法中，我们做同样的事情，反之亦然。就这么简单。
TreeBranch
我们树的每个元素都将称为 Branch。因此，我们的基类将是 TreeBranch。这个类遵循以下约定
- 分支有一个
protected List<TreeBranch>，用于存储当前分支的所有子分支。 - 分支有一个
public IReadOnlyList<TreeBranch>，它将分支列表包装为只读集合（稍后会解释原因）。 - 分支有一个
Tree属性，用于存储所属树的实例。 - 分支有一个
Parent属性，用于存储父分支。 - 分支有一个
EnumerationMode属性，允许切换枚举模式。 - 分支有两个方法：
AddBranch(TreeBranch)和bool RemoveBranch(TreeBranch)，用于添加/删除更多分支。 - 分支实现了
IEnumerable<TreeBranch>用于枚举（因此即使在单个分支上，而不仅仅是树上，您也可以使用foreach）。 - 分支实现了
ISerializable用于二进制序列化。- 分支实现了一个
protected序列化构造函数：.ctor(SerializationInfo, StreamingContext)，所有派生自Tree的类都必须继承它。 - 分支实现了
SerializableAttribute。
- 分支实现了一个
- （可选）分支实现了一个
Dump(StreamWriter, int)方法，允许数据转储。
[Serializable]
public abstract class TreeBranch : IEnumerable<TreeBranch>, ISerializable
{
protected List<TreeBranch> BranchList;
public Tree Tree { get; internal set; }
public TreeBranch Parent { get; private set; }
public TreeEnumerationMode EnumerationMode { get; set; }
public IReadOnlyList<TreeBranch> Branches => BranchList.AsReadOnly();
protected TreeBranch(TreeEnumerationMode mode = TreeEnumerationMode.DepthFirst)
{
BranchList = new List<TreeBranch>();
EnumerationMode = mode;
}
public void AddBranch(TreeBranch branch)
{
if (!BranchList.Contains(branch))
{
BranchList.Add(branch);
branch.Parent = this;
branch.Tree = Tree;
}
}
public bool RemoveBranch(TreeBranch branch)
{
return BranchList.Remove(branch);
}
public void Dump(string file)
{
using (FileStream fs = new FileStream(file, FileMode.OpenOrCreate))
{
using (StreamWriter writer = new StreamWriter(fs))
{
Dump(writer, 0);
}
}
}
public abstract void Dump(StreamWriter writer, int level);
protected string TabFromLevel(int level)
{
string tabs = "";
for (int i = 1; i <= level; i++)
tabs += '\t';
return tabs;
}
public IEnumerator<TreeBranch> GetEnumerator()
{
return EnumerationMode == TreeEnumerationMode.DepthFirst
? new DepthTreeEnumerator<TreeBranch>(this, null)
: (IEnumerator<TreeBranch>) new BreadthTreeEnumerator<TreeBranch>(this, null);
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
[SecurityPermission(SecurityAction.Demand, SerializationFormatter = true)]
public abstract void GetObjectData(SerializationInfo info, StreamingContext context);
public abstract void WriteXml(XmlDocument document, XmlElement parent);
public abstract void ParseXml(XmlElement element, TreeBranch parent);
public abstract void WriteBinary(BinaryWriter writer);
public abstract void ParseBinary(BinaryReader reader, TreeBranch parent);
}
我们使用只读集合，因为我们要求每个 TreeBranch 都定义了它所属的 Tree 以及一个父分支（除了树的根分支）。这些将在我们的 AddBranch() 和 RemoveBranch() 方法中设置（更好地继承）。因此，我们通过仅向公共提供所有分支的只读集合来强制使用这些方法。
Dump() 方法接受一个 StreamWriter 和一个 int。该方法基本上将当前分支的数据写入新行，并按 level 缩进。生成的文本文件是被转储的树（或分支）的可视化表示。TabFromLevel(int) 简单地构造一个包含 x (level) 个制表符 ('\t') 的 string。旁注：我修复了这个方法——在本文的版本 1 中，该方法有一个小错误（第一级没有缩进）。
序列化魔术
我们的所有五个序列化方法都是 abstract 的。这是因为我们无法知道任何实现实际需要写入/读取的数据类型和数量。然而，这些方法提供了一个基本框架，允许任何实现读取和写入它所需的任何内容，而我们的基类 Tree 仍然自动完成大部分工作。在我们的 TreeBranch 类中，序列化构造函数不是必需的，因为它不像我们的 Tree 那样需要读取任何内容。abstract 分支不包含任何有意义的保存或加载数据。另一方面，我们的 Tree 会反序列化根分支和枚举模式。由于继承，它会加载正确的类型，因为任何实现都是 TreeBranch 类型，并且 .NET 会存储它写入的数据类型（如果您用文本编辑器打开二进制文件，您可能会看到类型名称）。我们自定义的二进制序列化实现也这样做——尽管它只保存一次。Tree 基类在文件开头以类似于 XML 的方式写入。因为我们的树具有固定的分支类型，所以只保存一次就足够了。这就是 .Net 序列化和自定义序列化之间的区别。没有开销。
Tree<T>
现在，在我们构建了 abstract 基树和 abstract 分支类型之后，我们将实现 Tree 的泛型版本，它现在允许最大的灵活性。泛型 Tree<TBranch> 类仅通过使用 new 关键字覆盖某些方法和属性。此外，它还实现了 IEnumerable<TBranch>。因此，使用此树，您可以通过使用基类型 TreeBranch 或泛型类型 TBranch 来迭代其元素。
[Serializable]
public abstract class Tree<TBranch> : Tree, IEnumerable<TBranch> where TBranch : TreeBranch
{
public new TBranch Root => (TBranch) base.Root;
protected Tree(TBranch root, TreeEnumerationMode mode = TreeEnumerationMode.DepthFirst) : base(root, mode)
{
}
protected Tree(SerializationInfo info, StreamingContext context) : base(info, context)
{
}
public void AddBranch(TBranch branch)
{
Root.AddBranch(branch);
}
public bool RemoveBranch(TBranch branch)
{
return Root.RemoveBranch(branch);
}
public new IEnumerator<TBranch> GetEnumerator()
{
return EnumerationMode == TreeEnumerationMode.DepthFirst
? new DepthTreeEnumerator<TBranch>(Root, null)
: (IEnumerator<TBranch>) new BreadthTreeEnumerator<TBranch>(Root, null);
}
public new static Tree<TBranch> ParseXml(string file)
{
return (Tree<TBranch>) Tree.ParseXml(file);
}
public new static Tree<TBranch> ParseBinary(string file, Encoding textEncoding = null)
{
return (Tree<TBranch>) Tree.ParseBinary(file, textEncoding);
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
如您所见，我们的枚举器也有相同的方案。这些将是接下来要实现的。树必须实现一个序列化构造函数，因为我们的基类 Tree 在其序列化构造函数中包含了逻辑。因此，我们需要链接构造函数。任何派生类型都需要调用基构造函数才能成功反序列化整个树。此外，我们用 new 覆盖解析器方法，这样当我们使用例如 Tree<FileSystemTreeBranch>.ParseXml(...) 时，我们就有方法可以返回正确的类型。
TreeEnumerationMode
public enum TreeEnumerationMode
{
/// <summary> Provides a depth-first enumerator. </summary>
DepthFirst,
/// <summary> Provides a breadth-first enumerator. </summary>
BreadthFirst
}
这种枚举应该是不言自明的。
DepthTreeEnumerator
我们再次拥有一个非泛型基枚举器，它完成了大部分工作。它与我们的 abstract 基实现 Tree 兼容。此枚举器深度优先迭代（参见：维基百科“深度优先搜索”）。
public class DepthTreeEnumerator : IEnumerator<TreeBranch>
{
protected TreeBranch Leaf { get; set; }
protected DepthTreeEnumerator SubEnumerator { get; private set; }
private DepthTreeEnumerator ParentEnumerator { get; set; }
private int _currentIndex;
public DepthTreeEnumerator(TreeBranch leaf, DepthTreeEnumerator parent)
{
Leaf = leaf;
ParentEnumerator = parent;
}
public bool MoveNext()
{
if (SubEnumerator != null) return SubEnumerator.MoveNext();
// Has no children, kill parent subenumerator to indicate end of level
if (Current.Branches.Count == 0) return ParentEnumerator.IndicateEndOfLevel();
// Has child so go one level deeper
SubEnumerator = new DepthTreeEnumerator(Current.Branches[0], this);
return true;
}
private bool IndicateEndOfLevel()
{
SubEnumerator = null;
// Go to next branch if another exists
if (Leaf.Branches.Count <= _currentIndex + 1)
return ParentEnumerator != null && ParentEnumerator.IndicateEndOfLevel();
SubEnumerator = new DepthTreeEnumerator(Leaf.Branches[++_currentIndex], this);
return true;
}
public void Reset()
{
_currentIndex = 0;
SubEnumerator?.Dispose();
SubEnumerator = null;
}
public TreeBranch Current => SubEnumerator != null ? SubEnumerator.Current : Leaf;
object IEnumerator.Current => Current;
public void Dispose()
{
SubEnumerator?.Dispose();
SubEnumerator = null;
ParentEnumerator = null;
}
}
现在这个枚举器基本上通过创建自己的树来工作。每个枚举器都有一个 SubEnumerator 和一个 ParentEnumerator。每个枚举器都分配给树中的特定叶子。_currentIndex 定义了枚举指针当前位于哪个子分支。
这个系统相当简单。有两种情况可能发生
SubEnumerator为null，则当前分支（枚举器）上没有更多子分支SubEnumerator不为 null，则存在子分支，并且当前元素是子枚举器的当前元素（继承）。
通过在分支或树上调用 GetEnumerator 来开始枚举。树的匿名方法在其根分支上调用该方法。第一个元素被指向（深度级别 1，分支 1）。一旦您调用 MoveNext()（这由 foreach 自动完成），最顶层的枚举器会检查 SubEnumerator 是否为 null（第 16 行）。如果为 null 并且当前（根）分支有更多子分支，则会实例化一个子枚举器（第 22 行）。这个子枚举器现在指向下一级别的第一个分支。
对 MoveNext 的另一次调用现在被传递给子枚举器（第 16 行）。这个匿名枚举器没有子枚举器（至少在当前循环中）。我们假设级别 2 上的分支没有子分支。它的父枚举器（级别 1 的枚举器；第 19 行）调用 IndicateEndOfLevel() 方法。此调用现在将级别 1 枚举器的子枚举器设置为 null。然后它检查当前分支（级别 1，分支 1）在同一级别是否还有另一个分支。如果是，则 CurrentIndex 增加 1，并为级别 1 上的分支 2 实例化另一个子枚举器。这会一直持续到最后一个分支，我们现在假设它是级别 1 上的分支 2，在同一级别没有更多分支。如果 ParentEnumerator 为 null，则无法再进行 IndicateEndOfLevel() 调用（第 30 行）。这表示所有分支都已迭代，MoveNext() 返回 false，从而结束枚举过程。
信息：我目前没有机会为此描述创建某种可视化。我知道这有点难以理解，但通过分析代码（代码不多且不难）和阅读描述，您最终会明白。如果有人能为所描述的状态提供一些图形，我将不胜感激。尽管如此，我仍然参考了维基百科关于深度优先和广度优先搜索算法的文章，这些文章应该能完美地解释它。
DepthTreeEnumerator<T>
public sealed class DepthTreeEnumerator<TBranch> : DepthTreeEnumerator, IEnumerator<TBranch> where TBranch : TreeBranch
{
public DepthTreeEnumerator(TBranch leaf, DepthTreeEnumerator parent) : base(leaf, parent)
{
}
public new TBranch Current => (TBranch) base.Current;
}
此枚举器的泛型版本允许枚举泛型 Tree<TBranch>。它再次简单地将 TreeBranch 属性与实际泛型类型包装起来。这里唯一需要的是 Current 属性，它再次只使用基类的数据。
BreadthTreeEnumerator
此枚举器具有与我们的 DepthTreeEnumerator 相同的结构。唯一的区别是此枚举器采用广度优先（参见维基百科“广度优先搜索”）。
public class BreadthTreeEnumerator : IEnumerator<TreeBranch>
{
protected TreeBranch Leaf { get; set; }
protected BreadthTreeEnumerator SubEnumerator { get; private set; }
private BreadthTreeEnumerator ParentEnumerator { get; set; }
private int _currentIndex = -1;
public BreadthTreeEnumerator(TreeBranch leaf, BreadthTreeEnumerator parent)
{
Leaf = leaf;
ParentEnumerator = parent;
}
public bool MoveNext()
{
if (SubEnumerator != null) return SubEnumerator.MoveNext();
// First iterate through all branches on the same level
if (Leaf.Branches.Count > _currentIndex + 1)
{
_currentIndex++;
return true;
}
// This level has ben enumerated, so go back to the first element and go one level deeper
_currentIndex = -1;
return PointToNext();
}
private bool PointToNext()
{
int start = _currentIndex < 0 ? 0 : _currentIndex;
for (_currentIndex = start + 1; _currentIndex < Leaf.Branches.Count; _currentIndex++)
{
if (Leaf.Branches[_currentIndex].Branches.Count <= 0) continue;
SubEnumerator = new BreadthTreeEnumerator(Leaf.Branches[_currentIndex], this);
SubEnumerator._currentIndex = 0;
return true;
}
SubEnumerator = null;
return ParentEnumerator != null && ParentEnumerator.PointToNext();
}
public void Reset()
{
_currentIndex = -1;
SubEnumerator = null;
}
public TreeBranch Current =>
SubEnumerator != null ? SubEnumerator.Current : Leaf.Branches[_currentIndex];
object IEnumerator.Current => Current;
public void Dispose()
{
SubEnumerator?.Dispose();
SubEnumerator = null;
ParentEnumerator = null;
}
}
不过，此枚举器略有不同。首先，我们的 _currentIndex 从 -1 开始。这是因为对 MoveNext() 的第一次调用已经遍历了当前级别的分支。DepthTreeEnumerator 首先创建 SubEnumerator。直到下一个周期，当当前的 SubEnumerator 没有更多子分支时，它才会向上遍历树并递增 _currentIndex。
基本上，广度枚举器的工作方式如下：每个枚举器遍历其当前级别上的分支。遍历完成后，_currentIndex 被重置为 -1，并调用 PointToNext()。PointToNext() 使用 _currentIndex 遍历 current 级别上的所有分支，并检查这些分支是否有子分支。通过这种方式，它跳过了死胡同的分支。如果没有剩余的分支，它会调用 ParentEnumerator.PointToNext() 或返回 false。后一种情况仅在我们位于最顶层分支时发生，这将结束枚举。这里重要的是，新创建的子枚举器的索引设置为 0。这是因为在创建新子枚举器的循环之后，Current 属性已经指向该枚举器。如果将其设置为 -1，它将返回第一个文件（不过，我们必须在 Current 属性中实现一个检查，当索引为 -1 时返回 0 元素）。下一个循环会将索引增加到 0 并再次指向同一个分支。第一个条目会被重复。旁注：文章版本 2 的修复。
BreadthTreeEnumerator<T>
public class BreadthTreeEnumerator<T> : BreadthTreeEnumerator,
IEnumerator<T> where T : TreeBranch
{
public BreadthTreeEnumerator(TreeBranch leaf,
BreadthTreeEnumerator parent) : base(leaf, parent)
{
}
public T Current => (T)base.Current;
}
序列化
现在，如果我们想基于 .NET 的 ISerializable 接口实现二进制序列化，我们需要实际实现某种 TreeBranch。我将使用示例应用程序中使用的 FileSystemTreeBranch。该类如下所示
[Serializable]
public sealed class FileSystemTreeBranch : TreeBranch
{
public string Name { get; private set; }
public bool IsDirectory { get; private set; }
public new Tree<FileSystemTreeBranch> Tree => (Tree<FileSystemTreeBranch>) base.Tree;
public FileSystemTreeBranch()
{
}
public FileSystemTreeBranch(string name, bool isDirectory)
{
Name = name;
IsDirectory = isDirectory;
}
private FileSystemTreeBranch(SerializationInfo info, StreamingContext context)
{
// Deserialization
}
public override void Dump(StreamWriter writer, int level)
{
writer.WriteLine($"{TabFromLevel(level)}{Name} |
" + (IsDirectory ? "Directory" : "File"));
foreach (var branch in Branches) branch.Dump(writer, level + 1);
}
[SecurityPermission(SecurityAction.Demand, SerializationFormatter = true)]
public override void GetObjectData(SerializationInfo info, StreamingContext context)
{
// Serialization
}
public override void WriteXml(XmlDocument document, XmlElement parent)
{
// ...
}
public override void ParseXml(XmlElement element, TreeBranch parent)
{
// ...
}
public override void WriteBinary(BinaryWriter writer)
{
// ...
}
public override void ParseBinary(BinaryReader reader, TreeBranch parent)
{
// ...
}
public override string ToString()
{
return Name;
}
}
传统二进制序列化（使用 .Net 提供的 BinaryFormatter）
现在，如果我们想序列化我们的分支类型，我们需要实现 GetObjectData(SerializationInfo, StreamingContext) 方法。这将是我们的实现
[SecurityPermission(SecurityAction.Demand, SerializationFormatter = true)]
public override void GetObjectData(SerializationInfo info, StreamingContext context)
{
info.AddValue("Name", Name);
info.AddValue("IsDirectory", IsDirectory);
info.AddValue("Branches", BranchList.Count);
for (int i = 0; i < Branches.Count; i++)
info.AddValue("Branch" + i, Branches[i]);
}
首先，我们设置名称和 IsDirectory 属性，然后是此分支拥有的子分支数量。它不像简单地序列化列表本身那么容易，所以我们必须稍微改进一下。一旦我们写入了子分支的数量，我们就迭代它们并将其写入。再一次，由于我们的实现是可序列化的，我们只需直接传递实例本身。这基本上是一个递归方法。对象被命名为 'Branch0'、'Branch1' 等。
如果要反序列化，我们需要构造函数
private FileSystemTreeBranch(SerializationInfo info, StreamingContext context)
{
Name = info.GetString("Name");
IsDirectory = info.GetBoolean("IsDirectory");
int branchCount = info.GetInt32("Branches");
if (branchCount == 0) return;
for (int i = 0; i < branchCount; i++)
{
FileSystemTreeBranch branch = (FileSystemTreeBranch)info.GetValue
("Branch" + i, typeof(FileSystemTreeBranch));
AddBranch(branch);
}
}
首先，我们读取我们的属性，然后是我们拥有的分支数量，最后我们运行一个 for 循环并读出所有子分支。再次，这基本上是递归的。构造函数可以是 private 的。格式化程序可以使用任何具有此精确签名的构造函数，无论其访问修饰符如何。
XML 序列化
为了将整个树写入 XML 文件，基类 Tree 创建一个 XmlDocument 并在根分支上调用 WriteXml(XmlDocument, XmlElement)。现在，我们实现这个 abstract 方法
public override void WriteXml(XmlDocument document, XmlElement parent)
{
XmlElement element = document.CreateElement(IsDirectory ? "Directory" : "File");
element.SetAttribute("Name", Name);
foreach (var branch in Branches)
branch.WriteXml(document, element);
parent.AppendChild(element);
}
首先，我们用 document 创建一个新元素，根据类型，我们将其命名为“File”或“Directory”。我们将名称设置为属性，然后迭代所有子分支。我们通过在子分支上调用 WriteXml(...) 递归地遍历树。最后，我们将元素添加到父元素。在示例中使用示例文件夹会得到这个漂亮的小文件
<Tree Type="TreeIterator.FileSystemTree"
BranchType="TreeIterator.FileSystemTreeBranch">
<Directory Name="Test Folder">
<File Name="Level 1 Document 1.txt" />
<File Name="Level 1 Document 2.txt" />
<File Name="Level 1 Document 3.txt" />
<File Name="Level 1 Document 4.txt" />
<Directory Name="Level 1 Folder 1">
<File Name="Level 1 Folder 1 Document 1.txt" />
<File Name="Level 1 Folder 1 Document 2.txt" />
<Directory Name="Level 1 Folder 1 Folder 1">
<File Name="Level 1 Folder 1 Folder 1 Document 1.txt" />
<File Name="Level 1 Folder 1 Folder 1 Document 2.txt" />
<File Name="Level 1 Folder 1 Folder 1 Document 3.txt" />
</Directory>
</Directory>
<Directory Name="Level 1 Folder 2">
<File Name="Level 1 Folder 2 Document 1.txt" />
<File Name="Level 1 Folder 2 Document 2.txt" />
<File Name="Level 1 Folder 2 Document 3.txt" />
</Directory>
</Directory>
</Tree>
为了从该文件重新创建整个树，我们需要实现 ParseXml(XmlElement, TreeBranch) 方法
public override void ParseXml(XmlElement element, TreeBranch parent)
{
Name = element.GetAttribute("Name");
IsDirectory = element.Name == "Directory";
foreach (XmlElement sub in element.ChildNodes.OfType<XmlElement>())
{
FileSystemTreeBranch branch = new FileSystemTreeBranch();
branch.ParseXml(sub, this);
}
parent?.AddBranch(this);
}
我们只需读出名称，设置 IsDirectory 属性，然后遍历此元素的所有子元素，这些子元素等同于子分支。这里重要的是我们使用 LINQ 方法 OfType<XmlElement>()。否则，如果您插入注释或其他 XML 节点类型，它将抛出 InvalidCastException。我们为每个元素创建一个分支，并在新创建的分支上调用 ParseXml(...) 方法，将当前分支作为父级传递。最后，我们将当前分支添加到父级。这里，重要的是我们使用 null 传播运算符 (?.)，因为根节点可能为 null。
二进制序列化
为了序列化一个分支，我们需要实现 WriteBinary(writer)。因为二进制序列化是顺序的，我们不需要任何父元素。树将被“变形”成一维格式。
public override void WriteBinary(BinaryWriter writer)
{
writer.Write(Name);
writer.Write(IsDirectory);
writer.Write(Branches.Count);
foreach (var branch in Branches)
branch.WriteBinary(writer);
}
这里重要的是我们不要忘记序列化包含的分支数量。之后我们无法再获取此信息。错误的数值将导致致命的异常或仅重建实际树的一部分。
public override void ParseBinary(BinaryReader reader, TreeBranch parent)
{
Name = reader.ReadString();
IsDirectory = reader.ReadBoolean();
int branches = reader.ReadInt32();
for (int i = 0; i < branches; i++)
{
FileSystemTreeBranch branch = new FileSystemTreeBranch();
branch.ParseBinary(reader, this);
}
parent?.AddBranch(this);
}
解析器方法反之亦然。我们读出必要的信息并再次设置。我们获取作为此分支子分支的数量，创建一个新分支并调用其上的 ParseBinary(...) 方法，提供当前实例 this 作为父分支。读取所有子分支后，我们将其添加到父分支。再次强调：由于根节点不会有任何父分支，因此使用空传播。
Using the Code
首先，您需要实现一个继承自 Tree 或 Tree<T> 的树。然后，您可以像示例项目一样使用它
tree.EnumerationMode = TreeEnumerationMode.BreadthFirst;
foreach (var branch in tree)
{
Console.WriteLine(branch);
}
tree.EnumerationMode = TreeEnumerationMode.DepthFirst;
foreach (var branch in tree)
{
Console.WriteLine(branch);
}
传统二进制序列化/反序列化
序列化
BinaryFormatter formatter = new BinaryFormatter();
using (FileStream fs = new FileStream(Path.Combine(Environment.CurrentDirectory, "tree.legacybin"), FileMode.OpenOrCreate))
{
formatter.Serialize(fs, tree);
}
反序列化
FileSystemTree fsTree;
using (FileStream fs = new FileStream(file, FileMode.Open))
fsTree = (FileSystemTree) formatter.Deserialize(fs);
XML 序列化/反序列化
序列化
tree.WriteXml(Path.Combine(Environment.CurrentDirectory, "tree.xml"));
反序列化
FileSystemTree fsTree = (FileSystemTree) Tree.ParseXml(file);
二进制序列化/反序列化
序列化
tree.WriteBinary(Path.Combine(Environment.CurrentDirectory, "tree.bin"));
反序列化
fsTree = (FileSystemTree)Tree<FileSystemTreeBranch>.ParseBinary(file);
旁注：您可以使用这两个类的解析方法
fsTree = (FileSystemTree)Tree.ParseBinary(file);
等于
fsTree = (FileSystemTree)Tree<FileSystemTreeBranch>.ParseBinary(file);
等于
fsTree = Tree.ParseBinary<FileSystemTree>(file);
建议您使用 Tree.Parse*<TTree>(...) 或 Tree.Parse*(...) 方法，因为这些方法只进行一次类型转换。Tree<T>.Parse*(...) 版本在最坏的情况下会进行两次类型转换（一次转换为 Tree<T>，然后您很可能会将其转换为 CustomTreeImplementation）。此方法适用于少数特殊用例，例如您实际拥有泛型基本定义（例如在接口中，可由某些编译时未知的类使用，这些类都使用某种 Tree<MyDataBranch>）。您已经看到，大部分逻辑都放在 TreeBranch 实现中，而不是在树中。
欲了解更多详情，请下载示例项目。
性能
我还没有测试过性能。在测试应用程序中，我内置了一个简单的测试，但没有进行真正的性能测试。如果有人愿意进行测试，我将很高兴在此添加您的结果。到目前为止我所看到的确实取决于树的大小。使用示例文件夹（非常小 - 15 个项目），结果如下
- 迭代速度
- 广度优先：~ 2.454 毫秒（冷）/ 0.021 毫秒（热）
- 深度优先：~ 1.111 毫秒（冷）/ 0.008 毫秒（热）
- 输出大小
- 转储： 1 KB
- 传统二进制： 3 KB
- XML： 1 KB
- 二进制： 2 KB
- 序列化速度
- 转储： ~ 3.880 毫秒
- 传统二进制： ~ 1.530 毫秒
- XML： ~ 11.31 毫秒
- 二进制： ~ 3.351 毫秒
- 反序列化速度
- 传统二进制： ~ 1.960 毫秒（冷）/ ~ 0.151 毫秒（热）/ ~ 300 KB 内存
- XML： ~ 4.544 毫秒（冷）/ ~ 0.228 毫秒（热）/ ~ 300 KB 内存
- 二进制： ~ 1.980 毫秒（冷）/ ~ 0.168 毫秒（热）/ ~ 100 KB 内存
而像我整个系统驱动器这样的结构（664093 项）会产生以下时间
- 迭代速度
- 广度优先： ~ 17.56 毫秒（冷）/ 13.72 毫秒（热）
- 深度优先：~ 60.45 毫秒（冷）/ 59.59 毫秒（热）
- 输出大小
- 转储： 28.133 KB / ~ 27.4 MB
- 传统二进制： 108.041 KB / ~ 105 MB
- XML： 44.190 KB / ~ 43.1 MB
- 二进制： 36.161 KB / ~ 35.3 MB
- 序列化速度
- 转储： ~ 323.8 毫秒 (~ 0.324 秒)
- 传统二进制： ~ 5161 毫秒 (~ 5.161 秒)
- XML： ~ 1425 毫秒 (~ 1.425 秒)
- 二进制： ~ 203.5 毫秒 (~ 0.203 秒)
- 反序列化速度
- 传统二进制： ~ 3538 * 10^1 毫秒 [~ 35.38 秒] (冷) / ~ 3677 * 10^1 毫秒 [~ 36.77 秒] (热) / ~ 1.328 MB 内存
- XML： ~ 3547 毫秒 [~ 3.547 秒] (冷) / ~ 3582 毫秒 [~ 3.582 秒] (热) / ~ 268 MB 内存
- 二进制： ~ 2947 毫秒 [~ 2.947 秒] (冷) / ~ 2.990 [~ 2.990 秒] (热) / ~ 125 MB 内存
旁注：枚举时间在文章版本 3.1 之前是错误的。Console.WriteLine() 当然会扭曲结果。现在的性能结果应该更准确（但仍然不是彻底、正确的性能测试）。
结论
如果您不需要深度优先遍历，那么您应该坚持广度优先，因为它速度更快，尤其是在超过 100,000 个项目的大树中。
保存任何树的最佳选择可能是自定义二进制实现。它不仅在输出大小上击败所有其他实现，而且在序列化和反序列化速度上也是如此。正如您在图表（基于上述数据）中看到的那样，这不仅仅是轻微的优势
（越低越好）
（越低越好 / 冷启动时间）
信息：冷启动时间，因为您很少会在热状态下反序列化。此外，比率几乎相同。
关注点
使用这些类，您可以实现任何基于树的数据结构。我提供的示例通过文件系统树的实现演示了这一点。
历史
- 2016年1月18日：版本 1
- 更新：关于兼容性（.NET Framework）和使用的 C# 语言版本的信息；关于
TreeEnumerator功能的结论
- 更新：关于兼容性（.NET Framework）和使用的 C# 语言版本的信息；关于
- 2016年1月19日：版本 2
- 添加了广度优先搜索
- 修复了
TreeBranch.TabFromLevel()中的一个 bug - 添加了深度优先和广度优先搜索的维基百科链接（作为这些枚举器工作原理的解释）
- 改进了测试应用程序（包含示例文件夹、输出和时间）
- 2016年1月19日：版本 3
- 修复了
BreadthTreeEnumerator中的一个 bug，该 bug 导致较深分支的第一个子分支被枚举两次 - 添加了
ISerializable接口和自定义 XML 序列化方法 - 微小的重构（访问器、覆盖等，这些是不必要的）
- 修复了
- 2016年1月19日：版本 3.1
- 在缺失的
ISerializable类上添加了SecurityPermission，并将序列化构造函数设为私有 - 更新了
DepthTreeEnumerator<T>，因为有些部分是冗余的 - 添加了一些更详细的性能结果（热和冷）
- 更新了性能测试和结果（犯了一个大错误，结果完全错误——对此深表歉意）
- 在缺失的
- 2016年1月19日：版本 4
- 在介绍中添加了信息
- 添加了目录
- 添加了自定义二进制实现
- 为
Tree<T>添加了解析方法的覆盖 - 添加了更详细的性能测试和图表
- 2016年1月20日：版本 4.1
- 向
Tree添加了泛型解析器方法 - 扩展了反序列化代码使用说明
- 次要更改
- 向