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

public class Baum {
    private List blätter = new LinkedList();
    private Baum elternknoten = null;
    private String daten;

    public Baum(String daten, Baum elternknoten) {
        this.daten = daten;
        this.elternknoten = elternknoten;
    }
}

Natürlich können Sie Hilfsmethoden hinzufügen, um Kinder hinzuzufügen/entfernen.

Answer 2

Sie sollten damit beginnen zu definieren, was ein Baum ist (für das Domain), dies geschieht am besten durch die Definition der Schnittstelle zuerst. Nicht alle Baumstrukturen sind veränderbar, die Fähigkeit, Knoten hinzuzufügen und zu entfernen, sollte ein optionales Feature sein, daher erstellen wir eine zusätzliche Schnittstelle dafür.

Es ist nicht notwendig, Knotenobjekte zu erstellen, die die Werte halten, tatsächlich sehe ich dies als einen großen Designfehler und Überkopf in den meisten Baumimplementierungen. Wenn Sie sich Swing anschauen, das TreeModel ist frei von Knotenklassen (nur DefaultTreeModel verwendet TreeNode), da sie wirklich nicht benötigt werden.

public interface Baum  extends Serializable {
    List getRoots ();
    N getParent (N node);
    List getChildren (N node);
}

Veränderliche Baumstruktur (ermöglicht das Hinzufügen und Entfernen von Knoten):

public interface MutierbarerBaum  extends Baum {
    boolean add (N parent, N node);
    boolean remove (N node, boolean cascade);
}

Anhand dieser Schnittstellen muss sich der Code, der Bäume verwendet, nicht sehr um die Implementierung des Baumes kümmern. Dies ermöglicht es Ihnen, sowohl generische Implementierungen als auch spezialisierte zu verwenden, bei denen Sie den Baum realisieren, indem Sie Funktionen an eine andere API delegieren.

Beispiel: Dateibaumstruktur

public class DateiBaum implements Baum {

    @Override
    public List getRoots() {
        return Arrays.stream(Datei.listRoots()).collect(Collectors.toList());
    }

    @Override
    public Datei getParent(Datei node) {
        return node.getParentFile();
    }

    @Override
    public List getChildren(Datei node) {
        if (node.isDirectory()) {
            Datei[] children = node.listFiles();
            if (children != null) {
                return Arrays.stream(children).collect(Collectors.toList());
            }
        }
        return Collections.emptyList();
    }
}

Beispiel: generische Baumstruktur (basierend auf Eltern-/Kinderbeziehungen):

public class KartierteBaumstruktur implements MutierbarerBaum {

    public static void main(String[] args) {

        MutierbarerBaum baum = new KartierteBaumstruktur<>();
        baum.add("A", "B");
        baum.add("A", "C");
        baum.add("C", "D");
        baum.add("E", "A");
        System.out.println(baum);
    }

    private final Map knotenEltern = new HashMap<>();
    private final LinkedHashSet knotenListe = new LinkedHashSet<>();

    private void checkNotNull(N knoten, String parameterName) {
        if (knoten == null)
            throw new IllegalArgumentException(parameterName + " darf nicht null sein");
    }

    @Override
    public boolean add(N parent, N node) {
        checkNotNull(parent, "parent");
        checkNotNull(node, "node");

        // Überprüfung auf Zyklen
        N aktuell = parent;
        do {
            if (node.equals(aktuell)) {
                throw new IllegalArgumentException("Knoten darf nicht der gleiche sein oder ein Vorfahre des Elternknotens sein");
            }
        } while ((aktuell = getParent(aktuell)) != null);

        boolean hinzugefügt = knotenListe.add(node);
        knotenListe.add(parent);
        knotenEltern.put(node, parent);
        return hinzugefügt;
    }

    @Override
    public boolean remove(N node, boolean cascade) {
        checkNotNull(node, "node");

        if (!knotenListe.contains(node)) {
            return false;
        }
        if (cascade) {
            for (N kind : getChildren(node)) {
                remove(kind, true);
            }
        } else {
            for (N kind : getChildren(node)) {
                knotenEltern.remove(kind);
            }
        }
        knotenListe.remove(node);
        return true;
    }

    @Override
    public List getRoots() {
        return getChildren(null);
    }

    @Override
    public N getParent(N node) {
        checkNotNull(node, "node");
        return knotenEltern.get(node);
    }

