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

Benutzerdefinierte Baumimplementierung des Baums ohne Verwendung des Collection-Frameworks. Es enthält verschiedene grundlegende Operationen, die für die Implementierung eines Baums benötigt werden.

class Node {

    int data;
    Node left;
    Node right;

    public Node(int ddata, Node left, Node right) {
        this.data = ddata;
        this.left = null;
        this.right = null;      
    }

    public void displayNode(Node n) {
        System.out.print(n.data + " "); 
    }

}

class BinaryTree {

    Node root;

    public BinaryTree() {
        this.root = null;
    }

    public void insertLeft(int parent, int leftvalue ) {
        Node n = find(root, parent);
        Node leftchild = new Node(leftvalue, null, null);
        n.left = leftchild;
    }

    public void insertRight(int parent, int rightvalue) {
        Node n = find(root, parent);
        Node rightchild = new Node(rightvalue, null, null);
        n.right = rightchild;
    }

    public void insertRoot(int data) {
        root = new Node(data, null, null);
    }

    public Node getRoot() {
        return root;
    }

    public Node find(Node n, int key) {     
        Node result = null;

        if (n == null)
            return null;

        if (n.data == key)
            return n;

        if (n.left != null)
            result = find(n.left, key);

        if (result == null)
            result = find(n.right, key);

        return result;
    } 

    public int getheight(Node root){
        if (root == null)
            return 0;

        return Math.max(getheight(root.left), getheight(root.right)) + 1; 
    }

    public void printTree(Node n) {     
        if (n == null)
            return;

        printTree(n.left);
        n.displayNode(n);
        printTree(n.right);             
    }

}