Geschrieben von as_string am 24.11.2017 um 15:36:
RE: Binärbaum durchlaufen
| Zitat: |
Original von algori
Das soll die sortierte Folge der Knoten des Baumes angeben. |
Ja.
| Zitat: |
Original von algori
Nach meinem Verständnis wird der Vater vor den Kindern ausgegeben, also print(x) passiert, bevor print(x) im nächsten Aufruf passiert ... Erklärung please ? |
Wieso das denn? Es wird erst die Rekursion für den linken Unterbaum gemacht, dann erst der Vater ausgegeben und danach die Rekursion für den rechten. Wenn das bei jedem einzelnen Knoten passiert, dann bewahrt das die Reihenfolge, weil die ja so ist, dass alles im linken Unterbaum kleiner/vor dem aktuellen Vaterknoten sein muss und alles rechts größer/nach dem Vater. Man nennt das dann auch ein "in-order-traversal".
| Zitat: |
Original von algori
Die Laufzeit ist :
t(n) = 1 + t(k) + 1 + t(n-k-1)
Kann das jemand erklären ? |
Da Du uns nicht gesagt hast, was n und was k ist (n wahrscheinlich die Elemente im Baum? k die Elemente im linken Teilbaum, dann sind n-k-1 ja die übrigen Elemente im rechten Teilbaum, aber das ist nur geraden), eher schwierig.
Ansonsten, wenn meine Annahmen richtig sein sollten, ist das einfach nur hingeschrieben, was man aus der rekursiven Funktion rausliest: eine 1 für alles was vor dem rekursiven Aufruf ist, dann die Laufzeit für den rekursiven Aufruf für den linken Teilbaum, eine 1 für die Ausgabe des Vaters und wieder ein t(n-k-1) für die Laufzeit des rechten Teilbaums. Da ist nicht viel "Magie" drin, ist einfach nur das offensichtliche hingeschrieben.
Gruß
Marco