Wie implementiert man eine Baum-Datenstruktur in Java?

Question

Gibt es eine Standard-Java-Bibliotheksklasse, um einen Baum in Java darzustellen?

Speziell muss ich das Folgende darstellen:

• Der Teilbaum an einem beliebigen Knoten kann eine beliebige Anzahl von Kindern haben
• Jeder Knoten (nach der Wurzel) und seine Kinder haben einen String-Wert
• Ich muss alle Kinder (eine Art Liste oder Array von Strings) eines gegebenen Knotens und ihren Zeichenfolgenwert erhalten (d.h. eine Methode, die einen Knoten als Eingabe nimmt und alle Zeichenfolgenwerte der Kinderknoten als Ausgabe zurückgibt)

Gibt es eine verfügbare Struktur dafür oder muss ich meine eigene erstellen (falls erforderlich, wären Implementierungsvorschläge toll).

Answer 1

Entlang der gleichen Linien wie Gareth's Antwort, schau dir DefaultMutableTreeNode an. Es ist nicht generisch, aber ansonsten scheint es zu passen. Obwohl es sich im javax.swing-Paket befindet, hängt es nicht von einer AWT- oder Swing-Klasse ab. Tatsächlich hat der Quellcode tatsächlich den Kommentar // PROBLEM: diese Klasse hängt von nichts in AWT ab -- sollte nach java.util verschoben werden?

Answer 2

Es gibt ein paar Baumdatenstrukturen in Java, wie z. B. DefaultMutableTreeNode in JDK Swing, Tree im Stanford-Parserpaket und andere Spielzeugcodes. Aber keiner davon ist bisher ausreichend, aber klein genug für allgemeine Zwecke.

Java-Baum Projekt versucht, eine weitere allgemeine Baumdatenstruktur in Java bereitzustellen. Der Unterschied zu anderen besteht darin:

• Völlig kostenlos. Sie können es überall verwenden (außer in Ihren Hausaufgaben :P)
• Klein aber allgemein genug. Ich habe alles der Datenstruktur in einer Klassendatei zusammengefasst, sodass es einfach zu kopieren/einfügen ist.
• Nicht nur Spielzeug. Ich bin mir dutzender Java-Baumcodes bewusst, die nur binäre Bäume oder begrenzte Operationen verarbeiten können. Dieser TreeNode ist viel mehr als das. Es bietet verschiedene Möglichkeiten, Knoten zu besuchen, wie Vororder, Nachorder, Breitensuche, Blätter, Pfad zur Wurzel usw. Darüber hinaus werden auch Iteratoren für die Zweckmäßigkeit bereitgestellt.
• Weitere Dienstprogramme werden hinzugefügt. Ich bin bereit, weitere Operationen hinzuzufügen, um dieses Projekt umfassend zu machen, insbesondere wenn Sie eine Anfrage über github senden.

Answer 3

Da die Frage nach einer verfügbaren Datenstruktur fragt, kann ein Baum aus Listen oder Arrays konstruiert werden:

Object[] tree = new Object[2];
tree[0] = "Hallo";
{
  Object[] subtree = new Object[2];
  subtree[0] = "Auf Wiedersehen";
  subtree[1] = "";
  tree[1] = subtree;
}

instanceof kann verwendet werden, um festzustellen, ob ein Element ein Unterbaum oder ein Endknoten ist.

Answer 4

public abstract class Node {
  List children;

  public List getChidren() {
    if (children == null) {
      children = new ArrayList<>();
    }
    return chidren;
  }
}

So einfach wie möglich und sehr einfach zu verwenden. Um es zu verwenden, erweitern Sie es:

public class MenuItem extends Node {
  String label;
  String href;
  ...
}

Answer 5

In der Vergangenheit habe ich das einfach mit einer verschachtelten Karte gemacht. Das ist das, was ich heute benutze, es ist sehr einfach, aber es entspricht meinen Bedürfnissen. Vielleicht hilft es einem anderen.

import com.fasterxml.jackson.annotation.JsonValue;
import com.fasterxml.jackson.databind.ObjectMapper;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * Erstellt von kic am 16.07.15.
 */
public class NestedMap {
    private final Map root = new HashMap<>();

    public NestedMap put(K key) {
        Object nested = root.get(key);

        if (nested == null || !(nested instanceof NestedMap)) root.put(key, nested = new NestedMap<>());
        return (NestedMap) nested;
    }

    public Map.Entry put(K key, V value) {
        root.put(key, value);

        return (Map.Entry) root.entrySet().stream().filter(e -> ((Map.Entry) e).getKey().equals(key)).findFirst().get();
    }

    public NestedMap get(K key) {
        return (NestedMap) root.get(key);
    }

    public V getValue(K key) {
        return (V) root.get(key);
    }

    @JsonValue
    public Map getRoot() {
        return root;
    }

    public static void main(String[] args) throws Exception {
        NestedMap test = new NestedMap<>();
        test.put("a").put("b").put("c", 12);
        Map.Entry foo = test.put("a").put("b").put("d", 12);
        test.put("b", 14);
        ObjectMapper mapper = new ObjectMapper();
        System.out.println(mapper.writeValueAsString(test));

        foo.setValue(99);
        System.out.println(mapper.writeValueAsString(test));

        System.out.println(test.get("a").get("b").getValue("d"));
    }
}