Ich habe den Code zur Wirbeltraversierung (endlich!) ein bisschen näher angeschaut. (Ist auch nicht so super einfach zu verstehen.) In der Funktion rotate fände ich eine Kennung der **-Variablennamen ganz gut, also entweder Pcur statt nur cur oder gar pCur vs. Cur in wTrav. Zweitens meine ich beobachten zu können, dass ein globaler Zähler in wTrav zu jedem Knoten modulo 3 genau 3 verschiedene Werte auswirft, s. die untenstehende Tabelle, wo die 4. Spalte diesen Zähler und die 5. (gruppiert nach Knoten) den 3-er-Rest zeigt. visit pre 1 1 1 visit pre 2 2 2 visit pre 4 3 0 visit in 4 4 1 visit post 4 5 2 visit in 2 6 0 visit pre 5 7 1 visit in 5 8 2 visit pre 7 9 0 visit in 7 10 1 visit post 7 11 2 visit post 5 12 0 visit post 2 13 1 visit in 1 14 2 visit pre 3 15 0 visit pre 6 16 1 visit pre 8 17 2 visit in 8 18 0 visit post 8 19 1 visit in 6 20 2 visit pre 9 21 0 visit in 9 22 1 visit post 9 23 2 visit post 6 24 0 visit in 3 25 1 visit post 3 26 2 visit post 1 27 0 Dieses Gesetz müsste man erstmal beweisen, was vielleicht nicht so schwer ist, weil man jeden Knoten, zu dem man abgestiegen ist, beim Wiederaufstieg genau 3 mal besucht hat. Wenn man nun pro Knoten 2 Bits spendiert, die initial auf 3 gesetzt sind, könnte man beim ersten Besuch den Rest mod 3 (∈ [0,2]) des globalen Zählers reinschreiben und nachfolgende Besuche abhängig von (globalem Zähler abzüglich diesen Rest (wenn ≠ 3)) als in-order- resp. post-order-Besuch erkennen. Ob da vllt noch mehr rauszuholen ist? (Allerdings sollte man annehmen, dass Lindstrom und die vielen Asse solche Überlegungen auch schon angestellt haben.) Ich habe auch eine neue Version in die Sandbox. Beste Grüße - Nomen4Omen 10:58, 25. Mär. 2020 (CET)