Ayúdame a entender recorrido inorder sin utilizar la recursividad

Question

Soy capaz de entender preorden recorrido sin necesidad de utilizar la recursividad, pero estoy teniendo un tiempo duro con recorrido en orden. Simplemente no parece conseguirlo, tal vez, porque no he entendido el funcionamiento interno de la recursividad.

Esto es lo que he probado hasta ahora:

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

El bucle while interior simplemente no se siente bien. Además, algunos de los elementos están consiguiendo imprime dos veces; puede ser que pueda resolver esto comprobando si ese nodo ha sido impreso antes, pero que requiere otro variable, lo que, de nuevo, no se siente bien. ¿Dónde voy mal?

No he probado orden posterior recorrido, pero supongo que es similar y que se enfrentará a la misma bloqueo conceptual allí, también.

Gracias por su tiempo!

P.S .: Definiciones de Lifo y 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

Comenzar con el algoritmo recursivo (pseudocódigo):

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

Este es un caso claro de la recursión de cola, por lo que se puede convertir fácilmente en un bucle while.

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

uno se queda con una llamada recursiva. Lo que la llamada recursiva hace es empujar un nuevo contexto en la pila, ejecuta el código desde el principio, y luego recuperar el contexto y seguir haciendo lo que estaba haciendo. Así, se crea una pila de almacenamiento, y un bucle que determina, en cada iteración, si estamos en una situación (nodo no nulo) "primera ejecución" o un "volver" situación (nodo nulo, pila no está vacía ) y se ejecuta el código apropiado:

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

Lo más difícil de entender es la parte de "retorno": usted tiene que determinar, en su bucle, si el código que se está ejecutando está en la situación "entrar en la función" o en la situación "de regresar de una llamada" y que tendrá una cadena de if/else con más casos de los que tienen recurrencias no terminales en el código.

En esta situación específica, estamos usando el nodo para mantener la información acerca de la situación. Otra forma sería la de almacenar que en la pila en sí (al igual que lo hace una computadora para la recursividad). Con esta técnica, el código es menos óptimo, pero más fácil de seguir

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

Aquí es un simple no recursivo C ++ código en orden ..

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(root):
    stack = []
    current = root
    while True:
        while current is not None:
            stack.append(current)
            current = current.getLeft();
        if not stack:
            return
        current = stack.pop()
        print current.getValue()
        while current.getRight is None and stack:
            current = stack.pop()
            print current.getValue()
        current = current.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:. No sé Python lo que puede haber una serie de cuestiones pocas sintaxis

Answer 5

Este es un ejemplo de en traversal orden usando pila en C # (.NET):

(por orden post iterativo que puede referirse a: post orden de recorrido de árbol binario sin recursividad )

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

Este es un ejemplo con la bandera visitada:

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

las definiciones de la binarytreenode, listtostring utilidad:

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


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

Answer 6

Estado puede ser recordado de manera implícita,

traverse(node) {
   if(!node) return;
   push(stack, node);
   while (!empty(stack)) {
     /*Remember the left nodes in stack*/
     while (node->left) {
        push(stack, node->left);
        node = node->left;
      }

      /*Process the node*/
      printf("%d", node->data);

      /*Do the tail recursion*/
      if(node->right) {
         node = node->right
      } else {
         node = pop(stack); /*New Node will be from previous*/
      }
    }
 }

Answer 7

@Victor, tengo alguna sugerencia en su puesta en práctica tratando de empujar el estado en la pila. No veo que sea necesario. Debido a que cada elemento se toma de la pila ya está atravesada izquierda. así que en vez de almacenar la información en la pantalla, todo lo que necesitamos es una bandera para indicar si el nodo siguiente a procesar es de esa pila o no. Lo que sigue es mi aplicación que funciona muy bien:

def intraverse(node):
    stack = []
    leftChecked = False
    while node != None:
        if not leftChecked and node.left != None:
            stack.append(node)
            node = node.left
        else:
            print node.data
            if node.right != None:
                node = node.right
                leftChecked = False
            elif len(stack)>0:
                node = stack.pop()
                leftChecked = True
            else:
                node = None

