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

Ich habe eine kleine "TreeMap" Klasse basierend auf "HashMap" geschrieben, die das Hinzufügen von Pfaden unterstützt:

import java.util.HashMap;
import java.util.LinkedList;

public class TreeMap extends LinkedHashMap> {

    public void put(T[] path) {
        LinkedList list = new LinkedList<>();
        for (T key : path) {
            list.add(key);
        }
        return put(list);
    }

    public void put(LinkedList path) {
        if (path.isEmpty()) {
            return;
        }
        T key = path.removeFirst();
        TreeMap val = get(key);
        if (val == null) {
            val = new TreeMap<>();
            put(key, val);
        }
        val.put(path);
    }

}

Es kann verwendet werden, um einen Baum von Dingen vom Typ "T" (generisch) zu speichern, unterstützt jedoch (noch) nicht das Speichern von zusätzlichen Daten in seinen Knoten. Wenn Sie eine Datei wie diese haben:

root, child 1
root, child 1, child 1a
root, child 1, child 1b
root, child 2
root, child 3, child 3a

Dann können Sie es zu einem Baum machen, indem Sie folgendes ausführen:

TreeMap root = new TreeMap<>();
Scanner scanner = new Scanner(new File("input.txt"));
while (scanner.hasNextLine()) {
  root.put(scanner.nextLine().split(", "));
}

Und Sie erhalten einen schönen Baum. Es sollte einfach sein, es an Ihre Bedürfnisse anzupassen.

Answer 2

Zum Beispiel:

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * @author X2
 *
 * @param 
 */
public class HisTree 
{
    private Node root;

    public HisTree(T rootData) 
    {
        root = new Node();
        root.setData(rootData);
        root.setChildren(new ArrayList>());
    }

}

class Node 
{

    private T data;
    private Node parent;
    private List> children;

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node getParent() {
        return parent;
    }
    public void setParent(Node parent) {
        this.parent = parent;
    }
    public List> getChildren() {
        return children;
    }
    public void setChildren(List> children) {
        this.children = children;
    }
}

Answer 3

Ich habe eine Baum-Bibliothek geschrieben, die gut mit Java8 funktioniert und keine anderen Abhängigkeiten hat. Sie bietet auch eine lockere Interpretation einiger Ideen aus der funktionalen Programmierung und ermöglicht es Ihnen, den gesamten Baum oder Teilbäume abzubilden/filtern/aufzuräumen/zu durchsuchen.

https://github.com/RutledgePaulV/prune

Die Implementierung macht nichts Besonderes beim Indexieren und ich bin nicht von der Rekursion abgewichen, daher ist es möglich, dass die Leistung bei großen Bäumen abnimmt und der Stack überlaufen kann. Aber wenn Sie nur einen einfachen Baum mit geringer bis mäßiger Tiefe benötigen, denke ich, dass es gut genug funktioniert. Es bietet eine vernünftige (wertebasierte) Definition von Gleichheit und hat auch eine toString-Implementierung, die es Ihnen ermöglicht, den Baum zu visualisieren!

Answer 4

Es gibt keine spezifische Datenstruktur in Java, die Ihren Anforderungen entspricht. Ihre Anforderungen sind ziemlich spezifisch und dafür müssen Sie Ihre eigene Datenstruktur entwerfen. Wenn man sich Ihre Anforderungen ansieht, kann jeder sagen, dass Sie irgendeine Art von n-ären Baum mit bestimmten Funktionen benötigen. Sie können Ihre Datenstruktur wie folgt entwerfen:

1. Die Struktur des Knotens des Baumes wäre wie folgt: Inhalt im Knoten und Liste der Kinder wie: class Node { String Wert; Liste Kinder;}
2. Sie müssen die Kinder eines bestimmten Strings abrufen, daher können Sie 2 Methoden haben: 1: Node searchNode(String str), die den Knoten zurückgibt, der den gleichen Wert wie der gegebene Eingang hat (verwenden Sie BFS zum Suchen) 2: Liste getChildren(String str): Diese Methode ruft intern die searchNode auf, um den Knoten mit demselben String zu finden, und erstellt dann die Liste aller String-Werte der Kinder und gibt sie zurück.
3. Sie müssen auch einen String in den Baum einfügen. Sie müssen eine Methode schreiben, sagen wir void insert(String Eltern, String Wert): Diese Methode sucht erneut den Knoten mit dem Wert gleich dem Elternwert und dann können Sie einen Knoten mit dem angegebenen Wert erstellen und zur Liste der Kinder des gefundenen Elternknotens hinzufügen.

Ich würde vorschlagen, die Struktur des Knotens in einer Klasse wie Class Node { String Wert; Liste Kinder;} und alle anderen Methoden wie search, insert und getChildren in einer anderen NodeUtils-Klasse zu schreiben, damit Sie auch die Wurzel des Baumes übergeben können, um Operationen an einem bestimmten Baum durchzuführen, wie folgt: class NodeUtils{ public static Node search(Node root, String value){// Führe BFS durch und gib Node zurück}

Answer 5

    // TestTree.java
// Ein einfacher Test, um zu sehen, wie wir einen Baum erstellen und ihn füllen können
//
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;

public class TestTree extends JFrame {

  JTree baum;
  DefaultTreeModel baumModell;

  public TestTree( ) {
    super("Beispiel für Baumtest");
    setSize(400, 300);
    setDefaultCloseOperation(EXIT_ON_CLOSE);
  }

  public void init( ) {
    // Aufbau einer Reihe von TreeNodes. Wir verwenden DefaultMutableTreeNode, da das
    // DefaultTreeModel es verwenden kann, um einen vollständigen Baum aufzubauen.
    DefaultMutableTreeNode wurzel = new DefaultMutableTreeNode("Wurzel");
    DefaultMutableTreeNode subwurzel = new DefaultMutableTreeNode("Teilwurzel");
    DefaultMutableTreeNode blatt1 = new DefaultMutableTreeNode("Blatt 1");
    DefaultMutableTreeNode blatt2 = new DefaultMutableTreeNode("Blatt 2");

    // Erstellen unseres Baummodells, beginnend beim Wurzelknoten, und dann erstellen
    // wir daraus einen JTree.
    baumModell = new DefaultTreeModel(wurzel);
    baum = new JTree(baumModell);

    // Aufbau des Baums aus den erstellten Knoten.
    baumModell.insertNodeInto(subwurzel, wurzel, 0);
    // Oder prägnanter:
    subwurzel.add(blatt1);
    wurzel.add(blatt2);

    // Anzeigen des Baums.
    getContentPane( ).add(baum, BorderLayout.CENTER);
  }

  public static void main(String args[]) {
    TestTree tt = new TestTree( );
    tt.init( );
    tt.setVisible(true);
  }
}