Baumdatenstruktur in C #

Question

Ich war auf der Suche nach einem Baum oder Graphdatenstruktur in C #, aber ich denke, es gibt nicht eine vorgesehen ist. ausführliche Betrachtung der Datenstrukturen mit C # 2.0 ein wenig darüber, warum erklärt. Gibt es eine bequeme Bibliothek, die häufig verwendet wird, um diese Funktionalität bereitzustellen? Vielleicht durch eine Strategie Muster, um die Probleme in dem Artikel zu lösen.

Ich fühle mich ein bisschen dumm meinen eigenen Baum Umsetzung, so wie ich meine eigene Arraylist Umsetzung würde.

Ich will nur einen generischen Baum, der unausgeglichen sein kann. Denken Sie an einen Verzeichnisbaum. C5 sieht geschickt, aber die Baumstruktur scheint umgesetzt werden als ausgewogen rot-schwarz Bäume besser geeignet als die Suche eine Hierarchie von Knoten darstellt.

Answer 1

Mein bester Rat wäre, dass es keine Standard-Baumdatenstruktur ist, weil es so viele Möglichkeiten gibt, Sie es implementieren könnten, dass es unmöglich wäre, alle Basen mit einer Lösung abzudecken. Je spezifischer eine Lösung, desto weniger wahrscheinlich ist es für jedes gegebenes Problem. Ich habe sogar mit LinkedList ärgern - was ist, wenn ich eine kreisförmige verkettete Liste will

Die Grundstruktur, die Sie implementieren müssen, werden zu wird eine Sammlung von Knoten sein, und hier sind einige Optionen, die Sie den Start. Nehmen wir an, dass die Klasse Knoten die Basisklasse der gesamten Lösung.

Wenn Sie müssen nur den Baum navigieren nach unten, dann einer Node-Klasse braucht eine Liste der Kinder.

Wenn Sie den Baum navigieren müssen, dann ist die Node-Klasse muss einen Link zu seinem übergeordneten Knoten.

Erstellen Sie eine AddChild Methode, die Pflege aller Minutien dieser beiden Punkte und jede andere Business-Logik nimmt, die umgesetzt werden müssen (Kinder Grenzen, die Kinder sortieren, usw.)

Answer 2

Ich hasse es zuzugeben, aber ich am Ende meiner eigenen Baum Klasse schreibe eine verknüpfte Liste. Auf einem nicht verwandten Notiz entdeckte ich gerade diese runde Sache, die, wenn sie auf eine Sache angebracht ich eine ‚Achse‘ bin fordern einen leichteren Transport von Gütern ermöglicht.

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

Einfache rekursive Implementierung ... <40 Zeilen Code ... Sie müssen nur außerhalb der Klasse einen Verweis auf die Wurzel des Baumes zu halten, oder wickeln Sie es in einer anderen Klasse, benennen Sie vielleicht zu TreeNode ??

Answer 4

Hier ist meins, das sehr ähnlich ist Aaron Gage , nur ein wenig mehr konventionelle, meiner Meinung nach. Für meine Zwecke habe ich nicht in irgendwelche Probleme mit der Leistung List<T> lief. Es wäre leicht genug sein, um eine LinkedList zu wechseln, wenn nötig.

---

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

Noch eine weitere Baumstruktur:

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
}

Verwendungsbeispiel:

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
Siehe vollwertiges Baum mit:

• Iterator
• Suchen
• Java / C #

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

Answer 6

Die im Allgemeinen ausgezeichnet C5 generische Sammlung Bibliothek verschiedene Baum-basierten Datenstrukturen, zB Sets, Taschen und Wörterbücher. Der Quellcode ist verfügbar, wenn Sie ihre Implementierungsdetails studieren wollen. (Ich habe mit guten Ergebnissen in der Produktion Code C5 Sammlungen verwendet, obwohl ich habe keine der Baumstrukturen gezielt eingesetzt.)

Answer 7

Siehe http://quickgraph.codeplex.com/

QuickGraph enthält allgemeine gerichtet / ungerichteten Graphen Datenstrukturen und Algorithmen für .Net 2.0 oder höher. QuickGraph kommt mit Algorithmen wie Tiefen seach, Atem erste Suche, A * -Suche, kürzesten Weg, k-kürzesten Weg, die maximale Durchfluss, minimaler Spannbaum, kleinste gemeinsame Vorfahren, etc ... QuickGraph unterstützt MSAGL, GLEE und Graphviz zu machen die Graphen, Serialisierung GraphML, etc ...

Answer 8

