Binärer Baum - wie durchlaufen?

[RTC]

Hier nochmal ein binärer Baum von meiner Homepage (musste ich mal so programmieren). Zwar nicht ganz ausgereift (noch ein paar überflüssige Variablen drin), aber die Rekursionen sieht man schon schön:

http://www.linux-related.de/studium/gdinf/suchbaum_bin.c

[Shade Of Mine]

RTC schrieb:

Ich würde put() so machen (Achtung, nicht getestet!):

Node *put(key_type const& key, value_type const& val, Node *root){
  if(!root)
    return new Node(key,val);
  if(root->key < key)
    root->left=put(key,val,root->left);
  else
    root->right=put(key,val,root->right);
  return root;
}

thx, das sieht gut aus. Da spar ich mir die Referenzen.

[Jester]

Das finde ich nicht so schön, weil Du damit einen Teil der Arbeit in die nächsthöhere Rekursionsebene verlegst (nämlich das einhägen des angefügten Teils). Beim auflösen der Aufrufe werden dann lauter unnötige Zuweisungen ausgeführt. Ich finde es mit der Referenz am elegantesten.

MfG Jester

[volkard]

entgegen der herrschenden meinung finde ich hier rekursion nicht hübsch.

[Helium]

entgegen der herrschenden meinung finde ich hier rekursion nicht hübsch.

dU ARBEITEST GERNE ITERATIV AUF REKURSIVEN dATENSTRUKTUREN? mIT DER mEINUG STEHST DU WOHL ZIEMLICH ALLEINE HIER.

[volkard]

Helium schrieb:

dU ARBEITEST GERNE ITERATIV AUF REKURSIVEN dATENSTRUKTUREN? mIT DER mEINUG STEHST DU WOHL ZIEMLICH ALLEINE HIER.

keine bange, das bin ich gewohnt.

[Bashar]

Zum Glück ist 90% aller Software so schlecht, dass man keine Bange haben muss, wenn man von irgendeiner Mehrheitsmeinung abweicht.

[bmp]

Für was bist du denn jetzt Bashar? Rekursiv oder iterativ?

[RTC]

Bei vielen Knoten im Baum hat die Rekursion speichertechnische Nachteile, das ist klar!

[Bashar]

Nur bei entarteten Bäumen, sonst geht die Rekursion nicht besonders weltbewegend tief ...

[röhrich]

Abhängig von der möglichen Rekursionstiefe und dem damit verbundenen Speicherbedarfs (wirkt sich bekanntlich auch auf die Laufzeit aus) ist manchmal eine iteratives durchlaufen von Bäumen vorteilhafter.

[volkard]

in sachen laufzeit ist in c++ meist iteration schneller. das liegt aber auch nur an den schwachen compilern. manche probleme, wie die türme von hanoi drängen einem die rekursion so stark auf, daß rekursive lösungen sogar ein wenig schneller als iterative sind. und manche probleme gehen nur rekursiv (ich zähle iteration mit nem künstlichen stack als rekursion).
bei den nicht entarteten bäumen dürfte es fast wie bei den türmen von hanoi liegen.