Habe inzwischen auch den Hirschberg ueberflogen und finde ihn nicht mehr so toll. Weitere Nachteile (ausser den von Dir genannten) sind: Zeiger von ausserhalb des Baumes in ihn hinein (gespeicherte Suchergebnisse etwa) verlieren ihre Gueltigkeit; bei grossen (d.h. viel Speicherplatz benoetigenden) Keys kopiert sich der Algorithmus zu Tode. Dann doch lieber irgendwo noch ein Chirality-Bit abknapsen! Ich hab jetzt auch endlich Referenzen zur Wirbeltraversieung gefunden, naemlich Dwyer.1974 und Lindstrom.1973. Sie sind selbst nicht kostenlos zugaenglich, werden aber zitiert in Mcjones.Stepanov.2019 S.143 und Manghirmalani.Mateti.1988 S.30. Letztere erwaehnen die Zeigerrotation wie in den Bildern, erstere zeigen C++ Source Code. Anders als ich dachte, brauchen sie keine parent-Zeiger, sondern setzen "link reversal" ein. Auch mein cnt-Feld brauchen sie nicht unbedingt, sondern nur dann, wenn sie bei jedem Besuch wissen wollen, der wievielte es gerade ist. Ich werde den Artikel demnaechst entsprechend abaendern. Der nach C uebersetzte und (aus Faulheit an meiner alten Datenstruktur, aber ohne Verwendung der parent-Felder in m[]) ausprobierte Code sieht so aus: define LF 1 define RG 2 static inline void swRot(struct _node **cur,struct _node **prv) { /* tree_rotate */ struct _node * const tmp = (*cur)->ptr[LF]; (*cur)->ptr[LF] = (*cur)->ptr[RG]; (*cur)->ptr[RG] = *prv; if (tmp == NULL) { prv = tmp; } else { prv = *cur; cur = tmp; } } static inline void swTrav(struct _node *tree) { /* traverse_rotating */ struct _node *cur; struct _node *prv; if (tree == NULL) return; cur = tree; do { visit(cur); swRot(&cur,&prv); } while (cur != tree); do { visit(cur); swRot(&cur,&prv); } while (cur != tree); visit(cur); swRot(&cur,&prv); } int main(void) { swTrav(&m[1]); return 0; } Die erste do-Schleife traversiert den linken Unterbaum der Wurzel, sie stoppt, wenn die Wurzel in in-order-Position besucht wird. Die zweite Schleife traversiert dann den analog rechten Unterbaum. Der letzte visit-Aufruf ist die post-order-Position fuer die Wurzel. Meine Bildchen will ich neu zeichnen, sobald ich ganz verstanden habe, wie der bisherige parent-Zeiger durch das Paar cur/prv realisiert wird. - Jochen Burghardt 15:21, 13. Mär. 2020 (CET)