[Pascal] Binärer Baum

[Moeki]

Anwendungsentwickler vor. Als FiSi habe ich von folgender Aufgabe nicht ganz so viel Ahnung. Könntet ihr mir also bitte weiterhelfen und nen Denkansatz geben?

Schreiben Sie eine Prozedor swap in Pascal, die angewandt auf einen binären Baum den linken und rechten Sohn jedes Knotens vertauscht:

a)rekursiv

b)nicht-rekursiv

Was ein binärer Baum ist, weiß ich und ich kann mir auch bildlich vorstellen, wie der linke Teilbaum eines Knotens mit dem rechten Teilbaum vertauscht werden soll, aber ich kann das nicht algorithmisch ausdrücken.

Ausgehend von folgender Typdefinition, muss ich doch im Endeffekt nur die Zeiger umbiegen oder? Quasi alle Zeiger lt auf rt setzen und umgekehrt? Wie durchlaufe ich dabei den ganzen Baum?

type data=...

       knoten=record

                  inhalt:data;

                  lt,rt:^knoten;

                  end.


var b:^knoten

[Bubble]

Ausgehend von folgender Typdefinition, muss ich doch im Endeffekt nur die Zeiger umbiegen oder? Quasi alle Zeiger lt auf rt setzen und umgekehrt? Wie durchlaufe ich dabei den ganzen Baum?

Richtig, Du musst die beiden Zeiger vertauschen. Schreibe dazu am besten eine Funktion, die als einzigen Parameter einen Knoten bekommt. Diese Funktion vertauscht dann die beiden Zeiger und ruft sich anschließend für die beiden Knoten, auf die die Zeiger zeigen, selbst auf (natürlich nur, wenn die Zeiger gültig sind, also ungleich NULL). Damit hast Du bereits die rekursive Lösung.