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.