Algorithmus zur Überprüfung eines binären Suchbaums

[tekevic]

Hallo,

ich würde gerne einen Algorithmus schreiben , welcher überprüfen soll , ob ein binärer Baum ein Suchbaum ist.
Die Eigenschaften eines binären Suchbaums sind:
Das linke Kind ist immer kleiner als der Elternknoten und das rechte Kind immer größer.
Und zwar müsste ich doch jeden Schlüssel im Baum untersuchen und schauen ob dieser größer oder kleiner ist als der Elternknoten, wenn dies der Fall ist, dann ist mein Baum ein binärer Suchbaum.
Leider habe ich Schwierigkeiten , die Schlüssel des Baums zu überprüfen. Ich habe folgenden Ansatz:

if(root != null){
     parent = root;
    
     if(parent.links < parent){
         parent = parent.links;
         if(parent.rechts> parent){
             parent = parent.rechts;
         }
    } else{
      System.out.println("Baum ist kein binärer Suchbaum");
     }
     if(parent.rechts > parent){
        parent = parent.rechts;
        if(parent.rechts > parent){
           parent = parent.rechts;
        }
     }else{
       System.out.println("Baum ist kein binärer Suchbaum");
     }

Ich weiß , dass mein Ansatz falsch ist , aber da ich neu in der Programmierung bin , hoffe ich dass ihr ein wenig Verständnis habt.

 

[Flown]

Sieh dir mal an, wie man einen Baum traversiert: HIER.
Du musst jeden Knoten mit den Kindsknoten überprüfen, was wiederum rekursiv (aber auch iterativ möglich) geschieht.

 

[Elenteria]

Das schöne an Binärbäumen ist ja das man sie so schön rekusiv durchlaufen kann weil jedes Kind eines Knoten entweder ein weiterer Baum oder ein Blatt ist.
Entsprechend musst du Prüfen:

isSuchbaum(knoten) {
IF istBlatt(knoten)
THEN
  return true
ELSE
   retrun links < knoten && rechts > knoten &&  isSuchbaum(links) && isSuchbaum(rechts)
}