it-swarm-es.tech

Estructura de datos del árbol en C #

Estaba buscando una estructura de datos de árbol o gráfica en C # pero supongo que no se proporciona una. Un examen extenso de estructuras de datos usando C # 2.0 explica un poco sobre por qué. ¿Existe una biblioteca conveniente que se use 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 implementando mi propio árbol, tal como lo haría implementando mi propia ArrayList.

Solo quiero un árbol genérico que pueda estar desequilibrado. Piense en un árbol de directorios. C5 parece ingenioso, pero sus estructuras de árbol parecen implementarse como árboles equilibrados rojo-negro más adecuados para buscar que para representar una jerarquía de nodos.

228
stimms

Mi mejor consejo sería que no hay 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 es que sea aplicable a un problema dado. Incluso me molesta con LinkedList: ¿qué sucede si deseo una lista enlazada circular?

La estructura básica que necesitará 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 hacia abajo en el árbol, una clase de Nodo necesita una Lista de elementos secundarios.

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

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

140
David Boike

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 está conectada a una cosa que llamo un 'eje', permite un transporte más fácil de mercancías.

192
stimms
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 envolverla en otra clase, tal vez cambiar el nombre a TreeNode?

112
Aaron Gage

Aquí está el mío, que es muy similar a Aaron Gage's , un poco más convencional, en mi opinión. Para mis propósitos, no he encontrado ningún problema de rendimiento con List<T>. Sería bastante fácil cambiar a una lista enlazada 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()));
        }
    }
}
49
Ronnie Overby

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

BONUS
Ver árbol en toda regla con:

  • iterador
  • buscando
  • Java/C #

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

38
Grzegorz Dev

La excelente C5 Biblioteca de colecciones genéricas tiene varias estructuras de datos basadas en árboles diferentes, incluidos conjuntos, bolsas y diccionarios. El código fuente está disponible si desea estudiar sus detalles de 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).

21
McKenzieG1

Ver http://quickgraph.codeplex.com/

QuickGraph proporciona estructuras de datos y algoritmos de gráficos genéricos dirigidos/no dirigidos para .Net 2.0 y superiores. QuickGraph viene con algoritmos como búsqueda de profundidad en primer lugar, búsqueda por aliento, búsqueda A *, ruta más corta, ruta k más corta, flujo máximo, árbol de expansión mínimo, ancestros menos comunes, etc ... QuickGraph es compatible con MSAGL, GLEE y Graphviz para Renderiza los gráficos, serialización a GraphML, etc ...

10
nietras

Si desea escribir su propio documento, 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 junto con.

“Un examen extenso de estructuras de datos utilizando C # 2.0” por Scott Mitchell

7
user7116

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

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

Note que es diferente de una implementación no genérica, no necesita 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);  
}  
6
Erik Nagel

Prueba esta simple muestra.

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
}
4
Berezh

Creo un clase de nodo que podría ser útil para otras personas. La clase tiene propiedades como:

  • Niños
  • Los antepasados
  • Descendientes
  • Los hermanos
  • Nivel del nodo
  • Padre
  • Root
  • Etc.

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

2
Alex Siepman

Como no se menciona, me gustaría que llamara la atención sobre la base de código .net que ahora se lanzó: específicamente el código para una SortedSet que implementa un árbol rojo-negro:

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

Esto 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 central .net.

2
Meirion Hughes

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"
        }
    };
2
Visar

Aquí está mi propia

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

Salida:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger
2
moien

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

  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;
        }
    }
2
Ashkan Sirous

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

Supongamos que tiene una clase person que incluye detalles de la parents de alguien, ¿preferiría tener la estructura de árbol como parte de su "clase de dominio", o utilizar una clase de árbol separada que contenga enlaces a sus objetos personales? Piense en una operación simple como obtener toda la grandchildren de una person, ¿debería este código estar en la clase person, o el usuario de la clase person debe saber acerca de una clase de árbol separada?

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

Lo que estos dos ejemplos muestran es que el concepto de un árbol es parte del dominio de los datos y usar un árbol de propósito general separado al menos duplica la cantidad de objetos que se crean, así como la API. Más difícil de programar de nuevo.

Lo que queremos es una forma de reutilizar las operaciones de árbol estándar, sin tener que volver a implementarlas para todos los árboles, mientras que, al mismo tiempo, no tener que usar una clase de árbol estándar. Boost ha intentado resolver este tipo de problema para C++, pero aún no he visto ningún efecto para .NET adaptarme.

1
Ian Ringrose

He agregado una solución completa y un ejemplo utilizando 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;
        }
    }

utilizando

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

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 de TreeNode de cosecha propia).

0
Denise Skidmore