python - postorder traversal without recursion

Ayúdame a entender Inorder Traversal sin usar recursión

Question

Puedo entender el recorrido de preorden sin usar recursión, pero estoy teniendo dificultades con el recorrido inorden. Parece que no lo entiendo, quizás, porque no he entendido el funcionamiento interno de la recursión.

Esto es lo que he intentado 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 ciclo interno while simplemente no se siente bien. Además, algunos de los elementos se imprimen dos veces; puede ser que pueda resolver esto comprobando si ese nodo se ha impreso antes, pero eso requiere otra variable, que, una vez más, no se siente bien. ¿Dónde estoy equivocado?

No he intentado atravesar el postorder, pero supongo que es similar y enfrentaré el mismo bloqueo conceptual allí también.

¡Gracias por tu tiempo!

PD: 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

@Victor, tengo alguna sugerencia sobre su implementación tratando de insertar el estado en la pila. No veo que sea necesario. Porque cada elemento que tomas de la pila ya se ha dejado atravesado. entonces, en lugar de almacenar la información en la pila, todo lo que necesitamos es una bandera para indicar si el siguiente nodo que se procesará proviene de esa pila o no. A continuación está mi implementación que funciona 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 2

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

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 3

Aquí hay un código en C ++ no recursivo simple en el 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 4

Aquí hay una muestra de cruce en orden usando stack en c # (.net):

(para la iteración de pedido posterior, puede consultar: Trazar el recorrido de la orden del árbol binario sin recursión )

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

Aquí hay una muestra 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 utilidad binarytreenode, listtostring:

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


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

Answer 5

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

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 6

Comience 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 recursividad de cola, por lo que puede convertirlo fácilmente en un ciclo while.

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

Te queda una llamada recursiva. Lo que hace la llamada recursiva es empujar un nuevo contexto en la pila, ejecutar el código desde el principio, luego recuperar el contexto y seguir haciendo lo que estaba haciendo. Entonces, crea una pila para el almacenamiento y un bucle que determina, en cada iteración, si estamos en una situación de "primera ejecución" (nodo no nulo) o una situación de "devolución" (nodo nulo, pila no vacía ) y 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 difícil de comprender es la parte de "retorno": debe determinar, en su bucle, si el código que está ejecutando está en la situación de "ingresar a la función" o en la situación de "regresar de una llamada", y usted tendrá una cadena if/else con tantos casos como tenga recursiones no terminales en su código.

En esta situación específica, estamos usando el nodo para mantener información sobre la situación. Otra forma sería almacenar eso en la pila en sí (al igual que una computadora para recursividad). Con esa 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 7

Creo que parte del problema es el uso de la variable "prev". No debería tener que almacenar el nodo anterior, debería poder mantener el estado en la pila (Lifo).

De Wikipedia , el algoritmo al que apunta es:

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

En pseudocódigo (exención de responsabilidad, no conozco Python, así que me disculpo por el código de estilo Python / C ++ a continuación!) Su algoritmo sería algo así 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);
        }
    }
}

Para el recorrido del postorder simplemente intercambie el orden en que empuja los subárboles izquierdo y derecho en la pila.

Answer 8

Cruce iterativo iterativo simple sin recursión

''''''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 9

Estado puede recordarse implícitamente

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 10

Esto puede ser útil (implementación de 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 11

Poca 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 12

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 13

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 14

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

PD: No conozco Python, por lo que puede haber algunos problemas de sintaxis.