Rekursion Binärbaum

[LatinFavourite]

Hallo,

ich beschäftige mich gerade mit Binären Suchbäumen und versuche die entsprechendem Methoden rekursiv zu implementieren. Ich stelle mir aber gerade die Frage, wie es funktioniert, da scheinbar keine return verwendet wird. Warum benötige ich keine return Anweisung? Wird doch ansonsten bei Rekursionen verwendet. Für eine Erklärung wäre ich sehr dankbar.

Mit freundliche Grüßen
LatinFavourite

 

[Flown]

Wie lautet die Aufgabenstellung oder Programmrumpf?

 

[LatinFavourite]

Es gibt keine Aufgabenstellung. Habe den Binärbaum bis jetzt iterativ implementiert und wollte dies nun rekursiv vornehmen. Habe mir den Wikipedia Artikel zu dem Thema durchgelesen und scheibar wird hier auf ein return verzichtet, was ich nicht verstehe. Zur Ausgabe der Knoten wird, wenn vorhanden der linke Knoten ausgegeben. Ich komme aber nicht dahinter, wie man dann wieder an den entsprechende Vater gelangt und nun den rechten Knoten auswählt. Die Methode wird zwar erneut aufgerufen, jedoch ohne return. Ich bin einfach verwirrt.

 

[stg]

Sprichst du von der Traversierung oder wvon redest du denn überhaupt? Hier weiß keiner, was du genau gelesen und dabei nicht verstanden hast. Post doch einfach den betreffenden Code-Ausschnitt und stelle konkrete Fragen dazu.

 

[LatinFavourite]

Ganz genau, darauf beziehe ich mich. Beispielsweise das Wikipedia Beispiel.

preOrder( knoten ) {

// Führe die gewünschten Aktionen am Knoten aus, z.B.:
print( knoten );

if ( knoten.links ≠ null )
preOrder( knoten.links ); // rekursiver Aufruf

if ( knoten.rechts ≠ null )
preOrder( knoten.rechts );
}

Warum wird kein return bei Aufruf von preOrder() benötigt? Wie gelangt man dann wieder nach Abarbeiten des linken Knoten zum Vater, um rechts fortzufahren?

 

[stg]

Du gibst nur die Knoten aus, da interessiert ein Rückgabewert doch niemanden. Was willst du denn damit machen?

Wenn der erste if-Block fertig abgearbeitet ist, dann geht's ganz normal mit dem zweiten weiter.

Interessant ist hier eigentlich nur, wo du die Ausgabe genau platzierst. Führe doch einfach mal alle drei Varianten aus, dann solltest du eigentlich ziemlich genau sehen, was da passiert.

 

[LatinFavourite]

Schon einmal vielen Dank. Also die Rekursion besteht darin, dass nach preOrder(knoten.links) Wieder an diese Stelle gesprungen wird und somit der zweite if-Block bearbeitet wird. Ich dachte dafür wäre ein return notwendig. Danke.

 

[LatinFavourite]

Hallo, ich melde mich noch einmal zurück, habe inzwischen das Einfügen und Ausgeben rekursiv implementiert. Das Löschen macht mir gerade noch Schwierigkeiten. Wenn ich bei einem gefüllten Baum die Wurzel löschen möchte, so gehe ich einen nach rechts und dann solange nach links bis kein Element folgt. Das letzte Element ist dann die neue Wurzel. Die Wurzel wird bei mir auch ersetzt, der Knoten tritt dann jedoch doppelt auf. Bin noch nicht fertig, aber hat jemand vielleicht einen Rat. Danke.

public void delete(K key){
        if(mRoot.mKey.compareTo(key) == 0){
            if(mRoot.mLeft == null && mRoot.mRight == null){
                mRoot = null;
            }else if(mRoot.mLeft != null && mRoot.mRight == null){
                mRoot = mRoot.mLeft;
                mRoot.mLeft = null;
            }else if(mRoot.mLeft == null && mRoot.mRight != null){
                mRoot = mRoot.mRight;
                mRoot.mRight = null;
            }else{
                delete(mRoot.mRight, key);
            }
        }
    }
  
    private void delete(Node current, K key){

        if(current.mLeft != null){
            delete(current.mLeft, key);
        }else{
            mRoot.mKey = current.mKey;
            mRoot.mData = current.mData;
            current = null;
        }
          
    }