Estructura de datos de árbol en C #

Estaba buscando una estructura de datos de árbol o gráfico en C #, pero supongo que no hay ninguno. Un examen exhaustivo de estructuras de datos utilizando C # 2.0 explica un poco sobre por qué. ¿Hay una biblioteca conveniente que se usa comúnmente para proporcionar esta funcionalidad? Tal vez a través de un patrón de estrategia para resolver los problemas presentados en el artículo.

Me siento un poco tonto al implementar mi propio árbol, al igual que implementaría mi propia ArrayList.

Solo quiero un árbol genérico que pueda desequilibrarse. Piensa en un árbol de directorios. C5 parece ingenioso, pero las estructuras de sus árboles parecen implementarse como árboles equilibrados de color rojo-negro más adecuados para la búsqueda que representando una jerarquía de nodos.

Mi mejor consejo sería que no existe una estructura de datos de árbol estándar porque hay muchas maneras de implementarlo que sería imposible cubrir todas las bases con una sola solución. Mientras más específica sea una solución, es menos probable que sea aplicable a un problema determinado. Incluso me enojo con LinkedList, ¿y si quiero una lista circular vinculada?

La estructura básica que deberá implementar será una colección de nodos, y aquí hay algunas opciones para comenzar. Supongamos que el nodo de clase es la clase base de toda la solución.

Si solo necesita navegar por el árbol, una clase Node necesita una Lista de elementos secundarios.

Si necesita navegar por el árbol, la clase Node necesita un enlace a su nodo padre.

Cree un método AddChild que se ocupe de todos los detalles de estos dos puntos y de cualquier otra lógica de negocios que deba implementarse (límites para niños, clasificación de los niños, etc.)

Odio admitirlo, pero terminé escribiendo mi propia clase de árbol usando una lista vinculada. En una nota sin relación acabo de descubrir esta cosa redonda que, cuando se adjunta a una cosa que estoy llamando un “eje” permite un transporte más fácil de mercancías.

delegate void TreeVisitor(T nodeData); class NTree { private T data; private LinkedList> children; public NTree(T data) { this.data = data; children = new LinkedList>(); } public void AddChild(T data) { children.AddFirst(new NTree(data)); } public NTree GetChild(int i) { foreach (NTree n in children) if (--i == 0) return n; return null; } public void Traverse(NTree node, TreeVisitor visitor) { visitor(node.data); foreach (NTree kid in node.children) Traverse(kid, visitor); } } 

Implementación recursiva simple … <40 líneas de código ... Solo necesita mantener una referencia a la raíz del árbol fuera de la clase, o envolverlo en otra clase, ¿quizás cambiarle el nombre a TreeNode?

Aquí está el mío, que es muy similar al de Aaron Gage , un poco más convencional, en mi opinión. Para mis propósitos, no me encontré con ningún problema de rendimiento con List . Sería bastante fácil cambiar a LinkedList si es necesario.


 namespace Overby.Collections { public class TreeNode { private readonly T _value; private readonly List> _children = new List>(); public TreeNode(T value) { _value = value; } public TreeNode this[int i] { get { return _children[i]; } } public TreeNode Parent { get; private set; } public T Value { get { return _value; } } public ReadOnlyCollection> Children { get { return _children.AsReadOnly(); } } public TreeNode AddChild(T value) { var node = new TreeNode(value) {Parent = this}; _children.Add(node); return node; } public TreeNode[] AddChildren(params T[] values) { return values.Select(AddChild).ToArray(); } public bool RemoveChild(TreeNode node) { return _children.Remove(node); } public void Traverse(Action action) { action(Value); foreach (var child in _children) child.Traverse(action); } public IEnumerable Flatten() { return new[] {Value}.Concat(_children.SelectMany(x => x.Flatten())); } } } 

Sin embargo, otra estructura de árbol:

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

Uso de muestra:

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

PRIMA
Ver árboles en toda regla con:

  • iterador
  • buscando
  • Java / C #

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

En general, la excelente colección de C5 Generic Collection tiene varias estructuras de datos basadas en árboles diferentes, incluidos conjuntos, bolsos y diccionarios. El código fuente está disponible si desea estudiar sus detalles de implementación. (He utilizado las colecciones C5 en el código de producción con buenos resultados, aunque no he utilizado ninguna estructura de árbol específicamente).

Ver http://quickgraph.codeplex.com/

QuickGraph proporciona estructuras de datos y algoritmos generics dirigidos / no dirigidos para .Net 2.0 y posteriores. QuickGraph viene con algoritmos como profundidad primera búsqueda, primera búsqueda de aliento, búsqueda A *, ruta más corta, ruta k-más corta, flujo máximo, árbol de expansión mínimo, antepasados ​​menos comunes, etc. QuickGraph admite MSAGL, GLEE y Graphviz para renderizar los gráficos, serializar a GraphML, etc …

Si desea escribir uno propio, puede comenzar con este documento de seis partes que detalla el uso efectivo de las estructuras de datos C # 2.0 y cómo analizar su implementación de estructuras de datos en C #. Cada artículo tiene ejemplos y un instalador con ejemplos que puede seguir.

“Un examen exhaustivo de las estructuras de datos con C # 2.0” por Scott Mitchell

