BinärBaum in Java

[Alexander910681]

Hallo, ich hoffe mir kann hier jemand helfen mit meiner Aufgabe.
Gegeben ist folgende Klassenstruktur eines Binärbaums:

public class Knoten{
             private int wert;
             private Knoten teilbaumLinks;
             private Knoten teilbaumRechts;

             public int getWert() {
                   return wert;
             }

             public Knoten getKnotenLinks() {
                    return teilbaumLinks;
             }

             public Knoten getKnotenRechts() {
                     return teilbaumRechts;
              }
              // …
}

public class Baum {
            private Knoten wurzel;

            public boolean istTeilbaumKleiner(Knoten k, int wert) {
                   //rekursiv prüfen, ob alle Werte in einem Teilbaum kleiner dem Vergleichswert sind.
             }

            public boolean istTeilbaumGroesser(Knoten k, int wert) {
                   //rekursiv prüfen, ob alle Werte in einem Teilbaum größer dem Vergleichswert sind.
            }

            public boolean istSuchbaum() {
                      return istSuchbaum(wurzel);
            }

            public boolean istSuchbaum(Knoten k) {
                    // TODO
            }
           // …
}

Leider weiß ich nicht wie ich die Aufgabe lösen soll. Ich wäre für Ideen und Ansätze dankbar. Ich ergänze nacher nochmal meine ideen und ein paar sachen zu Binärbäumen und suchbäumen.

 

[Alexander910681]

Fortsetzung/Ergänzung:

Die Methode istSuchbaum() soll prüfen, ob der Binärbaum die Suchbaumeigenschaft erfüllt, also ob alle linken Teilbäume kleiner und alle rechten Teilbäume größer als der Elternknoten sind. Dafür braucht man sicher die beiden Methoden istTeilBaumKleiner/Größer. Daher erst zu diesen beiden.

Ich stelle mir die Methoden istTeilbaumKleiner/Größer ungefähr so vor:

public boolean istTeilbaumGroesser(Knoten k, int wert){
                   if(k.getWert()>wert){
                             return true;
                   }
}

Aber daran ist noch nichts rekrusiv, daher die Frage ist das wohl so richtig gedacht?

 

[kneitzel]

Das kannst Du Dir ja doch selbst überlegen. Mal Dir einen großen Baum auf und schau, was getestet wird. Du prüfst ja jetzt nur einen Unterknoten. Der kann aber doch auch noch mehr Unterknoten haben und die müssen alle geprüft werden.

 

[Alexander910681]

Das ist das Problem, ich denke lösen würde ich das mir einer while Schleife, die solange läuft wie k.getKnotenLinks bzw. Rechts != null ist. Dann würde ich jedesmal k.getWert prüfen und je nach dem true oder false liefern. Nur ist das nicht Rekrusiv. Ich kriege die Rekrusion einfach nicht ins Spiel.

 

[Bitfehler]

Mir fallen spontan dazu die Begriffe preOrder, postOrder und inOrder ein.
Dabei handelt es sich um ein Verfahren, mit dem man rekursiv durch Bäume laufen kann. Wenn du diese Begriffe nachliest, kommst du sicher ein Stück weiter.

 

[Alexander910681]

Die Traversierungsmethoden habe ich mittlerweile schon eingebaut für die Ausgabe. Beispielsweise

   // Pre-Order
    public String traversierePreOrder() {
        return traversierePreOrder(wurzel);
    }

    private String traversierePreOrder(Knoten einKnoten) {
        if (einKnoten == null) {
            return "";
        } else {
            return einKnoten.getDaten() + traversierePreOrder(einKnoten.getKnotenLinks())
                    + traversierePreOrder(einKnoten.getKnotenRechts());
        }
    }

Ich wusste nicht das ich sie auch hier verwenden muss. Wie das genau funktioniert ist mir klar, ich hab sie auf Papier geprüft. Die Kurve zur aktuellen Aufgabe krieg ich aber noch nicht. Ich müsste ja irgendwie bei jedem Schritt der Traversierung die Prüfung einbauen, ob der jeweilige Teilbaum kleiner oder größer wert ist.

 

[Bitfehler]

Ich müsste ja irgendwie bei jedem Schritt der Traversierung die Prüfung einbauen, ob der jeweilige Teilbaum kleiner oder größer wert ist.

Ja, du musst noch eine Prüfung einbauen.
Nein, du prüfst nicht den Teilbaum im dem Vergleich, sondern den aktuellen Knoten. Sind alle Knoten kleiner oder größer als dein Vergleichswert ist alles gut und du gibst true zurück, sonst false.

 

[Alexander910681]

public boolean istTeilbaumKleiner(Knoten k, int wert) {
        if (k.getDaten() < wert){
            if (k.getKnotenLinks() != null)
                istTeilbaumKleiner(k.getKnotenLinks(), wert);
            if (k.getKnotenRechts() != null)
                istTeilbaumKleiner(k.getKnotenRechts(), wert);
        }else{
            return false;
        }
        return true;
    }