Answer 8

Poco Optimización de respuesta por @Emadpres

def in_order_search(node):
    stack = Stack()
    current = node

    while True:
        while current is not None:
            stack.push(current)
            current = current.l_child

        if stack.size() == 0:
            break

        current = stack.pop()
        print(current.data)
        current = current.r_child

Answer 9

Esto puede ser útil (aplicación Java)

public void inorderDisplay(Node root) {
    Node current = root;
    LinkedList<Node> stack = new LinkedList<>();
    while (true) {
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else if (!stack.isEmpty()) {
            current = stack.poll();
            System.out.print(current.data + " ");
            current = current.right;
        } else {
            break;
        }
    }
}

Answer 10

Simple iterativo recorrido en orden y sin recursividad

'''iterative inorder traversal, O(n) time & O(n) space '''

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

def inorder_iter(root):

    stack = [root]
    current = root

    while len(stack) > 0:
        if current:
            while current.left:
                stack.append(current.left)
                current = current.left
        popped_node = stack.pop()
        current = None
        if popped_node:
            print popped_node.value
            current = popped_node.right
            stack.append(current)

a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')

b.right = d
a.left = b
a.right = c

inorder_iter(a)

Answer 11

class Tree:

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

    def insert(self,root,node):
        if root is None:
            root = node
        else:
            if root.value < node.value:
                if root.right is None:
                    root.right = node
                else:
                    self.insert(root.right, node)
            else:
                if root.left is None:
                    root.left = node
                else:
                    self.insert(root.left, node)       

    def inorder(self,tree):
        if tree.left != None:
            self.inorder(tree.left)
        print "value:",tree.value

        if tree.right !=None:
            self.inorder(tree.right)

    def inorderwithoutRecursion(self,tree):
        holdRoot=tree
        temp=holdRoot
        stack=[]
        while temp!=None:
            if temp.left!=None:
                stack.append(temp)
                temp=temp.left
                print "node:left",temp.value

            else:
                if len(stack)>0:
                    temp=stack.pop();
                    temp=temp.right
                    print "node:right",temp.value

Answer 12

Aquí hay una solución iterativa C ++ como una alternativa a lo publicado @Emadpres:

void inOrderTraversal(Node *n)
{
    stack<Node *> s;
    s.push(n);
    while (!s.empty()) {
        if (n) {
            n = n->left;
        } else {
            n = s.top(); s.pop();
            cout << n->data << " ";
            n = n->right;
        }
        if (n) s.push(n);
    }
}

Answer 13

Aquí hay un código Python iterativo para Inorder Transversal ::

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

def inOrder(root):
    current = root
    s = []
    done = 0

    while(not done):
        if current is not None :
            s.append(current)
            current = current.left
        else :
            if (len(s)>0):
                current = s.pop()
                print current.data
                current = current.right
            else :
                done =1

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

inOrder(root)

Answer 14

Creo que parte del problema es el uso de la variable "prev". Usted no debería tener que almacenar el nodo anterior debe ser capaz de mantener el estado de la pila (LIFO) en sí.

Wikipedia , el algoritmo que se está buscando es:

1. Visita la raíz.
2. Recorrer el subárbol izquierdo
3. Recorrer el subárbol derecho

En pseudocódigo (descargo de responsabilidad, no sé lo que Python disculpas por el código de estilo de Python / C ++ de abajo!) El algoritmo sería algo como:

lifo = Lifo();
lifo.push(rootNode);

while(!lifo.empty())
{
    node = lifo.pop();
    if(node is not None)
    {
        print node.value;
        if(node.right is not None)
        {
            lifo.push(node.right);
        }
        if(node.left is not None)
        {
            lifo.push(node.left);
        }
    }
}

Por orden posterior recorrido simplemente intercambiar el orden de empujar los subárboles izquierdo y derecho en la pila.