C＃中的树数据结构

我正在寻找C＃中的树或graphics数据结构，但我想没有提供一个。 使用C＃2.0进行数据结构的广泛检查解释了一些原因。 有没有一个常用的提供这种function的便利库？ 也许是通过战略模式来解决文章中提出的问题。

我感觉有点傻，实现我自己的树，就像我会实现我自己的ArrayList。

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

Answer 1

我最好的build议是没有标准的树型数据结构，因为有太多的方法可以实现，所以用一种解决scheme覆盖所有的基础是不可能的。 解决scheme越具体，对任何给定问题适用的可能性就越小。 我甚至讨厌LinkedList – 如果我想要一个循环链表？

你需要实现的基本结构将是一个节点的集合，这里有一些选项让你开始。 我们假设类Node是整个解决scheme的基类。

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

如果你需要在树上导航，那么Node类需要一个到其父节点的链接。

构build一个AddChild方法来处理这两点的所有细节以及必须实现的任何其他业务逻辑（儿童限制，孩子sorting等）

Answer 2

我讨厌承认它，但是我最终使用链表来编写自己的树类。 在一个不相关的说明中，我刚刚发现了这个圆形的东西，当它附着到我称之为“轴”的东西上时，便于运输货物。

Answer 3

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); } } 

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

Answer 4

这里是我的，和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())); } } } 

Answer 5

又一个树形结构：

 public class TreeNode<T> : IEnumerable<TreeNode<T>> { public T Data { get; set; } public TreeNode<T> Parent { get; set; } public ICollection<TreeNode<T>> Children { get; set; } public TreeNode(T data) { this.Data = data; this.Children = new LinkedList<TreeNode<T>>(); } public TreeNode<T> AddChild(T child) { TreeNode<T> childNode = new TreeNode<T>(child) { Parent = this }; this.Children.Add(childNode); return childNode; } ... // for iterator details see below link } 

示例用法：

 TreeNode<string> root = new TreeNode<string>("root"); { TreeNode<string> node0 = root.AddChild("node0"); TreeNode<string> node1 = root.AddChild("node1"); TreeNode<string> node2 = root.AddChild("node2"); { TreeNode<string> node20 = node2.AddChild(null); TreeNode<string> node21 = node2.AddChild("node21"); { TreeNode<string> node210 = node21.AddChild("node210"); TreeNode<string> node211 = node21.AddChild("node211"); } } TreeNode<string> node3 = root.AddChild("node3"); { TreeNode<string> node30 = node3.AddChild("node30"); } } 

奖金
看到完全成熟的树：

• 迭代器
• search
• 的Java / C＃

https://github.com/gt4dev/yet-another-tree-structure

Answer 6

一般优秀的C5通用集合库有几个不同的基于树的数据结构，包括集合，包和字典。 源代码是可用的，如果你想研究他们的实现细节。 （我已经在生产代码中使用了C5集合，结果很好，尽pipe我没有具体使用任何树结构。）

Answer 7

见http://quickgraph.codeplex.com/

QuickGraph为.Net 2.0及更高版本提供通用的定向/无向图数据结构和algorithm。 QuickGraph自带algorithm，如深度优先search，呼吸优先search，A *search，最短path，k-最短path，最大stream量，最小生成树，最小共同祖先等。QuickGraph支持MSAGL，GLEE和Graphviz渲染graphics，序列化到GraphML等…

Answer 8

如果您想编写自己的代码，可以从这个由六部分组成的文档开始，详细介绍C＃2.0数据结构的有效使用以及如何分析C＃中数据结构的实现。 每篇文章都有示例和一个安装程序，您可以按照样本进行操作。

Scott Mitchell的“使用C＃2.0进行数据结构的广泛考察”

Answer 9

我有一些解决scheme的扩展。

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

注意，它与非通用实现不同，不需要在“NodeWorker”中投射“节点”。

这是我的例子：

 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); } 

Answer 10

试试这个简单的例子。

 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 } 

Answer 11

我创build了一个可以帮助其他人的Node类 。 该类有如下属性：

• 孩子
• 祖先
• 后人
• 兄弟姐妹
• 节点的级别
• 亲
• 根
• 等等。

也有可能将一个Id和一个ParentId项目的平面列表转换为一个树。 节点拥有对子节点和父节点的引用，所以可以使迭代节点相当快。

Answer 12

因为没有提到，所以我想请大家注意一下现在发布的.net代码库：特别是实现Red-Black-Tree的SortedSet的代码：

https://github.com/Microsoft/referencesource/blob/master/System/compmod/system/collections/generic/sortedset.cs

但是，这是一个平衡的树状结构。 所以我的回答是更多的参考，我相信是.net核心库中唯一的本地树形结构。

