Deinen Algorithmus verstehe ich jetzt auch besser. Er steuert aktiv über die Kind-pointer auf den Rest des Baums zu. Wenn nicht Modulo gearbeitet würde, müsste der Nachweis erbracht werden, dass ein Knoten mit cnt == 3 nicht (nochmal) angefasst wird. Und das ist natürlich so: (wie Du schon sagtest): "Fuer den Algorithmus genuegt das." Das ist bei mir im Grund dasselbe. Wobei bei mir die Schleife sehr anders aufgedröselt ist und die Nähe zur rekursiven Version fast nicht mehr erkennbar. Ja, er ist von mir. Ich bin auf ihn gekommen, weil bei anderen Leuten die iterativen pre-, in-, post-order Algorithmen so außerordentlich verschieden ausfallen, wo doch der rekursive problemlos alle 3 nebeneinander enthält. Natürlich weiß ich nicht, ob's ihn in der weiten Welt sonstwo noch gibt. Ich habe auch einen Fehler gefunden: Wenn die Wurzel nur ein linkes Kind hat, dann findet er das Ende nicht. Es ist nicht schwer, das zu verbessern. Dabei fiel mir auch auf, dass ich das zweifache Vorkommen von printf in-order sowie von printf post-order jeweils in ein einfaches zusammenführen kann. Das mit dem ancestor stack sehe ich nicht dramatisch: Er enthält höchstens so viele Elemente wie Knoten, und in den "guten", balancierten Fällen nur logarithmisch viele. Nicht ganz unwichtig finde ich auch, dass der Stack lokal im Traversierprogramm bleiben kann (und nicht nach unten oder außen weitergegeben werden muss.) Daran, dass man den parent in dieser Schleife lokal speichern kann, glaube ich nicht so recht, denn die lokalen Variablen werden durch die Schleife völlig aus ihrem Kontext herausgerissen. Auch Folgendes geht nicht: den parent am Platz des Kindes, zu dem man hinabzusteigen im Begriff ist, ablegen. Und nachher, wenn man von diesem Kind aufsteigt (zurückkommt), ihn dort abgreifen und sofort den Kind-Zeiger restaurieren. Denn wie soll dann die Abfrage if (N == next->L) funktionieren? Aber ein Bit würde helfen, in dem festgehalten wird, ob ein Knoten linkes oder rechtes Kind ist (chirality bit). Ich muss die korrigierte Version noch überprüfen. Dann stelle ich sie hier rein. Das mit ArXiv habe ich noch nie gemacht. Würde ich gerne, denn auch ich bin dafür, dass er in en:tree traversal reinkommt. Ohne ArXiv müsste ich behaupten, dass er zB bei Pfaff vorkommt – nur halt ein bisschen umgebastelt ist. - Viele Grüße, Nomen4Omen 17:06, 12. Mär. 2020 (CET)