Estructura de datos de árbol en C#

Question

Estaba buscando una estructura de datos de árbol o gráfico en C#, pero supongo que no se proporciona ninguna. Un examen exhaustivo de las estructuras de datos utilizando C# 2.0 explica un poco por qué.¿Existe una biblioteca conveniente que se use comúnmente para proporcionar esta funcionalidad?Quizás 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, tal como lo haría con mi propio ArrayList.

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

Answer 1

Mi mejor consejo sería que no existe una estructura de datos de árbol estándar porque hay tantas formas de implementarla que sería imposible cubrir todas las bases con una sola solución.Cuanto más específica sea una solución, menos probable será que sea aplicable a un problema determinado.Incluso me molesta LinkedList: ¿qué pasa si quiero una lista circular enlazada?

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

Si solo necesita navegar hacia abajo en el árbol, entonces una clase Nodo necesita una Lista de elementos secundarios.

Si necesita navegar hacia arriba en el árbol, entonces la clase Nodo necesita un enlace a su nodo principal.

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

Answer 2

Odio admitirlo, pero terminé escribiendo mi propia clase de árbol usando una lista vinculada.En una nota no relacionada, acabo de descubrir esta cosa redonda que, cuando se une a algo que llamo "eje", permite un transporte más fácil de mercancías.

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

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, ¿tal vez cambiar el nombre de Treenode?

Answer 4

Aquí está el mío, que es muy parecido a Aaron Gage, sólo que un poco más convencional, en mi opinión.Para mis propósitos, no he tenido ningún problema de rendimiento con List<T>.Sería bastante fácil cambiar a LinkedList si fuera necesario.

---

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

Otra estructura de árbol más:

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
}

Uso de muestra:

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

PRIMA
Ver árbol completo con:

• iterador
• buscando
• Java/C#

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

Answer 6

El excelente en general Biblioteca de colección genérica C5 Tiene varias estructuras de datos diferentes basadas en árboles, incluidos conjuntos, bolsas y diccionarios.El código fuente está disponible si desea estudiar los detalles de su implementación.(He usado colecciones C5 en código de producción con buenos resultados, aunque no he usado ninguna de las estructuras de árbol específicamente).

Answer 7

Ver http://quickgraph.codeplex.com/

QuickGraph proporciona algoritmos y estructuras de datos de gráficos dirigidos/no dirigidos genéricos para .Net 2.0 y versiones posteriores.QuickGraph viene con algoritmos como búsqueda primero en profundidad, búsqueda primero en respiración, búsqueda A*, camino más corto, camino más corto k, flujo máximo, árbol de expansión mínimo, ancestros menos comunes, etc.QuickGraph admite MSAGL, GLEE y Graphviz para representar gráficos, serialización a GraphML, etc.

Answer 8

Si desea escribir el suyo propio, puede comenzar con este documento de seis partes que detalla el uso efectivo de las estructuras de datos de 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 utilizando C# 2.0" por Scott Mitchell

Answer 9

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

Al utilizar una declaración genérica recursiva y una subclase derivada, podrá concentrarse mejor en su objetivo real.

Tenga en cuenta que es diferente de una implementación no genérica: no es necesario convertir 'nodo' en 'NodeWorker'.

Aquí está mi ejemplo:

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

Pruebe este sencillo ejemplo.

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

yo creo un clase de nodo eso 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 un Id. y un ParentId en un árbol.Los nodos tienen una referencia tanto a los hijos como a los padres, por lo que la iteración de los nodos es bastante rápida.

Answer 12

Como no se menciona, me gustaría que llamaran su atención sobre el código base .net ahora publicado: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

Sin embargo, se trata de una estructura de árbol equilibrada.Entonces mi respuesta es más una referencia a lo que creo que es la única estructura de árbol nativa en la biblioteca central .net.

Answer 13

Completé el código que @Berezh compartió.

  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

Aquí hay un árbol

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

Incluso puedes usar inicializadores:

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

Answer 15

Aquí está el mío:

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

Producción:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger

Answer 16

La mayoría de los árboles se forman a partir de los datos que se procesan.

Di que tienes un person clase que incluye detalles de alguien parents, ¿Prefieres tener la estructura del árbol como parte de tu "clase de dominio", o usar una clase de árbol separada que contenía enlaces a los objetos de tu persona?Piense en una operación simple como obtener todo el grandchildren de un person, ¿debería estar este código en el personclase, o debería el usuario de la person ¿La clase tiene que saber sobre una clase de árbol separada?

Otro ejemplo es un árbol de análisis en un compilador...

Lo que ambos ejemplos muestran es que el concepto de árbol es parte del dominio de los datos y el uso de un árbol de propósito general separado al menos duplica la cantidad de objetos que se crean, además de hacer que la API sea más difícil de programar 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 no he visto ningún efecto para la adaptación de .NET.

Answer 17

Agregué una solución completa y un ejemplo usando la clase NTree anterior, también agregué el método "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;
        }
    }

usando

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

Answer 18

Si va a mostrar este árbol en la GUI, puede usar Vista de árbol y Nodo de árbol.(Supongo que técnicamente puedes crear un TreeNode sin ponerlo en una GUI, pero tiene más gastos generales que una simple implementación de TreeNode local).

Answer 19

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

Answer 20

En caso de que necesite una implementación de estructura de datos de árbol enraizada que utilice menos memoria, puede escribir su clase Nodo 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
}