древовидная структура данных в c #

<p>я искал древовидную или графическую структуру данных в c #, но, по-моему, ее нет. <a href="http://msdn.microsoft.com/en-us/library/ms379574.aspx">обширный анализ структур данных с использованием c # 2.</a> объясняет, почему. есть ли удобная библиотека, которая обычно используется для обеспечения этой функциональности? возможно, через шаблон стратегии для решения вопросов, представленных в статье.</p><p>я чувствую себя немного глупо, реализуя свое собственное дерево, так же, как я реализую свой собственный arraylist.</p><p>я просто хочу общее дерево, которое может быть неуравновешенным. подумайте о дереве каталогов. c5 выглядит изящно, но их древовидные структуры кажутся реализованными в виде сбалансированных красно-черных деревьев, которые лучше подходят для поиска, чем для представления иерархии узлов.</p>

<p>мой лучший совет: стандартная древовидная структура данных отсутствует, потому что вы можете реализовать ее так много способов, что невозможно охватить все базы одним решением. чем конкретнее решение, тем менее вероятно, что оно применимо к любой конкретной проблеме. меня даже раздражает linkedlist - что если я хочу круглый список ссылок?</p><p>базовая структура, которую вам нужно реализовать, будет набором узлов, и вот несколько вариантов, с которых можно начать. предположим, что класс node является базовым классом всего решения.</p><p>если вам нужно перемещаться только по дереву, то классу node необходим список дочерних элементов.</p><p>если вам нужно перемещаться вверх по дереву, то классу node нужна ссылка на его родительский узел.</p><p>создайте метод addchild, который позаботится обо всех мелочах этих двух точек и любой другой бизнес-логике, которая должна быть реализована (дочерние ограничения, сортировка дочерних элементов и т.д.)</p>

<p>ненавижу это признавать, но в итоге я написал свой собственный класс дерева, используя связанный список. на несвязанной ноте я только что обнаружил эту круглую вещь, которая, будучи прикрепленной к вещи, которую я называю "осью", облегчает транспортировку товаров.</p>

<pre><code>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); } } </code></pre><p>простая рекурсивная реализация ... <40 строк кода ... вам просто нужно сохранить ссылку на корень дерева вне класса или обернуть его в другом классе, возможно, переименовать в treenode ??</p>

<p>вот мой, который очень похож на <a href="https://stackoverflow.com/a/2012855/64334">аарона гейджа</a> , на мой взгляд, немного более условно. в моих целях я не сталкивался с проблемами производительности с <code>list<t></code>. было бы достаточно легко переключиться на linkedlist, если это необходимо.</p><hr><pre><code>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())); } } } </code></pre>

<p>еще одна древовидная структура:</p><pre><code>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 } </code></pre><p>пример использования:</p><pre><code>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"); } } </code></pre><p><strong>бонус</strong><br> см. полноценное дерево с:</p><ul> <li>итератор</li> <li>поиск</li> <li>java/c #</li> </ul><p> <a href="https://github.com/gt4dev/yet-another-tree-structure">https://github.com/gt4dev/yet-another-tree-structure</a> </p>

<p>обычно превосходный <a href="http://www.itu.dk/research/c5/">c5 generic collection library</a> имеет несколько различных древовидных структур данных, включая наборы, пакеты и словари. исходный код доступен, если вы хотите изучить детали их реализации. (я использовал коллекции c5 в рабочем коде с хорошими результатами, хотя я не использовал ни одну из древовидных структур специально.)</p>

<p>смотрите <a href="http://quickgraph.codeplex.com/">http://quickgraph.codeplex.com/</a> </p><p>quickgraph предоставляет общие структуры и алгоритмы ориентированных/ненаправленных графов для .net 2.0 и выше. quickgraph поставляется с такими алгоритмами, как поиск по глубине, поиск по дыханию, поиск a *, кратчайший путь, k-кратчайший путь, максимальный поток, минимальное связующее дерево, наименьшие общие предки и т.д. quickgraph поддерживает msagl, glee и graphviz для рендеринг графиков, сериализация в graphml и т. д.</p>

<p>если вы хотите написать свой собственный, вы можете начать с этого документа, состоящего из шести частей, подробно описывающего эффективное использование структур данных c # 2.0 и как анализировать реализацию ваших структур данных в c #. в каждой статье есть примеры и установщик с образцами, за которыми вы можете следить.</p><p> <a href="http://msdn.microsoft.com/en-us/library/ms364091(vs.80).aspx">"обширный анализ структур данных с использованием c # 2.0"</a> скотт митчелл</p>

<p>у меня есть небольшое расширение для решений.</p><p>используя рекурсивное обобщенное объявление и производный подкласс, вы можете лучше сконцентрироваться на своей реальной цели.</p><p>обратите внимание, что это отличается от не универсальной реализации, вам не нужно приводить 'node' в 'nodeworker'.</p><p>вот мой пример:</p><pre><code>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); } </code></pre>

<p>попробуйте этот простой пример.</p><pre><code>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 } </code></pre>

