Ich habe nach einer Baum- oder Diagrammdatenstruktur in C # gesucht, aber ich denke, es ist keine vorhanden. Eine ausführliche Untersuchung von Datenstrukturen mit C # 2.0 erklärt ein wenig, warum. Gibt es eine praktische Bibliothek, die üblicherweise zur Bereitstellung dieser Funktionalität verwendet wird? Vielleicht durch ein Strategiemuster, um die im Artikel vorgestellten Probleme zu lösen.
Ich finde es ein bisschen albern, meinen eigenen Baum zu implementieren, genauso wie ich meine eigene ArrayList implementieren würde.
Ich möchte nur einen generischen Baum, der unausgeglichen sein kann. Stellen Sie sich einen Verzeichnisbaum vor. C5 sieht gut aus, aber ihre Baumstrukturen scheinen als ausgeglichene rot-schwarze Bäume implementiert zu sein, die besser für die Suche geeignet sind als die Darstellung einer Hierarchie von Knoten.
quelle
Antworten:
Mein bester Rat wäre, dass es keine Standardstruktur für Baumdaten gibt, da es so viele Möglichkeiten gibt, diese zu implementieren, dass es unmöglich wäre, alle Basen mit einer Lösung abzudecken. Je spezifischer eine Lösung ist, desto weniger wahrscheinlich ist sie auf ein bestimmtes Problem anwendbar. Ich ärgere mich sogar über LinkedList - was ist, wenn ich eine zirkuläre verknüpfte Liste möchte?
Die Grundstruktur, die Sie implementieren müssen, besteht aus einer Sammlung von Knoten. Hier finden Sie einige Optionen, mit denen Sie beginnen können. Nehmen wir an, dass der Klassenknoten die Basisklasse der gesamten Lösung ist.
Wenn Sie nur im Baum nach unten navigieren müssen, benötigt eine Knotenklasse eine Liste der untergeordneten Elemente.
Wenn Sie im Baum nach oben navigieren müssen, benötigt die Node-Klasse einen Link zu ihrem übergeordneten Knoten.
Erstellen Sie eine AddChild-Methode, die alle Details dieser beiden Punkte und alle anderen Geschäftslogiken berücksichtigt, die implementiert werden müssen (untergeordnete Grenzwerte, Sortieren der untergeordneten Elemente usw.).
quelle
Einfache rekursive Implementierung ... <40 Codezeilen ... Sie müssen nur einen Verweis auf die Wurzel des Baums außerhalb der Klasse behalten oder ihn in eine andere Klasse einschließen, vielleicht in TreeNode umbenennen?
quelle
Action<T>
Delegaten verwenden :public void traverse(NTree<T> node, Action<T> visitor)
. Die Signatur von Aktion <> lautet :void Action<T>( T obj )
. Es gibt auch Versionen von 0 bis 4 verschiedenen Parametern. Es gibt auch einen analogen Delegaten für Funktionen namensFunc<>
.--i == 0
wird nur im Einzelfall funktionieren? Ist das wahr. Das hat mich verwirrtHier ist meine, die meiner Meinung nach Aaron Gages sehr ähnlich ist , nur ein bisschen konventioneller. Für meine Zwecke habe ich keine Leistungsprobleme mit
List<T>
. Es wäre einfach genug, bei Bedarf zu einer LinkedList zu wechseln.quelle
public TreeNode<T> InsertChild(TreeNode<T> parent, T value) { var node = new TreeNode<T>(value) { Parent = parent }; parent._children.Add(node); return node; }
var five = myTree.AddChild(5); myTree.InsertChild(five, 55);
Noch eine Baumstruktur:
Beispielnutzung:
BONUS
Siehe vollwertigen Baum mit:
https://github.com/gt4dev/yet-another-tree-structure
quelle
node
das? Bedeutet das, dass ich über den Baum iterieren muss, um den Suchcode zu verwenden?IEnumerable<>
Mitglieder implementiert sind und daher nicht kompiliert werden.Die allgemein ausgezeichnete C5 Generic Collection Library verfügt über verschiedene baumbasierte Datenstrukturen, darunter Sets, Taschen und Wörterbücher. Der Quellcode ist verfügbar, wenn Sie die Implementierungsdetails untersuchen möchten. (Ich habe C5-Sammlungen im Produktionscode mit guten Ergebnissen verwendet, obwohl ich keine der Baumstrukturen speziell verwendet habe.)
quelle
Siehe http://quickgraph.codeplex.com/
QuickGraph bietet generische gerichtete / ungerichtete Graphdatenstrukturen und -algorithmen für .Net 2.0 und höher. QuickGraph enthält Algorithmen wie Tiefen-Erst-Suche, Atem-Erst-Suche, A * -Suche, kürzester Pfad, k-kürzester Pfad, maximaler Fluss, minimaler Spanning Tree, am wenigsten verbreitete Vorfahren usw. QuickGraph unterstützt MSAGL, GLEE und Graphviz to Rendern der Grafiken, Serialisierung in GraphML usw.
quelle
Wenn Sie Ihre eigenen Daten schreiben möchten, können Sie mit diesem sechsteiligen Dokument beginnen, in dem die effektive Verwendung von C # 2.0-Datenstrukturen und die Analyse Ihrer Implementierung von Datenstrukturen in C # beschrieben werden. Jeder Artikel enthält Beispiele und ein Installationsprogramm mit Beispielen, denen Sie folgen können.
"Eine umfassende Untersuchung von Datenstrukturen mit C # 2.0" von Scott Mitchell
quelle
Ich habe eine kleine Erweiterung der Lösungen.
Mit einer rekursiven generischen Deklaration und einer ableitenden Unterklasse können Sie sich besser auf Ihr tatsächliches Ziel konzentrieren.
Beachten Sie, dass es sich von einer nicht generischen Implementierung unterscheidet. Sie müssen 'node' nicht in 'NodeWorker' umwandeln.
Hier ist mein Beispiel:
quelle
Hier ist meine eigene:
Ausgabe:
quelle
Probieren Sie dieses einfache Beispiel aus.
quelle
Ich erstelle eine Node-Klasse , die für andere hilfreich sein könnte. Die Klasse hat Eigenschaften wie:
Es besteht auch die Möglichkeit, eine flache Liste von Elementen mit einer ID und einer ParentId in einen Baum zu konvertieren. Die Knoten enthalten einen Verweis sowohl auf die untergeordneten als auch auf die übergeordneten Knoten, sodass iterierende Knoten sehr schnell ausgeführt werden können.
quelle
Da es nicht erwähnt wird, möchte ich Sie auf die jetzt veröffentlichte .net-Codebasis aufmerksam machen: speziell auf den Code für a
SortedSet
, der einen Rot-Schwarz-Baum implementiert:https://github.com/Microsoft/referencesource/blob/master/System/compmod/system/collections/generic/sortedset.cs
Dies ist jedoch eine ausgeglichene Baumstruktur. Meine Antwort bezieht sich also eher auf die meiner Meinung nach einzige native Baumstruktur in der .net-Kernbibliothek.
quelle
Ich habe den Code vervollständigt, den @Berezh geteilt hat.
quelle
Hier ist ein Baum
Sie können sogar Initialisierer verwenden:
quelle
Die meisten Bäume werden durch die Daten gebildet, die Sie verarbeiten.
Ein weiteres Beispiel ist ein Analysebaum in einem Compiler…
Beide Beispiele zeigen, dass das Konzept eines Baums Teil der Domäne der Daten ist und die Verwendung eines separaten Allzweckbaums mindestens die Anzahl der erstellten Objekte verdoppelt und die erneute Programmierung der API erschwert.
Was wir wollen, ist eine Möglichkeit, die Standardbaumoperationen wiederzuverwenden, ohne sie für alle Bäume erneut implementieren zu müssen, während gleichzeitig keine Standardbaumklasse verwendet werden muss. Boost hat versucht, diese Art von Problem für C ++ zu lösen, aber ich sehe noch keinen Effekt für .NET, der angepasst wird.
quelle
Ich habe eine vollständige Lösung und ein Beispiel mit der obigen NTree-Klasse hinzugefügt und auch die "AddChild" -Methode hinzugefügt ...
mit
quelle
Hier ist meine Implementierung von BST
quelle
Wenn Sie diesen Baum auf der GUI anzeigen möchten , können Sie TreeView und TreeNode verwenden . (Ich nehme an, technisch gesehen können Sie einen TreeNode erstellen, ohne ihn auf einer GUI zu platzieren, aber er hat mehr Overhead als eine einfache selbst entwickelte TreeNode-Implementierung.)
quelle
Wenn Sie eine Implementierung einer verwurzelten Baumdatenstruktur benötigen, die weniger Speicher benötigt, können Sie Ihre Node-Klasse wie folgt schreiben (C ++ - Implementierung):
quelle