为什么在.NET 中没有 Tree < T > 类？

中的基类库。NET 为集合提供了一些优秀的数据结构(List、 Queue、 Stack、 Dictionary) ，但奇怪的是，它不包含任何用于二叉树的数据结构。对于某些算法来说，这是一个非常有用的结构，比如那些利用不同遍历路径的算法。我正在寻找一个正确的编写，免费实现。

难道我只是瞎了眼，找不到它... 它被埋在 BCL 的某个地方？如果没有，是否可以推荐一个免费或开源的 C #/。用于二叉树的 NET 库？最好是使用仿制药的。

编辑: 为了弄清楚我在寻找什么。我对内部使用树的有序字典集合不感兴趣。实际上，我对二叉树很感兴趣——一种公开其结构的结构，这样您就可以做一些事情，比如提取子树，或者在节点上执行修复后遍历。理想情况下，这样一个类可以扩展为提供特定树的行为(即。红/黑、吸血鬼联盟、平衡等)。

41347 次浏览
小开

No, there isn't any "Tree<T>-like" type in the BCL (something that has always puzzled me as well) but here is a good article that will walk you through implementing your own in C#.

I guess you could make the argument that tree-based data structures are less commonly used in the kind of applications that .NET is usually used for (business apps, data-moving apps, etc.). Still, I agree with you, it is strange that the BCL has no implementation at all.

小开

There's a TreeNode you can use. It's not generic and hidden away in windows forms and used with the treeview control, but you can use it elsewhere as well.

小开

I believe that SortedDictionary as the log(n) insert, retrieval characteristics that you would expect from a Tree Data Stucture.

http://msdn.microsoft.com/en-us/library/f7fta44c(VS.80).aspx

小开

SortedSet<T> is implemented as a binary search treeref. SortedDictionary<TKey, TValue> internally makes use of SortedSet<T> so it too is a binary search tree ref.

小开

What would you want from such an implementation?

Binary tree? Red-black? Radix tree? B-tree? R-tree? R*-tree?

A tree is more a pattern than a data structure, and they tend to be used where performance matters (so implementation details probably matter too). If the BCL included some kind of a tree class, you'd only have to roll your own anyway

小开

You could define your own:

public class MyTree<K, V> : Dictionary<K, MyTree<K, V>>
{
public V Value { get; set; }
}

Or unkeyed:

public class MyTree<V> : HashSet<MyTree<V>>
{
public V Value { get; set; }
}
小开

This series of articles was helpful for me when I had to write my own especially part 3 and 4.

An Extensive Examination of Data Structures

小开
最佳答案

You're right, there's nothing in the BCL. I suspect this is because the choice of whether to use a tree is typically an implementation detail and is otherwise an unconventional way to access data. That is, you don't say, "binary-search-for element #37"; instead, you say, "get me element #37".

But have you taken a look at C5? It's super-handy and they have several tree implementations (1, 2, 3).


提交答案