C#中的树数据结构

Tree data structure in C#

提问by stimms

I was looking for a tree or graph data structure in C# but I guess there isn't one provided. An Extensive Examination of Data Structures Using C# 2.0explains a bit about why. Is there a convenient library which is commonly used to provide this functionality? Perhaps through a strategy pattern to solve the issues presented in the article.

我在 C# 中寻找树或图形数据结构，但我想没有提供。使用 C# 2.0 对数据结构的广泛检查解释了一些原因。是否有一个方便的库通常用于提供此功能？也许通过一种策略模式来解决文章中提出的问题。

I feel a bit silly implementing my own tree, just as I would implementing my own ArrayList.

我觉得实现我自己的树有点傻，就像我实现我自己的 ArrayList 一样。

I just want a generic tree which can be unbalanced. Think of a directory tree. C5 looks nifty, but their tree structures seem to be implemented as balanced red-black trees better suited to search than representing a hierarchy of nodes.

我只想要一个可以不平衡的通用树。想想目录树。C5 看起来很漂亮，但它们的树结构似乎实现为平衡的红黑树，而不是表示节点层次结构，更适合搜索。

采纳答案by David Boike

My best advice would be that there is no standard tree data structure because there are so many ways you could implement it that it would be impossible to cover all bases with one solution. The more specific a solution, the less likely it is applicable to any given problem. I even get annoyed with LinkedList - what if I want a circular linked list?

我最好的建议是没有标准的树数据结构，因为有很多方法可以实现它，以至于不可能用一个解决方案覆盖所有基础。解决方案越具体，它就越不可能适用于任何给定的问题。我什至对 LinkedList 感到恼火——如果我想要一个循环链表怎么办？

The basic structure you'll need to implement will be a collection of nodes, and here are some options to get you started. Let's assume that the class Node is the base class of the entire solution.

您需要实现的基本结构将是节点的集合，这里有一些选项可以帮助您入门。让我们假设类 Node 是整个解决方案的基类。

If you need to only navigate down the tree, then a Node class needs a List of children.

如果您只需要沿着树向下导航，那么 Node 类需要一个子项列表。

If you need to navigate up the tree, then the Node class needs a link to its parent node.

如果您需要向上导航树，则 Node 类需要一个到其父节点的链接。

Build an AddChild method that takes care of all the minutia of these two points and any other business logic that must be implemented (child limits, sorting the children, etc.)

构建一个 AddChild 方法来处理这两点的所有细节以及必须实现的任何其他业务逻辑（子限制、子项排序等）

回答by McKenzieG1