Wenn Sie mögen Ihre eigenen schreiben, können Sie mit diesem sechsteiligen Dokument Detaillierung effektive Nutzung von C # 2.0 Datenstrukturen beginnen und wie über die Analyse Ihre Implementierung von Datenstrukturen in C # zu gehen. Jeder Artikel hat Beispiele und ein Installationsprogramm mit Proben, die Sie mit entlang folgen können.

„eine eingehende Untersuchung von Datenstrukturen mit C # 2.0“ von Scott Mitchell

Answer 9

Ich habe eine kleine Erweiterung der Lösungen.

eine rekursive allgemeine Erklärung und eine Berechnungsunterklasse Verwenden Sie besser auf Ihre eigentlichen Ziel konzentrieren können.

Beachten Sie, es unterscheidet sich von einer nicht generische Implementierung, Sie don `t müssen werfen‚Knoten‘in‚NodeWorker‘.

Hier ist mein Beispiel:

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

Versuchen Sie diese einfache Probe.

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

Ich erstelle ein Knoten Klasse , die für andere Menschen hilfreich sein könnten. Die Klasse hat Eigenschaften wie:

• Kinder
• Vorfahren
• Nachkommen
• Geschwister
• Stufe des Knotens
• Eltern
• root
• Etc.

Es gibt auch die Möglichkeit, eine flache Liste der Elemente mit einer ID und einem ParentId an einen Baum zu konvertieren. Die Knoten enthält einen Verweis auf die beiden Kinder und die Eltern, so dass macht Iterieren recht schnell Knoten.

Answer 12

Weil es nicht erwähnt wird, würde Ich mag Sie die Aufmerksamkeit, die jetzt veröffentlicht .net Code-Basis zeichnen: speziell den Code für eine SortedSet, die ein Rot-Schwarz-Baum implementiert:

https: // GitHub. com / Microsoft / referencesource / Blob / Master / System / compmod / system / Sammlungen / generic / sortedset.cs

Dies ist jedoch eine ausgeglichene Baumstruktur. Also meine Antwort ist ein Hinweis auf das, was ich glaube, die einzige einheimische Baumstruktur in der .net-Core-Bibliothek ist.

Answer 13

Ich habe den Code abgeschlossen, die @Berezh geteilt.

  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

Hier ist ein Baum

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

Sie können sogar initializers verwenden:

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

Answer 15

Hier ist meine eigene:

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

Ausgabe:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger

Answer 16

Die meisten Bäume werden durch die Daten gebildet Sie verarbeiten.

  

Sagen Sie bitte eine person Klasse, die Details von jemandes enthält   parents, würden Sie lieber die Baumstruktur als Teil Ihrer   „Domain-Klasse“, oder eine separate Baum-Klasse verwenden, die Links enthalten   Ihre Person Objekte? Denken Sie über einen einfachen Vorgang wie alle bekommen   die grandchildren eines person, sollte dieser Code in der person   Klasse, oder sollte der Benutzer der person Klasse über eine wissen   separate Baum Klasse?

Ein weiteres Beispiel ist ein Parse-Baum in einem Compiler ...

Was diese beiden Beispiele zeigen, dass das Konzept eines Baumes Teil der Domäne der Daten und mit einem separaten Mehrzweck Baum mindestens verdoppelt sich die Anzahl der Objekte, die auch erstellt werden so macht den API schwieriger wieder zu programmieren.

Was wir wollen, ist eine Möglichkeit, die Standard-Baum-Operationen wieder zu verwenden, ohne dass sie für alle Bäume neu zu implementieren, während zur gleichen Zeit, nicht eine Standard-Baum-Klasse zu verwenden. Boost hat versucht, diese Art von Problem für C ++ zu lösen, aber ich noch einen Effekt zu sehen, für .NET angepasst bekommen.

Answer 17

Ich habe hinzugefügt Komplettlösung und am Beispiel NTree Klasse oben, auch „AddChild“ hinzugefügt Methode ...

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

mit

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

Answer 18

Wenn Sie sich diesen Baum auf der GUI angezeigt werden, können Sie TreeView und TreeNode . (Ich nehme an technisch können Sie einen TreeNode erstellen, ohne dass es auf einem GUI zu setzen, aber es hat mehr Aufwand als eine einfache homegrown TreeNode Implementierung.)

Answer 19

Hier ist meine Implementierung von 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

Falls Sie benötigen eine verwurzelte Baumdatenstruktur-Implementierung, die wenige Speicher verwendet, können Sie Ihre Node-Klasse wie folgt schreiben (C ++ Implementierung):

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
}