So sieht meine Methode jetzt aus. Um die Methode testen zu können benötige ich, wenn ich das richtig verstehe, ja die Methode istSuchbaum, die die Methoden istTeilbaumKleiner und Größer nutzt. Wie würde die aussehen? Einfach eine Prüfung ob istTeilbaumKleiner && istTeilbaumGrößer true liefern?

 

[Joose]

@Alexander910681 bitte verwende für deinen Code die entsprechenden Code/Java-Tags, danke!
[java] /* dein code hier */ [/java]

 

[kneitzel]

Also um die Methode istTeilbaumKleiner testen zu können brauchst Du istSuchbaum? Wie kommst Du auf diese Idee? Die Funktion istSuchbaum wird ja nicht benutzt. Was spricht dagegen, einfach irgendwelche Bäume zu erstellen um dann die Funktion zu testen?

Und meine Empfehlung: Übe doch bitte, Dir vorzustellen, was da genau passiert. Am Anfang mit Hilfe von Stift und Papier. Mal Dir ein paar Bäume auf und überleg Dir, was denn da genau passiert bzw. was passieren soll. So kommst Du direkt auf eine Lösung hoffe ich mal. Und ja - die Nutzung von den vorhandenen Funktionen innerhalb der istSuchbaum Funktion ist durchaus denkbar, aber ich würde diese nicht verwenden. Aber den Nachteil wirst Du hoffentlich selbst finden und dann ggf. auch eine eigene, bessere Lösung finden.

Konrad

 

[Alexander910681]

Auf dem Papier ist die Sache klar, das ganze rekrusiv zu programmieren ist mein Problem.
Ich hab die Methode überarbeitet und sie anhand meines Baumprogramms getestet. Allerdings passt die Ausgabe einfach nicht, zum Beispiel gibt die Methode für den Vergleichswert 11 (und größer) true zurück, obwohl sich im Baum mehrere Elemente befinden, die größer als 11 sind. Beim Aufruf gebe ich ihr den Wurzelknoten und den Vergleichswert mit.

    public boolean istTeilbaumKleiner(Knoten k, int n) {
        if (k.getDaten() >= n){
            return false;
        }
        if (k.getKnotenRechts() != null) {
            istkleiner = true;
            istTeilbaumKleiner(k.getKnotenRechts(), n);
        }
        if (k.getKnotenLinks() != null) {
            istkleiner = true;
            istTeilbaumKleiner(k.getKnotenLinks(), n);
        }
        return istkleiner;
    }

Ich weiß nicht wo da der Denkfehler ist. Es scheint als würde die Methode den Baum nicht komplett durchlaufen.

 

[kneitzel]

Du rufst die istTeilbaumKleiner Funktion rekursiv auf aber ignorierst den Rückgabewert. Ich sehe auch keine Definition von der Variablen istkleiner.

Was muss den gemacht werden?
- Wenn Daten >= ist, dann false zurückgeben. Hast Du schön eingebaut.
- Die "gleiche Logik" kann doch für den rechten und linken Knoten verwendet werden, oder?
- Und wenn die ganzen Prüfungen erfolgreich absolviert wurden: true zurückgeben.

Konrad

 

[Alexander910681]

Danke, die ersten beiden Methoden funktionieren jetzt wie sie sollen:

    public boolean istTeilbaumKleiner(Knoten k, int n) {
        if (k.getDaten() >= n){
            return false;
        }else{
            if (k.getKnotenRechts() != null) {
                return istTeilbaumKleiner(k.getKnotenRechts(), n);
            }
            if (k.getKnotenLinks() != null) {
                return istTeilbaumKleiner(k.getKnotenLinks(), n);
            }
            return true;
        }
    }

So komme ich nun zur Methode istSuchbaum. Diese soll ja prüfen, ob jeder Knoten die Suchbaumeigenschaft erfüllt, also ob die Daten im linken Teilbaum kleiner und die im rechten Teilbaum größer als der Elternknoten sind.
Mein erster Ansatz sieht dabei so aus:

    public boolean istSuchbaum(Knoten k) {
        if (k.getDaten() > k.getKnotenLinks().getDaten() && k.getDaten() < k.getKnotenRechts().getDaten()){
            if (k.getKnotenLinks() != null) {
                return istSuchbaum(k.getKnotenLinks());
            }
            if (k.getKnotenRechts() != null) {
                return istSuchbaum(k.getKnotenRechts());
            }
            return true;
        }else{
            return false;
        }
    }

Dabei wirft er mir eine NullPointerException. Die Frage is wie verhinder ich das.

 

[kneitzel]

Du musst natürlich sicher gehen, dass die Unterbäume existieren ... Also du prüfst nur dann links, wenn das nicht Null ist. Ebenso Rechts.