Answer 13

我已经完成了@Berezh共享的代码。

  public class TreeNode<T> : IEnumerable<TreeNode<T>> { public T Data { get; set; } public TreeNode<T> Parent { get; set; } public ICollection<TreeNode<T>> Children { get; set; } public TreeNode(T data) { this.Data = data; this.Children = new LinkedList<TreeNode<T>>(); } public TreeNode<T> AddChild(T child) { TreeNode<T> childNode = new TreeNode<T>(child) { Parent = this }; this.Children.Add(childNode); return childNode; } public IEnumerator<TreeNode<T>> GetEnumerator() { throw new NotImplementedException(); } IEnumerator IEnumerable.GetEnumerator() { return (IEnumerator)GetEnumerator(); } } public class TreeNodeEnum<T> : IEnumerator<TreeNode<T>> { int position = -1; public List<TreeNode<T>> Nodes { get; set; } public TreeNode<T> Current { get { try { return Nodes[position]; } catch (IndexOutOfRangeException) { throw new InvalidOperationException(); } } } object IEnumerator.Current { get { return Current; } } public TreeNodeEnum(List<TreeNode<T>> nodes) { Nodes = nodes; } public void Dispose() { } public bool MoveNext() { position++; return (position < Nodes.Count); } public void Reset() { position = -1; } } 

Answer 14

大多数树木是由您正在处理的数据组成的。

假设你有一个包含某人parents细节的person ，你愿意把树结构作为你的“领域类”的一部分，还是使用一个单独的树类来包含你的人物对象的链接？ 考虑一个简单的操作，比如获得一个person的grandchildren ，这个代码是否应该在person ，或者人类的用户是否应该知道一个单独的树类？

另一个例子是编译器中的一个分析树…

这两个例子都显示了树的概念是数据领域的一部分，并且使用单独的通用树至less使创build的对象数增加了一倍，并且使得API难以再次编程。

我们想要的是重用标准树操作的方法，而不必为所有树重新实现它们，同时不必使用标准的树类。 Boost试图为C ++解决这种types的问题，但是我还没有看到.NET的任何效果。

Answer 15

这是一棵树

 public class Tree<T> : List<Tree<T>> { public T Data { get; private set; } public Tree(T data) { this.Data = data; } public Tree<T> Add(T data) { var node = new Tree<T>(data); this.Add(node); return node; } } 

你甚至可以使用初始化器：

  var tree = new Tree<string>("root") { new Tree<string>("sample") { "console1" } }; 

Answer 16

如果要在GUI上显示此树，可以使用TreeView和TreeNode 。 （我想在技术上你可以创build一个TreeNode而不需要把它放在一个GUI上，但是它比一个简单的本地TreeNode实现有更多的开销。）

Answer 17

我已经添加完整的解决scheme和使用上面的NTree类的示例，还添加了“AddChild”方法…

  public class NTree<T> { public T data; public LinkedList<NTree<T>> children; public NTree(T data) { this.data = data; children = new LinkedList<NTree<T>>(); } public void AddChild(T data) { var node = new NTree<T>(data) { Parent = this }; children.AddFirst(node); } public NTree<T> Parent { get; private set; } 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, string t, ref NTree<T> r) { visitor(node.data, node, t, ref r); foreach (NTree<T> kid in node.children) Traverse(kid, visitor, t, ref r); } } public static void DelegateMethod(KeyValuePair<string, string> data, NTree<KeyValuePair<string, string>> node, string t, ref NTree<KeyValuePair<string, string>> r) { string a = string.Empty; if (node.data.Key == t) { r = node; return; } } 

运用

  NTree<KeyValuePair<string, string>> ret = null; tree.Traverse(tree, DelegateMethod, node["categoryId"].InnerText, ref ret); 

Answer 18

这是我执行BST

 class BST { public class Node { public Node Left { get; set; } public object Data { get; set; } public Node Right { get; set; } public Node() { Data = null; } public Node(int Data) { this.Data = (object)Data; } public void Insert(int Data) { if (this.Data == null) { this.Data = (object)Data; return; } if (Data > (int)this.Data) { if (this.Right == null) { this.Right = new Node(Data); } else { this.Right.Insert(Data); } } if (Data <= (int)this.Data) { if (this.Left == null) { this.Left = new Node(Data); } else { this.Left.Insert(Data); } } } public void TraverseInOrder() { if(this.Left != null) this.Left.TraverseInOrder(); Console.Write("{0} ", this.Data); if (this.Right != null) this.Right.TraverseInOrder(); } } public Node Root { get; set; } public BST() { Root = new Node(); } } 

Answer 19

如果您需要使用较less内存的根树数据结构实现，则可以按如下所示编写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 }