Estrutura de dados da tree em c #

Eu estava procurando por uma estrutura de dados em tree ou gráfico em C #, mas eu acho que não é fornecido um. Um exame extensivo de estruturas de dados usando C # 2.0 explica um pouco sobre o motivo. 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.

Eu me sinto um pouco bobo implementando minha própria tree, assim como eu implementaria minha própria ArrayList.

Eu só quero uma tree genérica que pode ser desequilibrada. Pense em uma tree de diretórios. O C5 parece bacana, mas suas estruturas de tree parecem ser implementadas como trees vermelhas e pretas balanceadas, mais adequadas para a pesquisa do que para representar uma hierarquia de nós.

Meu melhor conselho seria que não houvesse uma estrutura padrão de dados de tree, porque há tantas maneiras de implementá-la que seria impossível cobrir todas as bases com uma única solução. Quanto mais específica for uma solução, menos provável será aplicável a qualquer problema. Eu até fico irritado com LinkedList – e se eu quiser uma linked list circular?

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 o nó da class seja a class base de toda a solução.

Se você precisa apenas navegar pela tree, então uma class Node precisa de uma lista de filhos.

Se você precisar navegar pela tree, a class 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 de negócios que deva ser implementada (limites filhos, sorting dos filhos, etc.)

Eu odeio admitir isso, mas acabei escrevendo minha própria class de tree usando uma linked list. Em uma nota não relacionada, acabei de descobrir essa coisa redonda que, quando ligada a uma coisa que estou chamando de “eixo”, facilita o transporte de mercadorias.

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

Implementação recursiva simples … <40 linhas de código ... Você só precisa manter uma referência para a raiz da árvore fora da classe, ou envolvê-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 os meus propósitos, não encontrei nenhum problema de desempenho com List . Seria fácil mudar para uma LinkedList, se necessário.


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

Ainda outra estrutura de tree:

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

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

BÔNUS
Veja a tree completa com:

  • iterador
  • procurando
  • Java / C #

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

A geralmente genérica C5 Generic Collection Library possui várias estruturas de dados baseadas em tree, incluindo conjuntos, bolsas e dictionarys. Código-fonte está disponível se você quiser estudar seus detalhes de implementação. (Eu usei collections C5 em código de produção com bons resultados, embora eu não tenha usado nenhuma das estruturas de tree especificamente.)

Veja http://quickgraph.codeplex.com/

O QuickGraph fornece dados e algoritmos genéricos de dados direcionados / não direcionados para .Net 2.0 e superiores. O QuickGraph é fornecido com algoritmos como profundidade primeiro busca, busca primeiro respiração, pesquisa A *, caminho mais curto, caminho mais curto k, stream máximo, tree mínima, menos ancestrais comuns, etc … QuickGraph suporta MSAGL, GLEE e Graphviz para renderize os charts, serialização para GraphML, etc …

Se você gostaria de escrever o seu próprio, você pode começar com este documento de seis partes detalhando o uso efetivo 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 amostras que você pode acompanhar.

“Um extenso exame de estruturas de dados usando 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 subclass derivada, você pode se concentrar melhor no seu alvo real.

Observe, é diferente de uma implementação não genérica, você não precisa converter ‘node’ em ‘NodeWorker’.

Aqui está meu exemplo:

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

Tente esta amostra simples.

 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 } 

Eu crio uma class Node que pode ser útil para outras pessoas. A class tem propriedades como:

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

Há também a possibilidade de converter uma lista simples de itens com um Id e um ParentId em uma tree. Os nós contêm uma referência aos filhos e ao pai, o que torna os nós de iteração bastante rápidos.

Como não é mencionado, gostaria que você chamasse a atenção para a base de código do .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 tree equilibrada. Portanto, minha resposta é mais uma referência ao que acredito ser a única estrutura de tree nativa na biblioteca principal do .net.

Eu completei o código que @Berezh compartilhou.

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

Aqui está uma tree

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

Você pode até usar inicializadores:

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

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

Digamos que você tenha uma class de person que inclua detalhes dos parents de alguém, você preferiria ter a estrutura de tree como parte de sua “class de domínio” ou usar uma class de tree separada que contivesse links para objects de sua pessoa? Pense em uma operação simples, como obter todos os grandchildren de uma person , se esse código estiver na class de person , ou o usuário da turma precisa saber sobre uma class de tree separada?

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

O que ambos os exemplos mostram é que o conceito de tree faz parte do domínio dos dados e usar uma tree de propósito geral separada dobra pelo menos o número de objects que são criados, além de tornar a API mais difícil de programar novamente.

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

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

usando

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

Se você estiver indo para exibir esta tree na GUI, você pode usar TreeView e TreeNode . (Eu suponho tecnicamente você pode criar um TreeNode sem colocá-lo em uma GUI, mas tem mais sobrecarga do que uma implementação TreeNode simples caseira.)

Aqui está o meu próprio:

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

Saída:

 Fastfood Pizza Margherita Marinara Burger Cheese burger Chili burger Rice burger 

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

Caso você precise de uma implementação de estrutura de dados de tree com raiz que use menos memory, poderá escrever sua class Node da seguinte maneira (implementação 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 }