c# - resolvidos - grau de uma arvore




Estrutura de dados da árvore em c# (14)

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

Eu estava procurando por uma estrutura de dados em árvore ou gráfico em C #, mas eu acho que não é fornecido um. Um extenso exame 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 á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.


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

Digamos que você tenha uma classe de person que inclua detalhes dos 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 os objetos de sua pessoa? Pense em uma operação simples como obter todos os grandchildren de uma person , se esse código estiver na classe de person , ou o usuário da turma 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 propósito geral separada dobra pelo menos o número de objetos 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 á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.


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

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

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

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

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

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

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.


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

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


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


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


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







data-structures