Nicht-rekursive post-order-traversal

Sah ich folgenden post-order-traversal Algorithmus in eine Homepage... es scheint richtig zu sein. Ich will einfach nur, um zu überprüfen, dass dieser Algorithmus arbeitet korrekt — ist dieser Algorithmus korrekt für post-order-Traversierung ohne Rekursion?

void postOrderTraversal(Tree *root)
{
    node * previous = null;
    node * s = null;
    push(root);
    while( stack is not empty )
    {
        s = pop();

        if(s->right == null and s->left == null)
        {
            previous = s;
            process s;
        }
        else
        {
            if(s->right == previous or s->left == previous)
            {
                previous = s;
                process s;
            }
            else
            {
                push( s );
                if(s->right) { push(s->right); }
                if(s->left)  { push(s->left);  }
            }
        }
    }
}
  • Haben Sie Lesen Sie den rest des Fadens in Algogeeks? mail-archive.com/[email protected]/msg03546.html
  • Es ist nicht syntaktisch rekursiv, weil es emuliert die Rekursion mit PUSH und POP.
  • Barry, ich würde behaupten, dass es unnötig ist, selbst zu qualifizieren, ist es mit "zu emulieren."
  • Nein, ich denke, dass es notwendig ist, weil sonst bekommen wir gesogen in die semantische tar-pit, wo wir nicht sagen, der Unterschied zwischen "iterativ" und "rekursiv", wie die Hälfte der Programmierer in der Welt bereits haben.
InformationsquelleAutor suresh | 2009-09-24
  1. 2

    Versuchen so zu schreiben, iterative Versionen der pre-order, in-order und post-order binäre traversal-Methoden. Sie sehen dann das Muster oder die Methodik der Konvertierung Ihrer entsprechenden rekursiven Versionen in die iterative Versionen.

    Wichtiger Punkt ist das festhalten an einige grundlegende Regeln:


    - Verwenden Sie für die Auswahl der Strukturknoten (z.B. currentNode = currentNode->Links vor der Wiederholung der Schleife, etc.) für die sofortige Knoten-traversal.


    - Verwenden Sie Stapel zu erinnern Knoten müssen besucht werden oder revisited später.


    - Wenn ein Knoten sein müssen "REvisited"," erkennen /halten den Zustand, so dass Sie angeben können, ob der nächste Knoten werden muss "verarbeitet" in der nächsten iteration oder eines von mehreren untergeordneten Knoten, die besucht werden sollten, bevor der Knoten verarbeitet werden können.

    Wenn Sie halten Sie sich an diese Regeln, Sie können esily die Aufgaben.

    Hier ist ein Beispiel für die iterative post-order-traversal. Ignorieren BinarySearchTree - es funktioniert für binäre Bäume.

        public static IEnumerator<BinarySearchTreeNode<T>> GetPostOrderTraverseEnumerator(BinarySearchTreeNode<T> root)
    {
        if (root == null)
        {
            throw new ArgumentNullException("root");
        }

        Stack<BinarySearchTreeNode<T>> stack = new Stack<BinarySearchTreeNode<T>>();

        BinarySearchTreeNode<T> currentNode = root;

        //If the following flag is false, we need to visit the child nodes first
        //before we process the node.
        bool processNode = false;

        while (true)
        {
            //See if we need to visit child nodes first
            if (processNode != true)
            {
                if (currentNode.Left != null)
                {
                    //Remember to visit the current node later
                    stack.Push(currentNode);

                    if (currentNode.Right != null)
                    {
                        //Remember to visit the right child node later
                        stack.Push(currentNode.Right);
                    }

                    //Visit the left child
                    currentNode = currentNode.Left;
                    continue;
                }
                else if (currentNode.Right != null)
                {
                    //Remember to visit the current node later
                    stack.Push(currentNode);

                    //Visit the right child
                    currentNode = currentNode.Right;
                    continue;
                }
            }

            //Process current node
            yield return currentNode;

            //See if we are done.
            if (stack.Count == 0)
            {
                break;
            }

            //Get next node to visit from the stack
            BinarySearchTreeNode<T> previousNode = currentNode;
            currentNode = stack.Pop();

            //See if the next node should be processed or not
            //This can be determined by the fact that either of the current node's child nodes
            //has just been processed now.
            processNode = (previousNode == currentNode.Left || previousNode == currentNode.Right);
        }
    }
    InformationsquelleAutor Hwisung Im
  2. 1

    nicht hier zurück, sollten Sie nicht beginnen mit null
    zB:für bst, dass der Knoten 5 2 1 3 7 6 8 0
    Sie werden nicht als null, da an 1 seiner rechten Seite ist null, und dieses mal vorher auch null sein, daher wird es nicht betrachten Sie Ihre linke Kind also 0
    schreiben Sie die vorherigen=beliebiger Wert, aber nicht null

    InformationsquelleAutor abhinav8
  3. 1

    Hier ist der funktionierende code 

    Stack s=new Stack();
    while(true){
       if(root!=null){
           s.push(root);
           root=root.left;
       }
       else{
            if(s.top().right==NULL){
               root=s.top();
               s.pop();
               System.out.println(root.data);
               if(root==s.top().right){
                    System.out.println(s.top().data);
                    s.pop();
               }
            }
       if(!s.empty())
          root=s.top().right;
       else 
          root=NULL;

       }
    }
    • Fehler für diesen input. 3 \ 2 \ 1 ich erinnere mich, sah ich diesen code in ein Buch .. :-/
    InformationsquelleAutor Akash Verma
Schreibe einen Kommentar