Aidez-moi à comprendre Inorder Traversal sans utiliser la récursivité

Question

Je suis en mesure de comprendre précommande traversée sans utiliser la récursivité, mais je vais avoir un moment difficile avec afinde traversée. Je ne semblent tout simplement pas l'obtenir, peut-être, parce que je n'ai pas compris le fonctionnement interne de la récursivité.

C'est ce que j'ai essayé jusqu'à présent:

def traverseInorder(node):
    lifo = Lifo()
    lifo.push(node)
    while True:
        if node is None:
            break
        if node.left is not None:
            lifo.push(node.left)
            node = node.left
            continue
        prev = node
        while True:
            if node is None:
                break
            print node.value
            prev = node
            node = lifo.pop()
        node = prev
        if node.right is not None:
            lifo.push(node.right)
            node = node.right
        else:
            break

L'intérieur tandis que la boucle ne fonctionne tout simplement pas. Aussi, certains éléments sont arriver imprimé deux fois; peut-être que je peux résoudre ce problème en vérifiant si le nœud a été imprimé avant, mais qui nécessite une autre variable, qui, encore une fois, ne vous sentez pas bien. Où vais-je tort?

Je n'ai pas essayé postorder de la traversée, mais j'imagine que c'est similaire et je ferai face à la même conceptuel blocage il y a, trop.

Merci pour votre temps!

P. S.: Définitions, Lifo et Node:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class Lifo:
    def __init__(self):
        self.lifo = ()
    def push(self, data):
        self.lifo = (data, self.lifo)
    def pop(self):
        if len(self.lifo) == 0:
            return None
        ret, self.lifo = self.lifo
        return ret

Answer 1

Démarrer avec l'algorithme récursif (pseudo-code) :

traverse(node):
  if node != None do:
    traverse(node.left)
    print node.value
    traverse(node.right)
  endif

C'est un cas clair de la queue de récursivité, de sorte que vous pouvez facilement le transformer en un tout-en boucle.

traverse(node):
  while node != None do:
    traverse(node.left)
    print node.value
    node = node.right
  endwhile

Vous êtes de gauche avec un appel récursif. Ce que l'appel récursif n'est pousser un nouveau contexte dans la pile, exécutez le code à partir du début, puis récupérer le contexte et de faire ce qu'elle faisait. Ainsi, vous créez une pile de stockage, et une boucle qui détermine, à chaque itération, si nous sommes dans une "première" de la situation (non-null nœud) ou d'un "retour" à la situation (null nœud, non-pile vide) et exécute le code approprié:

traverse(node):
  stack = []
  while !empty(stack) || node != None do:
    if node != None do: // this is a normal call, recurse
      push(stack,node)
      node = node.left
    else // we are now returning: pop and print the current node
      node = pop(stack)
      print node.value
      node = node.right
    endif
  endwhile

La chose difficile à comprendre, c'est le "retour" de la partie: vous devez déterminer, dans votre boucle, si le code que vous utilisez est dans le "saisir la fonction" situation ou dans le "renvoi d'appel" de la situation, et vous aurez l' if/else chaîne avec autant de cases que vous avez un non-terminal récurrences dans votre code.

Dans cette situation spécifique, nous utilisons le nœud de garder l'information à propos de la situation. Une autre solution serait de stocker dans la pile elle-même (tout comme un ordinateur ne la récursivité). Avec cette technique, le code est moins optimal, mais plus facile à suivre

traverse(node):
  // entry:
  if node == NULL do return
  traverse(node.left)
  // after-left-traversal:
  print node.value
  traverse(node.right)

traverse(node):
   stack = [node,'entry']
   while !empty(stack) do:
     [node,state] = pop(stack)
     switch state: 
       case 'entry': 
         if node == None do: break; // return
         push(stack,[node,'after-left-traversal']) // store return address
         push(stack,[node.left,'entry']) // recursive call
         break;
       case 'after-left-traversal': 
         print node.value;
         // tail call : no return address
         push(stack,[node.right,'entry']) // recursive call
      end
    endwhile 

Answer 2

Voici un simple code c ++ non récursif dans l'ordre.

 void inorder (node *n)
{
    stack s;

    while(n){
        s.push(n);
        n=n->left;
    }

    while(!s.empty()){
        node *t=s.pop();
        cout<<t->data;
        t=t->right;

        while(t){
            s.push(t);
            t = t->left;
        }
    }
}
 

Answer 3

def print_tree_in(racine):
 pile = []
 courant = racine
 while True:
 tout en courant n'est pas Rien:
la pile.append(en cours)
 courant = courant.getLeft();
 si pas de pile:
de retour
 courant = pile.pop()
 d'impression actuelle.getValue()
 tout en courant.getRight est None et de la pile:
 courant = pile.pop()
 d'impression actuelle.getValue()
 courant = courant.getRight();

Answer 4

 def traverseInorder(node):
   lifo = Lifo()

  while node is not None:
    if node.left is not None:
       lifo.push(node)
       node = node.left
       continue

   print node.value

   if node.right is not None:
      node = node.right
      continue

   node = lifo.Pop()
   if node is not None :
      print node.value
      node = node.right
 

PS: Je ne connais pas Python donc il peut y avoir quelques problèmes de syntaxe.

Answer 5

Voici un échantillon de l'ordre dans la traversée à l'aide de la pile en c# (.net):

(par ordre de poste itératif vous pouvez vous référer à: Poste de commande de la traversée de l'arbre binaire sans récursivité)

public string InOrderIterative()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                var iterativeNode = this._root;
                while(iterativeNode != null)
                {
                    stack.Push(iterativeNode);
                    iterativeNode = iterativeNode.Left;
                }
                while(stack.Count > 0)
                {
                    iterativeNode = stack.Pop();
                    nodes.Add(iterativeNode.Element);
                    if(iterativeNode.Right != null)
                    {
                        stack.Push(iterativeNode.Right);
                        iterativeNode = iterativeNode.Right.Left;
                        while(iterativeNode != null)
                        {
                            stack.Push(iterativeNode);
                            iterativeNode = iterativeNode.Left;
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

Voici un échantillon de personnes ayant visité le pavillon:

public string InorderIterative_VisitedFlag()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                BinaryTreeNode iterativeNode = null;
                stack.Push(this._root);
                while(stack.Count > 0)
                {
                    iterativeNode = stack.Pop();
                    if(iterativeNode.visted)
                    {
                        iterativeNode.visted = false;
                        nodes.Add(iterativeNode.Element);
                    }
                    else
                    {
                        iterativeNode.visted = true;
                        if(iterativeNode.Right != null)
                        {
                            stack.Push(iterativeNode.Right);
                        }
                        stack.Push(iterativeNode);
                        if (iterativeNode.Left != null)
                        {
                            stack.Push(iterativeNode.Left);
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

les définitions de la binarytreenode, listtostring utilitaire:

string ListToString(List<int> list)
        {
            string s = string.Join(", ", list);
            return s;
        }


class BinaryTreeNode
    {
        public int Element;
        public BinaryTreeNode Left;
        public BinaryTreeNode Right;        
    }