Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Binärbaum durchlaufen » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Binärbaum durchlaufen
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
algori
Grünschnabel


Dabei seit: 22.11.2017
Beiträge: 1

Binärbaum durchlaufen Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

TreeWalk(x)

if x != null
then treeWalk(x.left)
print(x)
TreeWalk(x.right)


Das soll die sortierte Folge der Knoten des Baumes angeben.
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 ?

Die Laufzeit ist :
t(n) = 1 + t(k) + 1 + t(n-k-1)

Kann das jemand erklären ?
22.11.2017 22:36 algori ist offline Beiträge von algori suchen Nehmen Sie algori in Ihre Freundesliste auf
as_string as_string ist männlich
Routinier


Dabei seit: 06.11.2013
Beiträge: 408
Herkunft: Heidelberg

RE: Binärbaum durchlaufen Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
24.11.2017 15:36 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » Binärbaum durchlaufen