    @Override
    public List getChildren(N node) {
        List kinder = new LinkedList<>();
        for (N n : knotenListe) {
            N eltern = knotenEltern.get(n);
            if (node == null && eltern == null) {
                kinder.add(n);
            } else if (node != null && eltern != null && eltern.equals(node)) {
                kinder.add(n);
            }
        }
        return kinder;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        dumpNodeStructure(builder, null, "- ");
        return builder.toString();
    }

    private void dumpNodeStructure(StringBuilder builder, N node, String prefix) {
        if (node != null) {
            builder.append(prefix);
            builder.append(node.toString());
            builder.append('\n');
            prefix = "  " + prefix;
        }
        for (N kind : getChildren(node)) {
            dumpNodeStructure(builder, kind, prefix);
        }
    }
}

Answer 3

Keine Antwort erwähnt über vereinfachten, aber funktionierenden Code, also hier ist er:

public class TreeNodeArray {
    public T value;
    public final  java.util.List> kids =  new java.util.ArrayList>();
}

Answer 4

Wenn Sie Whiteboard-Codierung, ein Interview oder sogar nur die Planung zur Verwendung eines Baums durchführen, ist die Wortlast hier ein wenig zu viel.

Es sollte weiter gesagt werden, dass der Grund, warum ein Baum nicht wie z.B. ein Pair (über den dasselbe gesagt werden könnte) enthalten ist, darin besteht, dass Sie Ihre Daten in der Klasse, die sie verwendet, kapseln sollten, und die einfachste Implementierung so aussieht:

/***
/* Innerhalb der Klasse, die aus irgendeinem Grund einen Binärbaum verwendet. Sie könnten
/* mit Generika verallgemeinern, wenn die Elternklasse unterschiedliche Wertetypen benötigt.
 */
private class Node {
  public String value;
  public Node[] nodes; // Oder ein Iterable nodes;
}

Das war es schon für einen Baum mit beliebiger Breite.

Wenn Sie einen Binärbaum möchten, ist es oft einfacher, mit benannten Feldern zu verwenden:

private class Node { // Mit Paketsichtbarkeit ist eine Option
  String value;
  Node left;
  Node right;
}

Oder wenn Sie einen Trie möchten:

private class Node {
  String value;
  Map nodes;
}

Jetzt haben Sie gesagt, dass Sie

in der Lage sein möchten, alle Kinder (irgendeine Art von Liste oder Array von Strings) zu erhalten, die einen Eingabestring, der einen bestimmten Knoten darstellt, repräsentieren

Das klingt nach Hausaufgabe.
Aber da ich ziemlich sicher bin, dass jeder Termin jetzt abgelaufen ist…

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

public class kidsOfMatchTheseDays {
 static private class Node {
   String value;
   Node[] nodes;
 }

 // Pre-Order; du hast es nicht spezifiziert.
 static public List list(Node node, String find) {
   return list(node, find, new ArrayList(), false);
 }

 static private ArrayList list(
     Node node,
     String find,
     ArrayList list,
     boolean add) {
   if (node == null) {
     return list;
   }
   if (node.value.equals(find)) {
     add = true;
   }
   if (add) {
     list.add(node.value);
   }
   if (node.nodes != null) {
     for (Node child: node.nodes) {
       list(child, find, list, add);
     }
   }
   return list;
 }

 public static final void main(String... args) {
   // Normalerweise muss man nie Setup wie dieses machen, also entschuldigen Sie den Stil
   // Und es könnte sauberer sein, indem man einen Konstruktor hinzufügt, wie z.B.:
   //     Node(String val, Node... children) {
   //         value = val;
   //         nodes = children;
   //     }
   Node tree = new Node();
   tree.value = "root";
   Node[] n = {new Node(), new Node()};
   tree.nodes = n;
   tree.nodes[0].value = "leftish";
   tree.nodes[1].value = "rightish-leafy";
   Node[] nn = {new Node()};
   tree.nodes[0].nodes = nn;
   tree.nodes[0].nodes[0].value = "off-leftish-leaf";
   // Genug Setup
   System.out.println(Arrays.toString(list(tree, args[0]).toArray()));
 }
}

Dies ermöglicht Ihnen die Verwendung wie:

$ java kidsOfMatchTheseDays leftish
[leftish, off-leftish-leaf]
$ java kidsOfMatchTheseDays root
[root, leftish, off-leftish-leaf, rightish-leafy]
$ java kidsOfMatchTheseDays rightish-leafy
[rightish-leafy]
$ java kidsOfMatchTheseDays a
[]

Answer 5

Sie können jede XML-API von Java als Document und Node verwenden..da XML eine Baumstruktur mit Strings ist