Binärbaum/Implementierung

[Nirvana]

Hallo, also wir hatten in Vorlesung kurz Binärbäume.
Die Theorie habe ich intus aber die Implementierung bereitet Probleme.
Ich will selbst eine Klasse für eien Binärbaum entwickeln. Jeweils methoden schreiben für die tiefe, größe eine knotens sowie höhe eines baumes. Bis es aber zu dem kommt muss ich mal das Grundgerüst haben.


Zuerst habe ich Klasse Knoten mithilfe der Generizität formuliert mit Typparameter T:

public class Knoten<T> {

    public Knoten<T> links;
    public Knoten<T> rechts;
    public T inhalt;

    public Knoten(T elem){
        inhalt = elem;
        links = null;
        rechts = null;
    }
    public Knoten(T elem, Knoten<T> links, Knoten<T> rechts){
        inhalt = elem;
        this.links = links;
        this.rechts = rechts;
    }
}

Nun Klasse BinaerBaum erstellt:

public class BinaerBaum<T>  {
    public Knoten<T> wurzel;
    public Binaerbaum(){
   
    }
    public Binaerbaum(Knoten<T> wurzel){
        this.wurzel = wurzel;
    }
}

Nun kommt der Fehler bei Klasse BinaerBaum, zeile 3 und 6: invalid Method declaration.
Aber was gebe ich als Rückgabewert an=?

 

[Gonzo17]

Das ist case senstitive, also schreib BinearBaum und dann sollte es klappen. Sollen ja Konstruktoren sein, aber deine IDE denkt es wären Methoden wegen der unterschiedlichen Schreibweise und daher fehlt der Rückgabewert.

 

[PatrickO]

Hallo,

schau mal hier built up an binary search tree | Das JAVA-Hilfe Blog
vorbei, da gibts eine komplette Implementierung samt Methoden zur Traversierung des Baumes.

Gruß Patrick

 

[Nirvana]

Hallo

Danke Gonzo17.
Um weiterarbeiten zu können(Methoden für Größe,Tiefe,Höhe), welche Methoden muss ich dafür vorher noch implementieren?
Ich bin noch ziemlicher Anfänger und mir wäre geholfen wenn ich wüsste was ich mir nun als nächtes für Gedanken machen sollte.

LG

 

[buzz!dev]

Um mit dem Baum sinnvoll arbeiten zu können, sollte er die folgenden Methoden haben:

public T getRoot();
public BinaerBaum<T> getLeft();
public BinaerBaum<T> getRight();
public boolean isEmpty();

@PatrickO: Binärbaum und binärer Suchbaum sind nicht das gleiche.

 

[PatrickO]

Sorry, da hab ich wohl einfach zu schnell gelesen 😉 Verspreche Besserung!

 

[Nirvana]

Ich krieg das leider nicht ganz hin. Internetrecherche bringt mich auch nur auch die Suchbäume.

buzz!dev, vlt könntest du mir das bei einer Methode zeigen.
Hast du absichtlich nie einen Parameter in die Methoden verwendet?

public T getRoot(Binaerbaum<T>);{
return wurzel
}

soll die Wurzel des Binärbaums ausgeben. Ist also der Parameter der BinaerBaum?

public BinaerBaum<T> getLeft(Knoten<T>);

public BinaerBaum<T> getRight(Knoten<T>)

Hier sind die Parameter die Knoten. Aber wie soll in den Inhalt des rechten/linken Knotens ausgeben?

 

[hüteüberhüte]

Hier sind die Parameter die Knoten. Aber wie soll in den Inhalt des rechten/linken Knotens ausgeben?

Eigentlich rufst du auf dem jeweiligen Knoten getLeft/getRight auf. Für den Inhalt gibt's wieder 'ne extra Methode.

Vor allem interessant ist die Traversierung ( Binärbaum ? Wikipedia ):

