Binärer Suchbaum

Keros918

Mitglied
Hallo ich bräuchte Hilfe beim schreiben einer objektmethode, die überprüft ob eine Zahl im Binären Suchbaum vorhanden ist.
Java:
package verkettete_objekte;

public class Knoten {
    public int x;
    public Knoten links;
    public Knoten rechts;
   
    public Knoten(int wert) {
        x = wert;
        links = null;
        rechts = null;
        System.out.println("Ein neuer Knoten mit dem Wert " + x + " wurde erschaffen");
    }

   
    public void einfuegen (int wert) {
        if (wert != x) {
            if (wert < x && links == null) {
                links = new Knoten(wert);
            } else if(wert < x) {
                links.einfuegen(wert);
            }
            if (wert > x && rechts == null) {
                rechts = new Knoten(wert);
            } else if(wert > x){
                rechts.einfuegen(wert);
            }
        } else {
            System.out.println("Der Teilbaum kann nicht erschaffen werden.");
        }
    }
   
    public String toString() {
        String s_links = "";
        String s_rechts = "";
        if (links != null) {
            s_links = links.toString();
        }
        if (rechts != null) {
            s_rechts = rechts.toString();
        }
        String baum = "(" + s_links + x + s_rechts + ")";
        return baum;
    }
   
    public boolean suchen(int suche) {
        boolean enthält = false;
        System.out.println(x);
        if (x == suche) {
            enthält = true;
        }
        if (x < suche) {
            rechts.suchen(suche);
        }
        if (x > suche) {
            links.suchen(suche);
        }
        return enthält;
    }
}

Das ist soweit mal das was ich habe und mein Problem ist die Methode "suchen", da sie immer False zurückgibt. Mir ist auch klar warum, nur ist mir nicht klar wie ich das Problem beheben kann. Ich hoffe hier kann mir jemand helfen.


[CODE lang="java" title="TesterKlasse:"]public class KnotenTester {
public static void main(String[] args) {
int neu = 1;
Knoten wurzel = new Knoten(9);
wurzel.einfuegen(8);
wurzel.einfuegen(7);
wurzel.einfuegen(6);
wurzel.einfuegen(5);
wurzel.einfuegen(4);
wurzel.einfuegen(3);
wurzel.einfuegen(2);
wurzel.einfuegen(1);
System.out.println(wurzel.toString());
if (wurzel.suchen(neu) == true) {
System.out.println("Das Element ist enthalten.");
} else {
System.out.println("Das Element ist nicht enthalten.");
}
}
}[/CODE]
 
Zuletzt bearbeitet:

mihe7

Top Contributor
Mir ist auch klar warum, nur ist mir nicht klar wie ich das Problem beheben kann. Ich hoffe hier kann mir jemand helfen.
In Deiner suchen-Methode ist enthält eine lokale Variable. Für jeden Methodenaufruf gibt es eine eigene lokale Variable enthält. Wenn Du also z. B. rechts.suchen() aufrufst und in dem Aufruf true zurückegeben wird, ändert das an der lokalen Variable nichts. Am Ende gibst Du einfach false zurück.
 

mihe7

Top Contributor
Noch zur Verdeutlichung: Du kannst den rekursiven Aufruf bzgl. der lokalen Variable schlicht ignorieren. Der Code verhält sich also wie:
Java:
    public boolean suchen(int suche) {
        boolean enthält = false;
        System.out.println(x);
        if (x == suche) {
            enthält = true;
        }
        if (x < suche) {
            tuIrgendwas();
        }
        if (x > suche) {
            tuIrgendwas();
        }
        return enthält;
    }
Wenn x != suche ist, dann ändert sich enthält nicht und dem entsprechend gibst Du false zurück.
 

Keros918

Mitglied
Noch zur Verdeutlichung: Du kannst den rekursiven Aufruf bzgl. der lokalen Variable schlicht ignorieren. Der Code verhält sich also wie:
Java:
    public boolean suchen(int suche) {
        boolean enthält = false;
        System.out.println(x);
        if (x == suche) {
            enthält = true;
        }
        if (x < suche) {
            tuIrgendwas();
        }
        if (x > suche) {
            tuIrgendwas();
        }
        return enthält;
    }
Wenn x != suche ist, dann ändert sich enthält nicht und dem entsprechend gibst Du false zurück.
Danke schonmal, hab das jetzt mit einer statischen Variable versucht und es hat funktioniert.
 

Keros918

Mitglied
Noch zur Verdeutlichung: Du kannst den rekursiven Aufruf bzgl. der lokalen Variable schlicht ignorieren. Der Code verhält sich also wie:
Java:
    public boolean suchen(int suche) {
        boolean enthält = false;
        System.out.println(x);
        if (x == suche) {
            enthält = true;
        }
        if (x < suche) {
            tuIrgendwas();
        }
        if (x > suche) {
            tuIrgendwas();
        }
        return enthält;
    }
Wenn x != suche ist, dann ändert sich enthält nicht und dem entsprechend gibst Du false zurück.
Danke schonmal, hab das jetzt mit einer statischen Variable versucht und es hat funktioniert.
 

mihe7

Top Contributor

Keros918

Mitglied
Neiiiiiin: statische Variablen nur für Konstanten verwenden.


Natürlich. Du bräuchtest ja nur enthält entsprechend zu setzen (überleg mal, wo das sinnvoll gemacht werden kann).
Ok habs jetzt richtig geschafft.

Java:
public boolean suchen(int suche) {
        boolean enthält = false;
        if (x == suche) {
            enthält = true;
        }
        if (x < suche && rechts != null) {
            rechts.suchen(suche);
            if (rechts.suchen(suche) == true) {
                    enthält = true;
            }
        }
        if (x > suche && links != null) {
            links.suchen(suche);
            if (links.suchen(suche) == true) {
                    enthält = true;
            }
        }
        return enthält;
    }
}

Vielen Dank für die Hilfe :)
 
K

kneitzel

Gast
Das sind jetzt aber nur "kosmetische" Verbesserungen, wenn ich das richtig sehe oder?
Nein nicht nur. Bei folgendem Konstrukt:
Java:
            links.suchen(suche);
            if (links.suchen(suche) == true) {
                    enthält = true;
Ist die erste Zeile unnötig. Du suchst links aber das Ergebnis interessiert Dich nicht. Daher suchst Du dann innerhalb der if Bedingung gleich erneut.

Was das if mit dem true angeht: Da könnte man von einer kosmetischen Änderung sprechen. Aber im Rahmen von Clean Code wäre es schon besser, da der Code kürzer und auch leichter lesbar wird.
 

Keros918

Mitglied
Nein nicht nur. Bei folgendem Konstrukt:
Java:
            links.suchen(suche);
            if (links.suchen(suche) == true) {
                    enthält = true;
Ist die erste Zeile unnötig. Du suchst links aber das Ergebnis interessiert Dich nicht. Daher suchst Du dann innerhalb der if Bedingung gleich erneut.

Was das if mit dem true angeht: Da könnte man von einer kosmetischen Änderung sprechen. Aber im Rahmen von Clean Code wäre es schon besser, da der Code kürzer und auch leichter lesbar wird.
Alles klar, vielen Dank euch nochmal :)
 

Neue Themen


Oben