Ueber die Variablennamen will ich nicht streiten. Meinen Geschmack trifft das "p" nicht; als Extremfall habe ich schon Programmierkonventionen gesehen, wo jede Variable mit dem Projektnamen und dem Typnamen beginnen musste, was Programmierfehler (wohl entgegen der Intention) nicht verhindert sondern (durch die unuebersichtlich langen Zeilen) eher beguenstigt hat. Deine Beobachtung mit dem globalen Zaehler finde ich interessant. Ich glaube, Deine Beweisidee ist die richtige (mit Induktion ueber die Baumhoehe). Mit 2-Extrabits kann man sich aber sowieso merken, wie oft man bei einem Knoten schon gewesen ist (mit 0 initialisieren und bei jedem Besuch hochzaehlen, groesser als 3 wird er ja nicht) und entsprechen die pre- (0), in- (1) oder postorder-Aktion (2) ausfuehren. Das nur aus dem globalen Zaehler alleine rauszukriegen, waere toll, aber vermutlich geht's nicht, auch wenn man die Information ueber den vorigen Knoten noch zur Verfuegung hat, oder? Vielleicht kann man Dank des Zaehlers irgendwie mit nur einem Extrabit auskommen? Ich hab den wTrav nur abgeschrieben (von C++ nach C uebersetzt). Deine Vereinfachung sieht ueberzeugend aus, ich lasse sie morgen mal durch meine Tests laufen. Du meinst, die 2 Bits jeweils auf dem Stack speichern? Das spart gegenueber 2 Bits pro Knoten doch eine ganze Menge; Zusatzspeicher O(log n) statt O(n) im Mittel. Vielleicht gibt es Big-Data-Anwendungen, in denen das wichtig ist. Und das jetzt zusammen mit dem globalen Zaehler, kann man da nicht noch was rausquetschen? Zur Zeit komme ich bestimmt nicht an die Originalarbeiten. Wenn die Bibliotheken wieder aufmachen, kann ich es an der Uni versuchen. Was bei JSTOR angeboten wird, bekomme ich dort auf jeden Fall. Wenn ich was frei im Netz gefunden habe, hab ich den Link schon immer dazugeschrieben. - Jochen Burghardt 23:47, 31. Mär. 2020 (CEST)