Tengo una pequeña extensión a las soluciones.

Usando una statement genérica recursiva y una subclase derivada, puede concentrarse mejor en su objective real.

Tenga en cuenta que es diferente de una implementación no genérica, no necesita convertir ‘nodo’ en ‘NodeWorker’.

Aquí está mi ejemplo:

 public class GenericTree where T : GenericTree // recursive constraint { // no specific data declaration protected List children; public GenericTree() { this.children = new List(); } public virtual void AddChild(T newChild) { this.children.Add(newChild); } public void Traverse(Action visitor) { this.traverse(0, visitor); } protected virtual void traverse(int depth, Action visitor) { visitor(depth, (T)this); foreach (T child in this.children) child.traverse(depth + 1, visitor); } } public class GenericTreeNext : GenericTree // 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); } 

Prueba esta simple muestra.

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

Creo una clase Node que podría ser útil para otras personas. La clase tiene propiedades como:

  • Niños
  • Ancestros
  • Descendientes
  • Hermanos
  • Nivel del nodo
  • Padre
  • Raíz
  • Etc.

También existe la posibilidad de convertir una lista plana de elementos con Id y ParentId en un árbol. Los nodos contienen una referencia tanto a los elementos secundarios como a los elementos principales, por lo que los nodos de iteración son bastante rápidos.

Como no se menciona, me gustaría llamar la atención sobre la base de código .net publicada ahora: específicamente el código para un SortedSet que implementa un Árbol Rojo-Negro:

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

Esta es, sin embargo, una estructura de árbol equilibrada. Así que mi respuesta es más una referencia a lo que creo que es la única estructura de árbol nativa en la biblioteca principal de .net.

He completado el código que @Berezh ha compartido.

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

Aquí hay un árbol

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

Incluso puedes usar inicializadores:

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

La mayoría de los árboles están formados por los datos que estás procesando.

Digamos que tiene una clase de person que incluye detalles de los parents de alguien, ¿preferiría tener la estructura de árbol como parte de su “clase de dominio”, o usar una clase de árbol separada que contuviera enlaces a los objetos de su persona? Piense en una operación simple como obtener todos los grandchildren de una person , ¿debería este código estar en la clase de person , o debería el usuario de la clase de person tener que saber sobre una clase de árbol separada?

Otro ejemplo es un árbol de análisis sintáctico en un comstackdor …

Lo que estos dos ejemplos muestran es que el concepto de árbol forma parte del dominio de los datos y el uso de un árbol de propósito general por separado al menos duplica la cantidad de objetos que se crean y dificulta la progtwigción del API nuevamente.

Lo que queremos es una forma de reutilizar las operaciones de árbol estándar, sin tener que volver a implementarlas para todos los árboles, y al mismo tiempo, no tener que usar una clase de árbol estándar. Boost ha intentado resolver este tipo de problema para C ++, pero todavía veo que se puede adaptar cualquier efecto para .NET.

He agregado una solución completa y un ejemplo usando la clase NTree anterior, también agregué el método “AddChild” …

  public class NTree { public T data; public LinkedList> children; public NTree(T data) { this.data = data; children = new LinkedList>(); } public void AddChild(T data) { var node = new NTree(data) { Parent = this }; children.AddFirst(node); } public NTree Parent { get; private set; } public NTree GetChild(int i) { foreach (NTree n in children) if (--i == 0) return n; return null; } public void Traverse(NTree node, TreeVisitor visitor, string t, ref NTree r) { visitor(node.data, node, t, ref r); foreach (NTree kid in node.children) Traverse(kid, visitor, t, ref r); } } public static void DelegateMethod(KeyValuePair data, NTree> node, string t, ref NTree> r) { string a = string.Empty; if (node.data.Key == t) { r = node; return; } } 

utilizando

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

Si va a mostrar este árbol en la GUI, puede usar TreeView y TreeNode . (Supongo que técnicamente puede crear un TreeNode sin ponerlo en una GUI, pero tiene más sobrecarga que una simple implementación TreeNode de cosecha propia).

Aquí está el mío:

 class Program { static void Main(string[] args) { var tree = new Tree() .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(TreeNode node, int level) { Console.WriteLine("{0}{1}", new string(' ', level * 3), node.Value); level++; node.Children.ForEach(p => PrintNode(p, level)); } } public class Tree { private Stack> m_Stack = new Stack>(); public List> Nodes { get; } = new List>(); public Tree Begin(T val) { if (m_Stack.Count == 0) { var node = new TreeNode(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 Add(T val) { m_Stack.Peek().Add(val); return this; } public Tree End() { m_Stack.Pop(); return this; } } public class TreeNode { public T Value { get; } public TreeNode Parent { get; } public List> Children { get; } public TreeNode(T val, TreeNode parent) { Value = val; Parent = parent; Children = new List>(); } public TreeNode Add(T val) { var node = new TreeNode(val, this); Children.Add(node); return node; } } 

Salida:

 Fastfood Pizza Margherita Marinara Burger Cheese burger Chili burger Rice burger 

Aquí está mi implementación de 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(); } } 

En caso de que necesite una implementación de estructura de datos de árbol rooteada que use menos memoria, puede escribir su clase Node de la siguiente manera (implementación 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 }