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

Sie können die HashTree -Klasse verwenden, die in Apache JMeter enthalten ist und Teil des Jakarta-Projekts ist.

Die HashTree-Klasse ist im Paket org.apache.jorphan.collections enthalten. Obwohl dieses Paket außerhalb des JMeter-Projekts nicht veröffentlicht wird, können Sie es leicht erhalten:

1) Laden Sie die JMeter-Quellen herunter.

2) Erstellen Sie ein neues Paket.

3) Kopieren Sie die Dateien unter /src/jorphan/org/apache/jorphan/collections/ . Alle Dateien außer Data.java

4) Kopieren Sie auch /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree ist bereit zur Verwendung.

Answer 2

Bitte überprüfen Sie den untenstehenden Code, in dem ich Baumdatenstrukturen verwendet habe, ohne Collection-Klassen zu verwenden. Der Code kann Fehler/Verbesserungen enthalten, aber verwenden Sie ihn bitte nur als Referenz.

package com.datastructure.tree;

public class BinaryTreeWithoutRecursion  {

    private TreeNode root;

    public BinaryTreeWithoutRecursion (){
        root = null;
    }

    public void insert(T data){
        root =insert(root, data);

    }

    public TreeNode  insert(TreeNode node, T data ){

        TreeNode newNode = new TreeNode<>();
        newNode.data = data;
        newNode.right = newNode.left = null;

        if(node==null){
            node = newNode;
            return node;
        }
        Queue> queue = new Queue>();
        queue.enque(node);
        while(!queue.isEmpty()){

            TreeNode temp= queue.deque();
            if(temp.left!=null){
                queue.enque(temp.left);
            }else
            {
                temp.left = newNode;

                queue =null;
                return node;
            }
            if(temp.right!=null){
                queue.enque(temp.right);
            }else
            {
                temp.right = newNode;
                queue =null;
                return node;
            }
        }
        queue=null;
        return node; 

    }

    public void inOrderPrint(TreeNode root){
        if(root!=null){

            inOrderPrint(root.left);
            System.out.println(root.data);
            inOrderPrint(root.right);
        }

    }

    public void postOrderPrint(TreeNode root){
        if(root!=null){

            postOrderPrint(root.left);

            postOrderPrint(root.right);
            System.out.println(root.data);
        }

    }

    public void preOrderPrint(){
        preOrderPrint(root);
    }

    public void inOrderPrint(){
        inOrderPrint(root);
    }

    public void postOrderPrint(){
        inOrderPrint(root);
    }

    public void preOrderPrint(TreeNode root){
        if(root!=null){
            System.out.println(root.data);
            preOrderPrint(root.left);
            preOrderPrint(root.right);
        }

    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BinaryTreeWithoutRecursion  ls=  new BinaryTreeWithoutRecursion <>();
        ls.insert(1);
        ls.insert(2);
        ls.insert(3);
        ls.insert(4);
        ls.insert(5);
        ls.insert(6);
        ls.insert(7);
        //ls.preOrderPrint();
        ls.inOrderPrint();
        //ls.postOrderPrint();

    }

}

Answer 3

Sie können die TreeSet-Klasse in java.util.* verwenden. Sie funktioniert wie ein Binärbaum, daher ist sie bereits sortiert. Die TreeSet-Klasse implementiert die Iterable, Collection und Set-Schnittstellen. Sie können den Baum mit einem Iterator durchlaufen wie bei einem Set.

TreeSet treeSet = new TreeSet();
Iterator it  = treeSet.Iterator();
while(it.hasNext()){
...
}

Sie können die Java-Dokumentation und einige weitere überprüfen.

Answer 4

import java.util.Collection;
import java.util.LinkedList;
import java.util.function.BiConsumer;
import java.util.function.Function;

/**
 * @author changjin wei()
 * @since 2021/7/15
 */
public class TreeUtils {

    private TreeUtils() {
    }

    /**
     * @param collection dies ist eine Sammlung von Elementen
     * @param getId dies ist eine getId Funktion
     * @param getParentId dies ist eine getParentId Funktion
     * @param setNode dies ist eine setNode BiConsumer
     * @param  der Typ der Elemente in dieser Sammlung
     * @param  der Typ des Ergebnisses der Funktion
     *
     * @return Collection
     */
    public static  Collection tree(Collection collection, Function getId, Function getParentId, BiConsumer> setNode) {
        Collection root = new LinkedList<>();
        for (E node : collection) {
            R parentId = getParentId.apply(node);
            R id = getId.apply(node);
            Collection elements = new LinkedList<>();
            boolean isParent = true;
            for (E element : collection) {
                if (id.equals(getParentId.apply(element))) {
                    elements.add(element);
                }
                if (isParent && getId.apply(element).equals(parentId)) {
                    isParent = false;
                }
            }
            if (isParent) {
                root.add(node);
            }
            setNode.accept(node, elements);
        }
        return root;
    }
}

Answer 5

Einfaches Beispiel:

public class ArbrePlaner {

public static void main(String[] args) {
    ArbrePlaner ll = new ArbrePlaner();

    ll.add(1,"A");
    ll.add(2,"B");
    ll.add(1,"C");
    ll.add(3,"D");
    ll.add(1,"Z");

    for(int i = 0; i < ll.size; i++){
    //  System.out.println(ll.isIdExist(i));
        System.out.println("-----------------");
        System.out.println(ll.getIdAt(i)+" :");
        linkedList lst = ll.getListDataById(ll.getIdAt(i));
        for(int j = 0; j < lst.size; j++){
            System.out.println(lst.getElementAt(j));
        }
    }
}

private int size;
private Noeud root;

public Noeud add(long Id, Object data){
    if(isIdExist(Id)){
        Noeud nd = getNoeudId(Id);
        nd.add(data);
        return nd;
    }else{
        Noeud nd = new Noeud(Id, data, this.root);
        this.root = nd;
        this.size++;
        return nd;
    }
}

 public Object getDataById(long Id, int x){
        Noeud thisNode = this.root;
        while(thisNode!=null){
            if(thisNode.getId() == Id){
                return thisNode.getLl().getElementAt(x);
            }
            thisNode = thisNode.getNextNoeud();
        }
        return null;
    }

 public long getIdAt(int x){
        if(size >= x){
            Noeud nd = this.root;
            for(int i = 0; i