Gibt es eine Standard-Java-Bibliotheksklasse zur Darstellung eines Baums in Java?
Insbesondere muss ich Folgendes darstellen:
- Der Unterbaum an jedem Knoten kann eine beliebige Anzahl von untergeordneten Elementen haben
- Jeder Knoten (nach dem Stamm) und seine untergeordneten Knoten haben einen Zeichenfolgenwert
- Ich muss alle untergeordneten Elemente (eine Art Liste oder ein Array von Zeichenfolgen) eines bestimmten Knotens und seinen Zeichenfolgenwert abrufen (dh eine Methode, die einen Knoten als Eingabe verwendet und alle Zeichenfolgenwerte des untergeordneten Knotens als Ausgabe zurückgibt).
Gibt es dafür eine verfügbare Struktur oder muss ich meine eigene erstellen (wenn ja, wären Implementierungsvorschläge großartig).
Antworten:
Hier:
Dies ist eine grundlegende Baumstruktur, die für
String
oder jedes andere Objekt verwendet werden kann. Es ist ziemlich einfach, einfache Bäume zu implementieren, um das zu tun, was Sie brauchen.Alles, was Sie hinzufügen müssen, sind Methoden zum Hinzufügen, Entfernen, Durchlaufen und Konstruieren. Das
Node
ist der Grundbaustein derTree
.quelle
Tree
Klasse nicht notwendig, weil jederNode
für sich als Baum gesehen werden kann.Noch eine Baumstruktur:
Beispielnutzung:
BONUS
Siehe vollwertigen Baum mit:
https://github.com/gt4dev/yet-another-tree-structure
quelle
hasNext()
vor jedem Aufruf aufrufen müssennext()
, um gültige Ergebnisse zu erhalten. Dies ist nicht Teil derIterator
Spezifikation.Im JDK ist tatsächlich eine ziemlich gute Baumstruktur implementiert.
Schauen Sie sich javax.swing.tree , TreeModel und TreeNode an . Sie sind für die Verwendung mit dem konzipiert,
JTreePanel
aber sie sind in der Tat eine ziemlich gute Baumimplementierung, und nichts hindert Sie daran, sie ohne Swing-Schnittstelle zu verwenden.Beachten Sie, dass Sie ab Java 9 diese Klassen möglicherweise nicht mehr verwenden möchten, da sie in den 'Kompaktprofilen' nicht vorhanden sind .
quelle
Was ist damit?
quelle
setAsParent
odergetHead
tun, und dies ist die Zeit, in der ich wirklich Hilfe bei Baumdatenstrukturen bekommen könnte. Auch die Originalquelle des Dokuments enthält keine Kommentare.Ich schrieb eine kleine Bibliothek , dass Griffe generic Bäume. Es ist viel leichter als das Swing-Zeug. Ich habe auch ein Maven-Projekt dafür.
quelle
Natürlich können Sie Dienstprogrammmethoden hinzufügen, um untergeordnete Elemente hinzuzufügen / zu entfernen.
quelle
Sie sollten zunächst definieren, was ein Baum ist (für die Domäne). Dies geschieht am besten, indem Sie zuerst die Schnittstelle definieren . Nicht alle Baumstrukturen können geändert werden und können hinzugefügt und entfernt werden Knoten sollte eine optionale Funktion sein. erstellen wir hierfür eine zusätzliche Schnittstelle.
Es ist nicht erforderlich, Knotenobjekte zu erstellen, die die Werte enthalten . Tatsächlich sehe ich dies in den meisten Baumimplementierungen als großen Konstruktionsfehler und Overhead an. Wenn Sie sich Swing ansehen,
TreeModel
ist das frei von Knotenklassen (DefaultTreeModel
nutzt nurTreeNode
), da diese nicht wirklich benötigt werden.Veränderbare Baumstruktur (ermöglicht das Hinzufügen und Entfernen von Knoten):
Angesichts dieser Schnittstellen muss sich Code, der Bäume verwendet, nicht viel darum kümmern, wie der Baum implementiert wird. Auf diese Weise können Sie sowohl generische als auch spezialisierte Implementierungen verwenden verwenden, bei denen Sie den Baum realisieren, indem Sie Funktionen an eine andere API delegieren.
Beispiel: Dateibaumstruktur
Beispiel: generische Baumstruktur (basierend auf Eltern / Kind-Beziehungen):
quelle
In keiner Antwort wird ein stark vereinfachter, aber funktionierender Code erwähnt. Hier ist er also:
quelle
Sie können jede XML-API von Java als Dokument und Knoten verwenden. XML ist eine Baumstruktur mit Strings
quelle
Wenn Sie Whiteboard-Codierung, ein Interview oder einfach nur die Verwendung eines Baums planen, ist die Ausführlichkeit dieser Elemente ein wenig groß.
Es sollte ferner gesagt werden, dass der Grund, warum ein Baum dort nicht vorhanden ist, wie z. B. a
Pair
(worüber dasselbe gesagt werden könnte), darin besteht, dass Sie Ihre Daten in der Klasse kapseln sollten, die ihn verwendet, und die einfachste Implementierung sieht wie folgt aus:Das ist es wirklich für einen Baum beliebiger Breite.
Wenn Sie einen Binärbaum möchten, ist die Verwendung mit benannten Feldern oft einfacher:
Oder wenn Sie einen Versuch wollten:
Jetzt hast du gesagt, du willst
Das klingt nach deinen Hausaufgaben.
Aber da ich mir ziemlich sicher bin, dass jetzt eine Frist abgelaufen ist ...
Dies bringt Sie dazu, wie folgt zu verwenden:
quelle
Schauen Sie sich nach dem Vorbild von Gareths Antwort DefaultMutableTreeNode an . Es ist nicht generisch, scheint aber ansonsten in die Rechnung zu passen. Obwohl es im Paket javax.swing enthalten ist, hängt es nicht von AWT- oder Swing-Klassen ab. Tatsächlich enthält der Quellcode den Kommentar
// ISSUE: this class depends on nothing in AWT -- move to java.util?
quelle
In Java gibt es einige Baumdatenstrukturen, z. B. DefaultMutableTreeNode in JDK Swing, Tree im Stanford-Parser-Paket und andere Spielzeugcodes. Aber keines davon ist ausreichend und doch klein genug für den allgemeinen Zweck.
Das Java-Tree- Projekt versucht, eine andere universelle Tree-Datenstruktur in Java bereitzustellen. Der Unterschied zwischen diesem und anderen ist
quelle
Da in der Frage nach einer verfügbaren Datenstruktur gefragt wird, kann ein Baum aus Listen oder Arrays erstellt werden:
instanceof
kann verwendet werden, um zu bestimmen, ob ein Element ein Teilbaum oder ein Endknoten ist.quelle
Object
s wären entweder die Blattobjekte (zum BeispielString
s) oder Zweige (dargestellt durch Arrays). Und es funktioniert: Dieser Code wird kompiliert und es wird ein kleiner Baum vonString
s erstellt.So einfach wie es nur geht und sehr einfach zu bedienen. Um es zu verwenden, erweitern Sie es:
quelle
Beispielsweise :
quelle
In der Vergangenheit habe ich dafür gerade eine verschachtelte Karte verwendet. Dies ist, was ich heute benutze, es ist sehr einfach, aber es passt zu meinen Bedürfnissen. Vielleicht hilft das einem anderen.
quelle
Ich habe eine kleine "TreeMap" -Klasse geschrieben, die auf "HashMap" basiert und das Hinzufügen von Pfaden unterstützt:
Es kann verwendet werden, um einen Baum von Dingen vom Typ "T" (generisch) zu speichern, unterstützt jedoch (noch) nicht das Speichern zusätzlicher Daten in seinen Knoten. Wenn Sie eine Datei wie diese haben:
Dann können Sie daraus einen Baum machen, indem Sie Folgendes ausführen:
Und du wirst einen schönen Baum bekommen. Es sollte einfach sein, sich an Ihre Bedürfnisse anzupassen.
quelle
Sie können die in Apache JMeter enthaltene HashTree- Klasse verwenden, die Teil des Jakarta-Projekts ist.
Die HashTree-Klasse ist im Paket org.apache.jorphan.collections enthalten. Obwohl dieses Paket nicht außerhalb des JMeter-Projekts veröffentlicht wurde, können Sie es einfach herunterladen:
1) Laden Sie die JMeter-Quellen herunter .
2) Erstellen Sie ein neues Paket.
3) Kopieren Sie darauf / src / jorphan / org / apache / jorphan / collection /. Alle Dateien außer Data.java
4) Kopieren Sie auch /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java
5) HashTree ist einsatzbereit.
quelle
In Java gibt es keine spezifische Datenstruktur, die Ihren Anforderungen entspricht. Ihre Anforderungen sind sehr spezifisch und dafür müssen Sie Ihre eigene Datenstruktur entwerfen. Wenn Sie sich Ihre Anforderungen ansehen, kann jeder sagen, dass Sie eine Art Baum mit einer bestimmten Funktionalität benötigen. Sie können Ihre Datenstruktur folgendermaßen gestalten:
Ich würde vorschlagen, dass Sie die Struktur des Knotens in einer Klasse wie Class Node {String value; Listen Sie untergeordnete Elemente;} und alle anderen Methoden wie search, insert und getChildren in einer anderen NodeUtils-Klasse auf, damit Sie auch die Wurzel des Baums übergeben können, um eine Operation für einen bestimmten Baum auszuführen, z. B.: Class NodeUtils {public static Node search (Knotenwurzel, String-Wert) {// BFS ausführen und Node zurückgeben}
quelle
quelle
Ich habe eine Baumbibliothek geschrieben, die gut mit Java8 funktioniert und keine anderen Abhängigkeiten aufweist. Es bietet auch eine lose Interpretation einiger Ideen aus der funktionalen Programmierung und ermöglicht das Zuordnen / Filtern / Beschneiden / Durchsuchen des gesamten Baums oder der Teilbäume.
https://github.com/RutledgePaulV/prune
Die Implementierung macht nichts Besonderes mit der Indizierung und ich bin nicht von der Rekursion abgewichen. Daher ist es möglich, dass sich die Leistung bei großen Bäumen verschlechtert und Sie den Stapel sprengen können. Aber wenn Sie nur einen einfachen Baum von kleiner bis mittlerer Tiefe benötigen, funktioniert er meiner Meinung nach gut genug. Es bietet eine vernünftige (wertebasierte) Definition von Gleichheit und eine toString-Implementierung, mit der Sie den Baum visualisieren können!
quelle
Bitte überprüfen Sie den folgenden Code, in dem ich Tree-Datenstrukturen verwendet habe, ohne Collection-Klassen zu verwenden. Der Code kann Fehler / Verbesserungen aufweisen, aber bitte verwenden Sie diesen nur als Referenz
quelle
Sie können die TreeSet-Klasse in java.util verwenden. *. Es funktioniert wie ein binärer Suchbaum, ist also bereits sortiert. Die TreeSet-Klasse implementiert Iterable-, Collection- und Set-Schnittstellen. Sie können den Baum mit einem Iterator wie eine Menge durchlaufen.
Sie können Java Doc und einige andere überprüfen .
quelle
Benutzerdefiniertes Tree-Implementieren von Tree ohne Verwendung des Collection-Frameworks. Es enthält verschiedene grundlegende Operationen, die für die Tree-Implementierung erforderlich sind.
quelle