Ich hab es ausprogrammiert und laufen lassen, bevor ich den Code auf der Seite gezeigt hab. Was fuer ein komplettes C-Programm noch fehlt, steht hier: include void visit(struct _node *tree) { const char * const name[3] = { "pre ", "in ", "post" }; printf("visit %s %d\n",name[tree->cnt],tree->key); } struct _node m[10] = { /* par lft rgt */ /*0*/ { 0, 0, {NULL , NULL , NULL } }, /*1*/ { 0, 1, {NULL , &m[2], &m[3]} }, /*2*/ { 0, 2, {&m[1], &m[4], &m[5]} }, /*3*/ { 0, 3, {&m[1], &m[6], NULL } }, /*4*/ { 0, 4, {&m[2], NULL , NULL } }, /*5*/ { 0, 5, {&m[2], NULL , &m[7]} }, /*6*/ { 0, 6, {&m[3], &m[8], &m[9]} }, /*7*/ { 0, 7, {&m[5], NULL , NULL } }, /*8*/ { 0, 8, {&m[6], NULL , NULL } }, /*9*/ { 0, 9, {&m[6], NULL , NULL } }, }; int main(void) { wTrav(&m[1]); return 0; } Das Ergebnis eines Laufs sieht bei mir so aus: visit pre 1 visit pre 2 visit pre 4 visit in 4 visit post 4 visit in 2 visit pre 5 visit in 5 visit pre 7 visit in 7 visit post 7 visit post 5 visit post 2 visit in 1 visit pre 3 visit pre 6 visit pre 8 visit in 8 visit post 8 visit in 6 visit pre 9 visit in 9 visit post 9 visit post 6 visit in 3 visit post 3 visit post 1 Der Baum in m[] sieht so aus: 1 / \ / \ 2 3 / \ / 4 5 6 \ / \ 7 8 9 Bei der Invariante bzgl. cnt hab ich mich schlampig ausgedrueckt. cnt enthaelt genau genommen nicht die Anzahl der Besuche, sonderen diese Anzahl mod 3. Fuer den Algorithmus genuegt das. Ich habe, wie gesagt, den Algorithmus aus dem Gedaechnis rekonstruiert (es hat einige Tests und Modifikationen gebraucht, bis er den richtigen Output erzeugt hat). Sicher bin ich nur, den Namen "Wirbeltraversierung" mal gelesen und dazu in etwas die Bilder auf der Seite gesehen zu haben, mit den verwirbelten Zeigern. Bei Google findet man unter "Wirbeltraversierung" nur diese Seite. Immerhin scheint sich Master-2000 auch an den Namen erinnert zu haben. In Deinem Algorithmus hatte ich die Abfrage if (N == next->L) uebersehen bzw. an den falschen Stellen gesucht. Dank Deiner Erklaerung verstehe ich ihn jetzt so ungefaehr. Er hat gegenueber der Wirbeltraversierung tatsaechlich nur Vorteile. Du hast ihn Dir doch nicht etwa selbst ausgedacht? Falls doch, publiziere ihn schnell (z.B. als Technical Report bei ArXiv)! In jedem Fall sollte er letztendlich auf en:tree traversal erscheinen (als ich mich gegen iterative Algorithmen dort ausgesprochen habe, habe ich nicht bedacht, dass es welche geben koennte, die ohne Stack auskommen). Uebrigens koennte ich mir vorstellen, dass er auf die parent-Zeiger auch noch verzichten kann: wenn er den Zeiger, den er nach unten verfolgt, in einer lokalen Variable speichert und das Zeigerfeld im Knoten auf den parent setzt (den er aus einer anderen lokalen Variablen entnimmt). - Gruss Jochen Burghardt 12:35, 12. Mär. 2020 (CET)