Traversée de commande de poste non récursive

Question

J'ai vu l'algorithme de traversée de commande de poste suivant dans un site Web ... il semble correct. Je veux juste vérifier que cet algorithme fonctionne correctement - cet algorithme est-il correct pour la traversée de post-commande sans récursion?

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); } 
      } 
     } 
    } 
} 

Answer 1

pas ici prev ne devrait pas commencer par null par exemple: pour bst ayant des noeuds 5 2 1 3 7 6 8 0 il ne considérera pas zéro car à 1 son droit est nul et cette fois précédente sera également nul, donc il ne considérera pas son enfant de gauche, c'est-à-dire 0 écriture précédente = toute valeur mais non nulle

Answer 2

Essayez d'écrire des versions itératives des méthodes de traversée binaire précommande, en ordre et après commande. Vous verrez alors le modèle ou la méthodologie de conversion de leurs versions récursives correspondantes dans les versions itératives.

Point clé colle à quelques règles de base:
- Sélection de nœud Utilisation (par exemple, currentNode = currentNode-> gauche avant de réitérer la boucle, etc.) pour traversal noeud immédiat.
- Utilisez la pile pour mémoriser les nœuds qui doivent être visités ou revisités plus tard.
- Si un noeud doit être "REvisited", détecter/conserver l'état afin de pouvoir indiquer si le noeud suivant doit être "traité" lors de la prochaine itération ou si l'un des autres noeuds enfant doit être visité avant le le noeud peut être traité.

Si vous respectez ces règles, vous pouvez facilement accomplir les tâches.

Voici un exemple de la traversée itérative d'un ordre après l'ordre. Ignorer BinarySearchTree - cela fonctionne pour tous les arbres binaires.

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); 
     } 
    } 

Answer 3

Voici le code de travail

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; 

     } 
    }