Почему нет класса дерева in.NET?

библиотека базовых классов в .NET имеет отличные структуры данных для коллекций (список, очередь, стек, словарь), но, как ни странно, она не содержит никаких структур данных для двоичных деревьев. Это очень полезная структура для некоторых алгоритмов, таких как те, которые предлагают различные пути обхода. Я ищу правильно написанную, свободную реализацию.

Я просто слепой, и не находя его... он похоронен где-то в ОУЗ? Если нет, может кто-то рекомендуем бесплатные или с открытым исходным кодом на C#/.Net библиотека для бинарных деревьев? Предпочтительно тот, который использует дженерики.

EDIT: уточнить, что я ищу. Меня не интересуют упорядоченные коллекции словарей, которые внутренне используют дерево. На самом деле меня интересует двоичное дерево, которое предоставляет свою структуру, чтобы вы могли делать такие вещи, как извлечение поддеревьев или выполнение обхода после исправления на узлах. В идеале такой класс может быть расширен для обеспечения поведения специализированные деревья (т. е. Красный / черный, AVL, сбалансированный и т. д.).

8 77
c# .net data-structures

8 ответов:

вы правы, в BCL ничего нет. Я подозреваю, что это связано с тем, что выбор использования дерева обычно является детализацией реализации и в противном случае является нетрадиционным способом доступа к данным. То есть вы не говорите: "binary-search-for element #37"; вместо этого вы говорите: "get me element #37".

но вы взглянули на C5? Это супер-удобно, и у них есть несколько реализаций дерева (1,2,3).

27

Вы можете определить свой собственный:

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

или unkeyed:

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

Что бы вы хотели от такой реализации?

бинарное дерево? Красно-черные? Дерево радикса? Б-дерево? Р-дерево? R*-дерева?

дерево-это скорее шаблон, чем структура данных, и они, как правило, используются там, где важна производительность (поэтому детали реализации, вероятно, тоже имеют значение). Если бы BCL включал какой-то класс дерева, вам все равно пришлось бы свернуть свой собственный

36

Я считаю, что SortedDictionary как вставка журнала (n), характеристики извлечения, которые вы ожидаете от структуры данных дерева.

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

14

SortedSet<T> реализовано в виде двоичного дерева поиска ref. SortedDictionary<TKey, TValue> внутренне использует SortedSet<T> Так это тоже бинарное дерево поиска ref.

12

нет, нет "Tree<T> - Как " введите в BCL (что-то, что всегда озадачивало меня), но вот хорошая статья это поможет вам реализовать свой собственный В C#.

Я думаю, вы можете сделать аргумент, что древовидные структуры данных реже используются в приложениях, для которых обычно используется .NET (бизнес-приложения, приложения для перемещения данных и т. д.). Тем не менее, я согласен с вами, странно, что BCL не имеет реализации на все.

8

эта серия статей была полезна для меня, когда я должен был написать свой собственный особенно Часть 3 и 4.

обширное изучение структур данных

1

здесь TreeNode вы можете использовать. Он не является универсальным и скрытым в windows forms и используется с элементом управления treeview, но вы также можете использовать его в другом месте.

-5