<p>я создаю <a href="http://www.siepman.nl/blog/post/2013/07/30/tree-node-nodes-descendants-ancestors.aspx">класс узла</a> , который может быть полезен для других людей. у класса есть свойства как:</p><ul> <li>дети</li> <li>предки</li> <li>потомки</li> <li>братья и сестры</li> <li>уровень узла</li> <li>родитель</li> <li>root</li> <li>и т.п.</li> </ul><p>существует также возможность преобразовать плоский список элементов с id и parentid в дерево. узлы содержат ссылку как на дочерние, так и на родительские элементы, что делает итерацию узлов достаточно быстрой.</p>

<p>поскольку это не упомянуто, я хотел бы, чтобы вы обратили внимание на уже выпущенную базу кода .net: в частности, код для <code>sortedset</code>, который реализует red-black-tree:</p><p> <a href="https://github.com/microsoft/referencesource/blob/master/system/compmod/system/collections/generic/sortedset.cs">https://github.com/microsoft/referencesource/blob/master/system/compmod/system/collections/generic/sortedset.cs</a> </p><p>это, однако, сбалансированная древовидная структура. поэтому мой ответ - скорее ссылка на то, что я считаю единственной нативной древовидной структурой в базовой библиотеке .net.</p>

<p>вот дерево</p><pre><code>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; } } </code></pre><p>вы даже можете использовать инициализаторы:</p><pre><code> var tree = new tree<string>("root") { new tree<string>("sample") { "console1" } }; </code></pre>

<p>вот мой собственный:</p><pre><code>class program { static void main(string[] args) { var tree = new tree<string>() .begin("fastfood") .begin("pizza") .add("margherita") .add("marinara") .end() .begin("burger") .add("cheese burger") .add("chili burger") .add("rice burger") .end() .end(); tree.nodes.foreach(p => printnode(p, 0)); console.readkey(); } static void printnode<t>(treenode<t> node, int level) { console.writeline("{0}{1}", new string(' ', level * 3), node.value); level++; node.children.foreach(p => printnode(p, level)); } } public class tree<t> { private stack<treenode<t>> m\_stack = new stack<treenode<t>>(); public list<treenode<t>> nodes { get; } = new list<treenode<t>>(); public tree<t> begin(t val) { if (m\_stack.count == 0) { var node = new treenode<t>(val, null); nodes.add(node); m\_stack.push(node); } else { var node = m\_stack.peek().add(val); m\_stack.push(node); } return this; } public tree<t> add(t val) { m\_stack.peek().add(val); return this; } public tree<t> end() { m\_stack.pop(); return this; } } public class treenode<t> { public t value { get; } public treenode<t> parent { get; } public list<treenode<t>> children { get; } public treenode(t val, treenode<t> parent) { value = val; parent = parent; children = new list<treenode<t>>(); } public treenode<t> add(t val) { var node = new treenode<t>(val, this); children.add(node); return node; } } </code></pre><p>результат:</p><pre><code>fastfood pizza margherita marinara burger cheese burger chili burger rice burger </code></pre>

<p>я выполнил код, которым поделился @berezh.</p><pre><code> 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; } } </code></pre>

<p>большинство деревьев сформированы данными, которые вы обрабатываете.</p><blockquote> <p>скажем, у вас есть класс <code>person</code>, который включает в себя детали чьего-то <code>parents</code>, вы бы предпочли иметь древовидную структуру как часть вашего "класса домена", или использовать отдельный класс дерева, который содержал ссылки на ваши личные объекты? подумайте о такой простой операции, как получение всех <code>grandchildren</code> <code>person</code>, должен ли этот код быть в классе <code>person</code>, или пользователь класса <code>person</code> должен знать о отдельном классе дерева?</p> </blockquote><p>другой пример - дерево разбора в компиляторе…</p><p>оба этих примера показывают, что концепция дерева является частью данных <strong>домен</strong>, и использование отдельного дерева общего назначения по крайней мере удваивает число создаваемых объектов, а также создает api сложнее программировать заново.</p><p>нам нужен способ многократного использования стандартных операций с деревом, без необходимости повторной реализации их для всех деревьев, и в то же время без необходимости использовать стандартный класс дерева. boost пытался решить проблему такого типа для c++, но я пока не вижу, чтобы какой-либо эффект для .net был адаптирован.</p>

<p>я добавил полное решение и пример с использованием класса ntree выше, а также добавил метод "addchild" ...</p><pre><code> 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; } } </code></pre><p>с помощью</p><pre><code> ntree<keyvaluepair<string, string>> ret = null; tree.traverse(tree, delegatemethod, node["categoryid"].innertext, ref ret); </code></pre>

<p>если вы собираетесь отображать это дерево в графическом интерфейсе, вы можете использовать <a href="https://msdn.microsoft.com/en-us/library/system.windows.forms.treeview(v=vs.100).aspx">treeview</a> и <a href="https://msdn.microsoft.com/en-us/library/system.windows.forms.treenode(v=vs.100).aspx">treenode</a> . (полагаю, технически вы можете создать treenode, не помещая его в графический интерфейс, но он имеет больше накладных расходов, чем простая реализация treenode.)</p>