it-swarm-pt.tech

Estrutura de dados da árvore em c #

Eu estava procurando por uma estrutura de dados em árvore ou gráfico em C #, mas eu acho que não é fornecido um. m exame extensivo de estruturas de dados usando C # 2. 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 árvore, assim como eu 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 vermelhas e pretas balanceadas, mais adequadas para a pesquisa do que para representar uma hierarquia de nós.

228
stimms

Meu melhor conselho seria que não houvesse estrutura de dados de árvore padrão, pois 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 um determinado problema. Eu até fico irritado com LinkedList - e se eu quiser uma lista vinculada 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 classe seja a classe base de toda a solução.

Se você precisa apenas navegar pela árvore, então uma classe Node precisa de uma lista de filhos.

Se você precisar navegar pela á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 de negócios que deva ser implementada (limites filhos, classificação dos filhos, etc.)

141
David Boike

Eu odeio admitir isso, mas acabei escrevendo minha própria classe de árvore usando uma lista vinculada. 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.

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

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 ??

112
Aaron Gage

Aqui está o meu, que é muito semelhante ao Aaron Gage , apenas um pouco mais convencional, na minha opinião. Para os meus propósitos, não encontrei nenhum problema de desempenho com List<T>. Seria bastante fácil mudar para uma 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()));
        }
    }
}
49
Ronnie Overby

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

BONUS
Veja a árvore completa com:

  • iterador
  • procurando
  • Java/C #

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

40
Grzegorz Dev

O geralmente excelente C5 Generic Collection Library tem várias estruturas de dados baseadas em árvore diferentes, incluindo conjuntos, malas e dicionários. Código-fonte está disponível se você quiser estudar seus detalhes de implementação. (Eu usei coleções C5 em código de produção com bons resultados, embora eu não tenha usado nenhuma das estruturas de árvore especificamente.)

22
McKenzieG1

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, busca A *, caminho mais curto, caminho mais curto k, fluxo máximo, árvore mínima, menos ancestrais comuns, etc ... QuickGraph suporta MSAGL, GLEE e Graphviz para renderizar os gráficos, serialização para GraphML, etc ...

10
nietras

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

7
user7116

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, é diferente de uma implementação não genérica, você não precisa converter 'node' em '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);  
}  
6
Erik Nagel

Tente esta amostra 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
}
4
Berezh

Eu crio um classe Node que poderia ser útil para outras pessoas. A classe tem propriedades como:

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

Há também 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 ao pai, o que torna os nós de iteração bastante rápidos.

2
Alex Siepman

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 árvore equilibrada. Portanto, minha resposta é mais uma referência ao que acredito ser a única estrutura de árvore nativa na biblioteca do núcleo .net.

2
Meirion Hughes

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

Aqui está o meu próprio:

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
2
moien

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

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

Digamos que você tenha uma classe person que inclua detalhes de parents de alguém. Você preferiria ter a estrutura de árvore como parte de sua "classe de domínio" ou usar uma classe de árvore separada que contivesse links para seus objetos de pessoa? Pense em uma operação simples como obter todo o grandchildren de um person, este código deve estar na classe person, ou o usuário da classe person 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 uma árvore é parte do domínio dos dados e usar uma árvore de propósito geral separada pelo menos dobra o número de objetos que são criados, assim como API mais difícil de programar novamente.

O que queremos é uma maneira de reutilizar as operações de árvore padrão, sem ter que reimplementá-las para todas as árvores, enquanto, ao mesmo tempo, não precisar usar uma classe de árvore 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.

1
Ian Ringrose

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

Se você estiver indo para exibir esta árvore 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.)

0
Denise Skidmore