# BinärBaum in Java



## Alexander910681 (24. Jan 2016)

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 (24. Jan 2016)

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 (24. Jan 2016)

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 (24. Jan 2016)

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 (24. Jan 2016)

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 (24. Jan 2016)

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 (24. Jan 2016)

Alexander910681 hat gesagt.:


> 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 (25. Jan 2016)

```
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 (25. Jan 2016)

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


----------



## kneitzel (25. Jan 2016)

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 (25. Jan 2016)

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 (25. Jan 2016)

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 (25. Jan 2016)

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 (25. Jan 2016)

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.


----------

