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

Hier:

public class Tree {
    private Node root;

    public Tree(T rootData) {
        root = new Node();
        root.data = rootData;
        root.children = new ArrayList>();
    }

    public static class Node {
        private T data;
        private Node parent;
        private List> children;
    }
}

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 erledigen, was Sie benötigen.

Alles, was Sie hinzufügen müssen, sind Methoden zum Hinzufügen, Entfernen, Durchqueren und Konstruktoren. Der Node ist der grundlegende Baustein des Tree.

Answer 2

Noch eine Baumstruktur:

public class TreeNode implements Iterable> {

    T data;
    TreeNode parent;
    List> children;

    public TreeNode(T data) {
        this.data = data;
        this.children = new LinkedList>();
    }

    public TreeNode addChild(T child) {
        TreeNode childNode = new TreeNode(child);
        childNode.parent = this;
        this.children.add(childNode);
        return childNode;
    }

    // andere Funktionen ...

}

Beispiel Verwendung:

TreeNode root = new TreeNode("root");
{
    TreeNode node0 = root.addChild("node0");
    TreeNode node1 = root.addChild("node1");
    TreeNode node2 = root.addChild("node2");
    {
        TreeNode node20 = node2.addChild(null);
        TreeNode node21 = node2.addChild("node21");
        {
            TreeNode node210 = node20.addChild("node210");
        }
    }
}

BONUS
Siehe vollständig ausgearbeiteten Baum mit:

• iterator
• Suchfunktion
• Java/C#

https://github.com/gt4dev/yet-another-tree-structure

Answer 3

Es gibt tatsächlich eine ziemlich gute Baumstruktur, die in der JDK implementiert ist.

Schauen Sie sich javax.swing.tree, TreeModel und TreeNode an. Sie sind dafür gedacht, mit dem JTreePanel verwendet zu werden, aber sie sind tatsächlich eine ziemlich gute Baumimplementierung und nichts hindert Sie daran, sie ohne eine Swing-Schnittstelle zu verwenden.

Beachten Sie, dass Sie ab Java 9 möglicherweise nicht mehr diese Klassen verwenden möchten, da sie nicht in den 'Kompakten Profilen' vorhanden sein werden.

Answer 4

Was ist damit?

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

/**
  * @author ycoppel@google.com (Yohann Coppel)
  * 
  * @param 
  *          Objekttyp im Baum.
*/
public class Tree {

  private T head;

  private ArrayList> leafs = new ArrayList>();

  private Tree parent = null;

  private HashMap> locate = new HashMap>();

  public Tree(T head) {
    this.head = head;
    locate.put(head, this);
  }

  public void addLeaf(T root, T leaf) {
    if (locate.containsKey(root)) {
      locate.get(root).addLeaf(leaf);
    } else {
      addLeaf(root).addLeaf(leaf);
    }
  }

  public Tree addLeaf(T leaf) {
    Tree t = new Tree(leaf);
    leafs.add(t);
    t.parent = this;
    t.locate = this.locate;
    locate.put(leaf, t);
    return t;
  }

  public Tree setAsParent(T parentRoot) {
    Tree t = new Tree(parentRoot);
    t.leafs.add(this);
    this.parent = t;
    t.locate = this.locate;
    t.locate.put(head, this);
    t.locate.put(parentRoot, t);
    return t;
  }

  public T getHead() {
    return head;
  }

  public Tree getTree(T element) {
    return locate.get(element);
  }

  public Tree getParent() {
    return parent;
  }

  public Collection getSuccessors(T root) {
    Collection successors = new ArrayList();
    Tree tree = getTree(root);
    if (null != tree) {
      for (Tree leaf : tree.leafs) {
        successors.add(leaf.head);
      }
    }
    return successors;
  }

  public Collection> getSubTrees() {
    return leafs;
  }

  public static  Collection getSuccessors(T of, Collection> in) {
    for (Tree tree : in) {
      if (tree.locate.containsKey(of)) {
        return tree.getSuccessors(of);
      }
    }
    return new ArrayList();
  }

  @Override
  public String toString() {
    return printTree(0);
  }

  private static final int indent = 2;

  private String printTree(int increment) {
    String s = "";
    String inc = "";
    for (int i = 0; i < increment; ++i) {
      inc = inc + " ";
    }
    s = inc + head;
    for (Tree child : leafs) {
      s += "\n" + child.printTree(increment + indent);
    }
    return s;
  }
}

Answer 5

Ich habe eine kleine Bibliothek geschrieben, die generische Bäume handhabt. Sie ist viel leichter als das Swing-Zeug. Ich habe auch ein Maven-Projekt dafür.