Struttura dei dati dell'albero in C#

Question

Stavo cercando una struttura dati ad albero o grafico in C# ma immagino che non ce ne sia una fornita. Un esame approfondito delle strutture dati utilizzando C# 2.0 spiega un po' il perché.Esiste una libreria conveniente comunemente utilizzata per fornire questa funzionalità?Magari attraverso uno schema strategico per risolvere i problemi presentati nell’articolo.

Mi sento un po' sciocco nell'implementare il mio albero, proprio come farei con il mio ArrayList.

Voglio solo un albero generico che possa essere sbilanciato.Pensa a un albero di directory.C5 sembra ingegnoso, ma le loro strutture ad albero sembrano essere implementate come alberi rosso-neri bilanciati più adatti alla ricerca che a rappresentare una gerarchia di nodi.

Answer 1

Il mio miglior consiglio sarebbe che non esiste una struttura dati ad albero standard perché ci sono così tanti modi in cui potresti implementarla che sarebbe impossibile coprire tutte le basi con un'unica soluzione.Più una soluzione è specifica, meno è probabile che sia applicabile a un dato problema.Mi dà fastidio persino LinkedList: cosa succede se voglio un elenco collegato circolare?

La struttura di base che dovrai implementare sarà una raccolta di nodi ed ecco alcune opzioni per iniziare.Supponiamo che la classe Node sia la classe base dell'intera soluzione.

Se devi solo navigare lungo l'albero, una classe Node necessita di un Elenco di figli.

Se devi navigare lungo l'albero, la classe Node necessita di un collegamento al suo nodo genitore.

Costruisci un metodo AddChild che si occupi di tutte le minuzie di questi due punti e di qualsiasi altra logica aziendale che deve essere implementata (limiti figlio, ordinamento dei figli, ecc.)

Answer 2

Odio ammetterlo, ma ho finito per scrivere la mia classe di alberi utilizzando un elenco collegato.In una nota non correlata ho appena scoperto questa cosa rotonda che, quando attaccata a una cosa che chiamo "asse", consente un più facile trasporto delle merci.

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

Semplice implementazione ricorsiva...<40 righe di codice...Devi solo mantenere un riferimento alla radice dell'albero al di fuori della classe o avvolgerla in un'altra classe, forse rinominare per trenode ??

Answer 4

Ecco il mio, che è molto simile a Quello di Aaron Gage, solo un po' più convenzionale, secondo me.Per i miei scopi, non ho riscontrato problemi di prestazioni con List<T>.Sarebbe abbastanza semplice passare a una LinkedList se necessario.

---

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

Ancora un'altra struttura ad albero:

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
}

Utilizzo del campione:

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
Guarda l'albero a tutti gli effetti con:

• iteratore
• ricerca
• Java/C#

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

Answer 6

Il generale eccellente Libreria di raccolte generiche C5 ha diverse strutture dati basate su alberi, inclusi set, borse e dizionari.Il codice sorgente è disponibile se desideri studiare i dettagli di implementazione.(Ho utilizzato le raccolte C5 nel codice di produzione con buoni risultati, anche se non ho utilizzato alcuna struttura ad albero in modo specifico.)

Answer 7

Vedere http://quickgraph.codeplex.com/

QuickGraph fornisce strutture dati e algoritmi di grafici generici diretti/non diretti per .Net 2.0 e versioni successive.QuickGraph viene fornito con algoritmi come la ricerca prima in profondità, la ricerca prima nel respiro, la ricerca A*, il percorso più breve, il percorso più breve k, il flusso massimo, l'albero di copertura minimo, gli antenati meno comuni, ecc...QuickGraph supporta MSAGL, GLEE e Graphviz per eseguire il rendering dei grafici, la serializzazione su GraphML, ecc...

Answer 8

Se desideri scriverne uno tuo, puoi iniziare con questo documento in sei parti che descrive in dettaglio l'utilizzo efficace delle strutture dati C# 2.0 e come analizzare l'implementazione delle strutture dati in C#.Ogni articolo contiene esempi e un programma di installazione con esempi che puoi seguire.

"Un esame approfondito delle strutture dati utilizzando C# 2.0" di Scott Mitchell

Answer 9

Ho una piccola estensione alle soluzioni.

Usando una dichiarazione generica ricorsiva e una sottoclasse derivata puoi concentrarti meglio sul tuo obiettivo reale.

Nota, è diverso da un'implementazione non generica, non è necessario eseguire il cast di "node" in "NodeWorker".

Ecco il mio esempio:

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

Prova questo semplice esempio.

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

Creo un Classe del nodo potrebbe essere utile per altre persone.La classe ha proprietà come:

• Bambini
• Antenati
• Discendenti
• Fratelli
• Livello del nodo
• Genitore
• Radice
• Eccetera.

C'è anche la possibilità di convertire un elenco semplice di elementi con un Id e un ParentId in un albero.I nodi contengono un riferimento sia ai figli che al genitore, in modo che l'iterazione dei nodi sia abbastanza veloce.

Answer 12

Poiché non è menzionato, vorrei che attirassi l'attenzione sul codice base .net ora rilasciato:in particolare il codice per a SortedSet che implementa un Red-Black-Tree:

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

Si tratta, tuttavia, di una struttura ad albero equilibrata.Quindi la mia risposta è più un riferimento a quella che credo sia l'unica struttura ad albero nativa nella libreria principale .net.

Answer 13

Ho completato il codice condiviso da @Berezh.

  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

Ecco un albero

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

Puoi anche usare gli inizializzatori:

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

Answer 15

Ecco il mio:

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

Produzione:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger

Answer 16

La maggior parte degli alberi sono formati dai dati che stai elaborando.

Diciamo che hai un person classe che include i dettagli di qualcuno parents, preferiresti avere la struttura dell'albero come parte della tua "classe di dominio" o utilizzare una classe di albero separata che conteneva collegamenti agli oggetti della persona?Pensa a una semplice operazione come ottenere tutto il grandchildren di un person, questo codice dovrebbe essere nel file personclasse, o dovrebbe l'utente di person La classe deve conoscere una classe di albero separata?

Un altro esempio è un albero di analisi in un compilatore...

Ciò che entrambi questi esempi mostrano è che il concetto di albero fa parte del dominio dei dati e l'utilizzo di un albero per scopi generali separato raddoppia almeno il numero di oggetti creati e rende l'API più difficile da programmare nuovamente.

Ciò che vogliamo è un modo per riutilizzare le operazioni standard dell'albero, senza doverle reimplementare per tutti gli alberi e, allo stesso tempo, senza dover utilizzare una classe dell'albero standard.Boost ha provato a risolvere questo tipo di problema per C++, ma non ho ancora visto alcun effetto per l'adattamento di .NET.

Answer 17

Ho aggiunto la soluzione completa e l'esempio utilizzando la classe NTree sopra, ho anche aggiunto il metodo "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;
        }
    }

utilizzando

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

Answer 18

Se intendi visualizzare questo albero sulla GUI, puoi utilizzare Visualizzazione ad albero E TreeNode.(Suppongo che tecnicamente sia possibile creare un TreeNode senza inserirlo in una GUI, ma ha un sovraccarico maggiore rispetto a una semplice implementazione TreeNode nostrana.)

Answer 19

Ecco la mia implementazione di 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

Nel caso in cui sia necessaria un'implementazione della struttura dati dell'albero con radice che utilizzi meno memoria, puoi scrivere la classe Node come segue (implementazione 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
}