The generally excellent C5 Generic Collection Libraryhas several different tree-based data structures, including sets, bags and dictionaries. Source code is available if you want to study their implementation details. (I have used C5 collections in production code with good results, although I haven't used any of the tree structures specifically.)

普遍优秀的C5 Generic Collection Library有几种不同的基于树的数据结构，包括集合、包和字典。如果您想研究它们的实现细节，可以使用源代码。（我在生产代码中使用了 C5 集合，效果很好，尽管我没有专门使用任何树结构。）

回答by user7116

If you would like to write your own, you can start with this six-part document detailing effective usage of C# 2.0 data structures and how to go about analyzing your implementation of data structures in C#. Each article has examples and an installer with samples you can follow along with.

如果您想自己编写，可以从这个由六部分组成的文档开始，详细介绍 C# 2.0 数据结构的有效用法以及如何分析您在 C# 中的数据结构实现。每篇文章都有示例和一个安装程序，其中包含您可以遵循的示例。

“An Extensive Examination of Data Structures Using C# 2.0”by Scott Mitchell

Scott Mitchell 的“使用 C# 2.0 对数据结构的广泛检查”

回答by Aaron Gage

delegate void TreeVisitor<T>(T nodeData);

class NTree<T>
{
    private T data;
    private LinkedList<NTree<T>> children;

    public NTree(T data)
    {
         this.data = data;
        children = new LinkedList<NTree<T>>();
    }

    public void AddChild(T data)
    {
        children.AddFirst(new NTree<T>(data));
    }

    public NTree<T> GetChild(int i)
    {
        foreach (NTree<T> n in children)
            if (--i == 0)
                return n;
        return null;
    }

    public void Traverse(NTree<T> node, TreeVisitor<T> visitor)
    {
        visitor(node.data);
        foreach (NTree<T> kid in node.children)
            Traverse(kid, visitor);
    }
}

Simple recursive implementation... < 40 lines of code... You just need to keep a reference to the root of the tree outside of the class, or wrap it in another class, maybe rename to TreeNode??

简单的递归实现... < 40行代码...你只需要在类之外保留对树根的引用，或者将其包装在另一个类中，也许重命名为TreeNode？？

回答by nietras

See http://quickgraph.codeplex.com/

请参阅http://quickgraph.codeplex.com/

QuickGraph provides generic directed/undirected graph datastructures and algorithms for .Net 2.0 and up. QuickGraph comes with algorithms such as depth first seach, breath first search, A* search, shortest path, k-shortest path, maximum flow, minimum spanning tree, least common ancestors, etc... QuickGraph supports MSAGL, GLEE, and Graphviz to render the graphs, serialization to GraphML, etc...

QuickGraph 为 .Net 2.0 及更高版本提供通用的有向/无向图数据结构和算法。QuickGraph自带深度优先搜索、呼吸优先搜索、A*搜索、最短路径、k-最短路径、最大流量、最小生成树、最小公共祖先等算法...... QuickGraph支持MSAGL、GLEE和Graphviz渲染图形，序列化到 GraphML 等...

回答by Ronnie Overby

Here's mine, which is very similar to Aaron Gage's, just a little more conventional, in my opinion. For my purposes, I haven't ran into any performance issues with List<T>. It would be easy enough to switch to a LinkedList if needed.

这是我的，在我看来，它与Aaron Gage 的非常相似，只是更传统一些。出于我的目的，我没有遇到任何性能问题List<T>。如果需要，切换到 LinkedList 会很容易。

---

---

namespace Overby.Collections
{
    public class TreeNode<T>
    {
        private readonly T _value;
        private readonly List<TreeNode<T>> _children = new List<TreeNode<T>>();

        public TreeNode(T value)
        {
            _value = value;
        }

        public TreeNode<T> this[int i]
        {
            get { return _children[i]; }
        }

        public TreeNode<T> Parent { get; private set; }

        public T Value { get { return _value; } }

        public ReadOnlyCollection<TreeNode<T>> Children
        {
            get { return _children.AsReadOnly(); }
        }

        public TreeNode<T> AddChild(T value)
        {
            var node = new TreeNode<T>(value) {Parent = this};
            _children.Add(node);
            return node;
        }

        public TreeNode<T>[] AddChildren(params T[] values)
        {
            return values.Select(AddChild).ToArray();
        }

        public bool RemoveChild(TreeNode<T> node)
        {
            return _children.Remove(node);
        }

        public void Traverse(Action<T> action)
        {
            action(Value);
            foreach (var child in _children)
                child.Traverse(action);
        }

        public IEnumerable<T> Flatten()
        {
            return new[] {Value}.Concat(_children.SelectMany(x => x.Flatten()));
        }
    }
}

回答by Jake

In case you need a rooted tree data structure implementation that uses less memory, you can write your Node class as follows (C++ implementation):

如果您需要使用较少内存的有根树数据结构实现，您可以按如下方式编写 Node 类（C++ 实现）：

class Node {
       Node* parent;
       int item; // depending on your needs

       Node* firstChild; //pointer to left most child of node
       Node* nextSibling; //pointer to the sibling to the right
}

回答by Erik Nagel

I have a little extension to the solutions.

我对解决方案有一些扩展。

Using a recursive generic declaration and a deriving subclass you can better concentrate on your actual target.

使用递归泛型声明和派生子类，您可以更好地专注于您的实际目标。

Notice, it's different from a non generic implementation, you don`t need to cast 'node' in 'NodeWorker'.

请注意，它与非通用实现不同，您不需要在“NodeWorker”中强制转换“node”。

Here's my example:

这是我的例子：

public class GenericTree<T> where T : GenericTree<T> // recursive constraint  
{
  // no specific data declaration  

  protected List<T> children;

  public GenericTree()
  {
    this.children = new List<T>();
  }

  public virtual void AddChild(T newChild)
  {
    this.children.Add(newChild);
  }

  public void Traverse(Action<int, T> visitor)
  {
    this.traverse(0, visitor);
  }

  protected virtual void traverse(int depth, Action<int, T> visitor)
  {
    visitor(depth, (T)this);
    foreach (T child in this.children)
      child.traverse(depth + 1, visitor);
  }
}

public class GenericTreeNext : GenericTree<GenericTreeNext> // concrete derivation
{
  public string Name {get; set;} // user-data example

  public GenericTreeNext(string name)
  {
    this.Name = name;
  }
}

static void Main(string[] args)  
{  
  GenericTreeNext tree = new GenericTreeNext("Main-Harry");  
  tree.AddChild(new GenericTreeNext("Main-Sub-Willy"));  
  GenericTreeNext inter = new GenericTreeNext("Main-Inter-Willy");  
  inter.AddChild(new GenericTreeNext("Inter-Sub-Tom"));  
  inter.AddChild(new GenericTreeNext("Inter-Sub-Magda"));  
  tree.AddChild(inter);  
  tree.AddChild(new GenericTreeNext("Main-Sub-Chantal"));  
  tree.Traverse(NodeWorker);  
}  

static void NodeWorker(int depth, GenericTreeNext node)  
{                                // a little one-line string-concatenation (n-times)
  Console.WriteLine("{0}{1}: {2}", String.Join("   ", new string[depth + 1]), depth, node.Name);  
}  

回答by Berezh

Try this simple sample.

试试这个简单的示例。

public class TreeNode<TValue>
{
    #region Properties
    public TValue Value { get; set; }
    public List<TreeNode<TValue>> Children { get; private set; }
    public bool HasChild { get { return Children.Any(); } }
    #endregion
    #region Constructor
    public TreeNode()
    {
        this.Children = new List<TreeNode<TValue>>();
    }
    public TreeNode(TValue value)
        : this()
    {
        this.Value = value;
    }
    #endregion
    #region Methods
    public void AddChild(TreeNode<TValue> treeNode)
    {
        Children.Add(treeNode);
    }
    public void AddChild(TValue value)
    {
        var treeNode = new TreeNode<TValue>(value);
        AddChild(treeNode);
    }
    #endregion
}

回答by Alex Siepman

I create a Node classthat could be helpfull for other people. The class has properties like:

我创建了一个可能对其他人有帮助的Node 类。该类具有以下属性：

• Children
• Ancestors
• Descendants
• Siblings
• Level of the node
• Parent
• Root
• Etc.

• 孩子们
• 祖先
• 后代
• 兄弟姐妹
• 节点级别
• 家长
• 根
• 等等。

There is also the possibility to convert a flat list of items with an Id and a ParentId to a tree. The nodes holds a reference to both the children and the parent, so that makes iterating nodes quite fast.

还可以将具有 Id 和 ParentId 的项目的平面列表转换为树。节点拥有对子节点和父节点的引用，因此迭代节点非常快。