• pre-order (auch depth-first) oder Hauptreihenfolge (auch Tiefensuche) (W–L–R): Zuerst wird die Wurzel (W) betrachtet und anschließend der linke (L), schließlich der rechte (R) Teilbaum durchlaufen.
• post-order oder Nebenreihenfolge (L–R–W): Zuerst wird der linke (L), dann der rechte (R) Teilbaum durchlaufen und schließlich die Wurzel (W) betrachtet.
• in-order oder symmetrische Reihenfolge (L–W–R): Zuerst wird der linke (L) Teilbaum durchlaufen, dann die Wurzel (W) betrachtet und schließlich der rechte (R) Teilbaum durchlaufen.
• reverse in-order oder anti-symmetrische Reihenfolge (R–W–L): Zuerst wird der rechte (R) Teilbaum durchlaufen, dann die Wurzel (W) betrachtet und schließlich der linke (L) Teilbaum durchlaufen.
• level-order (auch breadth-first, deutsch Breitensuche): Beginnend bei der Baumwurzel werden die Ebenen von links nach rechts durchlaufen.

public class Node<T> {
    public T value; // eigentlich private
    public Node<T> left;
    public Node<T> right;

    public Node(T value, Node<T> left, Node<T> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

public abstract class AbstractTraverser<T> {
    public void inOrder(Node<T> node) {
        if (node != null) {
            inOrder(node.left);
            toDo(node);
            inOrder(node.right);
        }
    }

    public abstract void toDo(Node<T> node);
}

public class Main {
    public static void main(String[] args) {
        Node<String> node = new Node<String>("vier",
                new Node<String>("zwei",
                new Node<String>("eins", null, null),
                new Node<String>("drei", null, null)),
                new Node<String>("sechs",
                new Node<String>("fünf", null, null),
                new Node<String>("sieben", null, null)));
        new AbstractTraverser<String>() {

            @Override
            public void toDo(Node<String> node) {
                System.out.println(node.value);
            }
        }.inOrder(node);
    }
}

eins
zwei
drei
vier
fünf
sechs
sieben

🙂

 

[Nirvana]

Danke für den Post..
Könntest du mir die Klasse public abstract class AbstractTraverser<T> erklären? Ich verstehe nicht was sie bzw. ihre methoden machen.

Wohin ist meine Klasse verschwunden mit der die Wurzelgesetzt wird?
LG

 

[hüteüberhüte]

Könntest du mir die Klasse public abstract class AbstractTraverser<T> erklären? Ich verstehe nicht was sie bzw. ihre methoden machen.

Darin könntest du Methoden wie

    public void inOrder(Node<T> node) {
        if (node != null) {
            inOrder(node.left);
            toDo(node);
            inOrder(node.right);
        }
    }

    public void preOrder(Node<T> node) {
    }

    public void postOrder(Node<T> node) {
    }

    public void breadthFirst(Node<T> node) {
    }

unterbringen. Die Methoden durchschreiten (Traverser=der Durchquerer) beginnend bei einem Knoten den Baum. Was mit den einzelnen Knoten geschehen soll, ist implementierungsabhängig

Wohin ist meine Klasse verschwunden mit der die Wurzelgesetzt wird?

Wurzel-Knoten und richtiges Einfügen ist wieder so eine Sache. Soll der Baum geordnet sein, soll er höhenbalanciert sein, sollen Elemente zufällig eingefügt werden usw. Das musst du dir vorher überlegen, dann in eine extra Klasse schreiben

Beispielsweise:

public class Tree<T> {

    private Node<T> root;

    public Node<T> getRoot() {
        return root;
    }

    public void insert(T t) {
        if (root == null) {
            root = new Node<T>(t, null, null);
        } else {
            ins(root, t);
        }
    }

    private void ins(Node<T> n, T t) {
        if (Math.random() < 0.5) {
            if (n.left == null) {
                n.left = new Node<T>(t, null, null);
            } else if (n.right == null) {
                n.right = new Node<T>(t, null, null);
            } else {
                ins(n.left, t);
            }
        } else {
            if (n.right == null) {
                n.right = new Node<T>(t, null, null);
            } else if (n.left == null) {
                n.left = new Node<T>(t, null, null);
            } else {
                ins(n.right, t);
            }
        }
    }
}

Es gibt auch einen Beweis, dass ein zufällig erstellter Baum nicht in der Höhe "ausufert" 🙂

Über ein Danke würd ich mich auch mal freuen