Estrutura de dados em árvore em C#

Question

Eu estava procurando uma estrutura de dados em árvore ou gráfico em C#, mas acho que não há nenhuma fornecida. Um exame extensivo de estruturas de dados usando C# 2.0 explica um pouco sobre o porquê.Existe uma biblioteca conveniente comumente usada para fornecer essa funcionalidade?Talvez através de um padrão de estratégia para solucionar as questões apresentadas no artigo.

Sinto-me um pouco bobo ao implementar minha própria árvore, assim como faria ao implementar meu próprio ArrayList.

Eu só quero uma árvore genérica que possa ser desequilibrada.Pense em uma árvore de diretórios.C5 parece bacana, mas suas estruturas em árvore parecem ser implementadas como árvores vermelho-pretas balanceadas, mais adequadas para pesquisa do que representar uma hierarquia de nós.

Answer 1

Meu melhor conselho seria que não existe uma estrutura de dados em árvore padrão porque há tantas maneiras de implementá-la que seria impossível cobrir todas as bases com uma solução.Quanto mais específica for uma solução, menor será a probabilidade de ela ser aplicável a qualquer problema.Até fico irritado com o LinkedList - e se eu quiser uma lista circular vinculada?

A estrutura básica que você precisará implementar será uma coleção de nós, e aqui estão algumas opções para você começar.Vamos supor que a classe Node seja a classe base de toda a solução.

Se você precisar apenas navegar pela árvore, uma classe Node precisará de uma lista de filhos.

Se você precisar navegar pela árvore, a classe Node precisará de um link para seu nó pai.

Construa um método AddChild que cuide de todas as minúcias desses dois pontos e de qualquer outra lógica de negócios que deva ser implementada (limites filhos, classificação dos filhos, etc.)

Answer 2

Odeio admitir, mas acabei escrevendo minha própria classe de árvore usando uma lista vinculada.Numa nota não relacionada, acabei de descobrir esta coisa redonda que, quando ligada a uma coisa que chamo de 'eixo', permite um transporte mais fácil de mercadorias.

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

Implementação recursiva simples...<40 linhas de código...Você só precisa manter uma referência à raiz da árvore fora da classe ou envolvê -la em outra classe, talvez renomeie para Treenode ??

Answer 4

Aqui está o meu, que é muito parecido com Aaron Gage, só um pouco mais convencional, na minha opinião.Para meus propósitos, não encontrei nenhum problema de desempenho com List<T>.Seria fácil mudar para um LinkedList, se necessário.

---

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

Ainda outra estrutura de árvore:

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 amostra:

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

BÔNUS
Veja uma árvore completa com:

• iterador
• procurando
• Java/C#

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

Answer 6

O geralmente excelente Biblioteca de coleções genéricas C5 possui diversas estruturas de dados baseadas em árvore, incluindo conjuntos, pacotes e dicionários.O código-fonte está disponível se você quiser estudar os detalhes de implementação.(Usei coleções C5 no código de produção com bons resultados, embora não tenha usado nenhuma das estruturas em árvore especificamente.)

Answer 7

Ver http://quickgraph.codeplex.com/

QuickGraph fornece estruturas de dados e algoritmos gráficos genéricos direcionados/não direcionados para .Net 2.0 e superior.QuickGraph vem com algoritmos como busca em profundidade, busca em primeira respiração, busca A*, caminho mais curto, caminho mais curto k, fluxo máximo, árvore geradora mínima, ancestrais menos comuns, etc.QuickGraph suporta MSAGL, GLEE e Graphviz para renderizar os gráficos, serialização para GraphML, etc...

Answer 8

Se quiser escrever o seu próprio, você pode começar com este documento de seis partes detalhando o uso eficaz de estruturas de dados C# 2.0 e como proceder para analisar sua implementação de estruturas de dados em C#.Cada artigo tem exemplos e um instalador com exemplos que você pode acompanhar.

“Um exame extensivo de estruturas de dados usando C# 2.0” por Scott Mitchell

Answer 9

Eu tenho uma pequena extensão para as soluções.

Usando uma declaração genérica recursiva e uma subclasse derivada, você pode se concentrar melhor no seu alvo real.

Observe que é diferente de uma implementação não genérica, você não precisa lançar 'node' em 'NodeWorker'.

Aqui está meu exemplo:

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

Experimente este exemplo simples.

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

Eu crio um Classe de nó isso pode ser útil para outras pessoas.A classe possui propriedades como:

• Crianças
• Ancestrais
• Descendentes
• Irmãos
• Nível do nó
• Pai
• Raiz
• Etc.

Também existe a possibilidade de converter uma lista simples de itens com um Id e um ParentId em uma árvore.Os nós contêm uma referência aos filhos e aos pais, o que torna a iteração dos nós bastante rápida.

Answer 12

Como não foi mencionado, gostaria que você chamasse a atenção para a base de código .net agora lançada:especificamente o código para um SortedSet que implementa uma Red-Black-Tree:

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

Esta é, no entanto, uma estrutura de árvore equilibrada.Portanto, minha resposta é mais uma referência ao que acredito ser a única estrutura de árvore nativa na biblioteca principal do .net.

Answer 13

Concluí o código que @Berezh compartilhou.

  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

Aqui está uma árvore

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

Você pode até usar inicializadores:

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

Answer 15

Aqui está o meu:

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

Saída:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger

Answer 16

A maioria das árvores é formada pelos dados que você está processando.

Digamos que você tenha um person classe que inclui detalhes de alguém parents, você prefere ter a estrutura da árvore como parte da sua "classe de domínio" ou usar uma classe de árvore separada que continha links para os objetos de sua pessoa?Pense em uma operação simples, como obter todo o grandchildren de um person, caso este código esteja no personclasse, ou o usuário da person A classe precisa saber sobre uma classe de árvore separada?

Outro exemplo é uma árvore de análise em um compilador…

O que ambos os exemplos mostram é que o conceito de árvore faz parte do domínio dos dados e usar uma árvore de uso geral separada pelo menos dobra o número de objetos criados, além de dificultar a programação da API novamente.

O que queremos é uma maneira de reutilizar as operações de árvore padrão, sem ter que reimplementá-las para todas as árvores, e ao mesmo tempo, sem ter que usar uma classe de árvore padrão.Boost tentou resolver esse tipo de problema para C++, mas ainda não vi nenhum efeito para o .NET ser adaptado.

Answer 17

Eu adicionei solução completa e exemplo usando a classe NTree acima, também adicionei o 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

Se você for exibir esta árvore na GUI, você pode usar TreeView e ÁrvoreNode.(Suponho que tecnicamente você pode criar um TreeNode sem colocá-lo em uma GUI, mas ele tem mais sobrecarga do que uma simples implementação caseira de TreeNode.)

Answer 19

Aqui está minha implementação do 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

Caso você precise de uma implementação de estrutura de dados em árvore enraizada que use menos memória, você pode escrever sua classe Node da seguinte maneira (implementação em 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
}