Estrutura de dados em árvore em C #

Eu estava procurando uma estrutura de dados em árvore ou gráfico em C #, mas acho que não há uma fornecida. Um exame abrangente das estruturas de dados usando o C # 2.0 explica um pouco sobre o porquê. Existe uma biblioteca conveniente que é comumente usada para fornecer essa funcionalidade? Talvez através de um padrão de estratégia para resolver os problemas apresentados no artigo.

Sinto-me um pouco tolo ao implementar minha própria árvore, assim como implementaria minha própria ArrayList.

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

Meu melhor conselho seria que não exista 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 uma solução, menor a probabilidade de ela ser aplicável a qualquer problema. Eu até me irrito 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 navegar apenas pela árvore, uma classe Node precisará de uma Lista de filhos.

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

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

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 agrupá-la em outra classe, talvez renomear para TreeNode ??

Aqui está o meu, que é muito semelhante ao de Aaron Gage , um pouco mais convencional, na minha opinião. Para meus propósitos, não tive problemas com desempenho 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()));
        }
    }
}

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 da 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 a árvore de pleno direito com:

• iterador
• procurando
• Java / C #

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

A geralmente excelente biblioteca de coleções genéricas C5 possui várias estruturas de dados baseadas em árvore, incluindo conjuntos, malas e dicionários. O código-fonte está disponível se você deseja 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.)

Consulte http://quickgraph.codeplex.com/

O QuickGraph fornece estruturas de dados e algoritmos genéricos de gráficos direcionados / não direcionados para .Net 2.0 e superior. O QuickGraph vem com algoritmos como profundidade na primeira busca, respiração na primeira busca, busca A *, caminho mais curto, caminho mais curto k, fluxo máximo, árvore de abrangência mínima, ancestrais menos comuns, etc. renderize os gráficos, serialize para GraphML, etc ...

Se você quiser escrever o seu próprio, pode começar com este documento de seis partes detalhando o uso efetivo das estruturas de dados do C # 2.0 e como analisar a implementação das estruturas de dados no C #. Cada artigo tem exemplos e um instalador com amostras que você pode acompanhar.

“Um exame abrangente das estruturas de dados usando o C # 2.0” por Scott Mitchell

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 destino real.

Observe que é diferente de uma implementação não genérica; você não precisa converter 'node' no 'NodeWorker'.

Aqui está o 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);  
}  

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

Resultado:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger

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
}

Crio uma classe Node que pode ser útil para outras pessoas. A classe possui propriedades como:

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

Também há a possibilidade de converter uma lista simples de itens com um ID e um ParentId em uma árvore. Os nós mantêm uma referência para os filhos e o pai, o que torna os nós iterativos bastante rápidos.

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 de um SortedSetque implementa uma árvore 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 .net.

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

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

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

Digamos que você tenha uma personclasse que inclua detalhes dos de alguém parents, você prefere ter a estrutura em árvore como parte da sua "classe de domínio" ou use uma classe em árvore separada que contenha links para os objetos da sua pessoa? Pense em uma operação simples, como obter todo grandchildrenum de person, esse código deve estar na person classe ou o usuário da personclasse precisa saber sobre uma classe de árvore separada?

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

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

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

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

Aqui está a 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();
    }
}

Se você deseja exibir essa árvore na GUI, pode usar o TreeView e o TreeNode . (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 doméstica do TreeNode.)

Caso você precise de uma implementação de estrutura de dados em árvore com raiz que use menos memória, você pode gravar 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
}