Iterativo de recorrido de orden posterior sin mantener la bandera visitado
https://stackoverflow.com/questions/1350311
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Por qué es necesario mantener la bandera visitado por iterativo de recorrido de orden posterior y no para finde o el orden pre recorrido iterativo.
¿Es posible hacer el recorrido posterior orden sin mantener la bandera visitado?
Solución
Esto es una visita posterior a la orden:
postordervisit(t)
{ if not(leaf(t))
{ postordervisit(left(t);
postordervisit(right(t));
}
L1: process(t);
L2:
}
No utiliza ninguna bandera. ¿Por qué cree una bandera es necesario?
Tal vez no entiendo la frase, "orden transversal posterior iterativa". Por simetría, si usted piensa que "recorrido en preorden iterativo" no necesita una bandera, Afirmo que lo tienes que creer "recorrido iterativo orden posterior" es también bandera libre, y viceversa.
EDIT: Mi mal, debe ser a altas horas de la noche. "Iterativo", que significa "poner en práctica sin recursividad". Aceptar, por lo que poner en marcha su propia pila de nodos, y que tienen que poner en práctica lo que equivale a una pila de direcciones de retorno. Creo que la bandera está simulando el efecto de la devolución abordar saber si ir a L1 o L2 siguiente. Y ya que se necesita para esta orden posterior, por la simetría que lo necesite para pre-orden.
EDITAR octubre de 2010: Mi mal otra vez, el algoritmo proporcionado no era posterior a la orden. Revisada.
Otros consejos
orden posterior recorrido versión iterativa podría llevarse a cabo sin el uso de banderas visitados, es simplemente más difícil de implementar.
Vea aquí por dos soluciones para el recorrido iterativo orden posterior sin necesidad de utilizar ninguna bandera visitados.
http://www.leetcode.com/ 2010/10 / árbol binario post-fin-traversal.html
Si empezamos con el simple algoritmo recursivo orden posterior,
def postorder1(node, f):
# a:
if node is None:
return None
postorder1(node.left, f)
# b:
postorder1(node.right, f)
# c:
f(node)
podemos picar la función en tres partes "a", "b" y "c" y, a continuación, ingenuamente traducirlo en un algoritmo iterativo mediante la emulación de una pila de llamadas virtual:
def postorder2(node, f):
stack = [("a", node)]
while stack:
go, node = stack.pop()
if go == "a":
if node is not None:
stack.append(("b", node))
stack.append(("a", node.left))
elif go == "b":
stack.append(("c", node))
stack.append(("a", node.right))
elif go == "c":
f(node)
A partir de este se observa que la pila sólo se puede modificar en una de tres maneras:
[…, a] → […, b, a]
[…, b] → […, c, a]
[…, c] → […]
Esto implica que:
- "a" sólo puede aparecer como máximo una vez en la parte superior de la pila , mientras que
- "b" y "c" y aparecer cualquier número de veces en el medio de la pila, posiblemente intercalada.
Por lo tanto, realmente no necesita para almacenar "a" dentro de la pila - una única variable para almacenar "a" sería suficiente. Esto nos permite simplificar el algoritmo iterativo ingenua en la forma más convencional:
def postorder3(node, f):
stack = []
while True:
if node:
stack.append((True, node))
node = node.left
elif stack:
left, top = stack.pop()
if left:
stack.append((False, top))
node = top.right
else:
f(top)
else:
break
El indicador booleano en la pila es la “bandera visitado”. En este ejemplo, no almacenamos la bandera directamente en los nodos, pero dentro de nuestra pila, pero el efecto neto es el mismo. Algunas variantes del algoritmo utilizan un “por última vez el nodo” variable en lugar, pero que requiere una manera de comparar los nodos de la “identidad” (puntero / igualdad de referencia), que no asumimos aquí.
Esta bandera es un esencial parte del algoritmo, ya que, como se señala en nuestro análisis anterior, la "b" y "c" entradas en la pila pueden aparecer de forma completamente arbitraria. Necesitamos algunos tipo de información que nos diga si hay que recorrer hacia la derecha o llame f.
He encontrado un problema en la solución del usuario 1337c0d3r : se trata simplemente de una pre-orden en el orden inverso. Mi solución utiliza una "lista activa" para marcar los nodos en la pila.
(Se puede almacenar la bandera marca en la pila. Fijará por esa solución por separado.)
void print_postorder(Nodes const& roots)
{
typedef std::set<Node const*> ActiveList;
ActiveList activeNodes;
vector<Nodes::const_iterator> stack(1, roots.begin());
while( stack.empty() == false )
{
Nodes::const_iterator node = stack.back();
ActiveList::iterator activeEntry = activeNodes.find( &*node );
if( activeEntry == activeNodes.end() )
{
// This node is now active.
activeNodes.insert( &*node );
// Plan to visit each child.
for( Nodes::const_reverse_iterator rchild = node->children.rbegin();
rchild != node->children.rend(); ++rchild )
{
Nodes::const_reverse_iterator rchild2 = rchild;
Nodes::const_iterator child = (++rchild2).base();
stack.push_back(child);
}
}
else
{
// Post-order visit the node.
std::size_t depth = activeNodes.size();
for( std::size_t i = 0; i < 4 * depth; ++i )
cout << ' '; // Indent
cout << node->name << endl;
// We're finished with this node.
activeNodes.erase( activeEntry );
stack.pop_back();
}
}
}
// Try this for yourself! Tree representation:
#include <vector>
#include <set>
struct Node;
typedef std::vector<Node> Nodes;
struct Node
{
std::string name;
Nodes children;
};
Creo que el programa de algoritmo de la anterior reseña para atravesar el puerto orden es en como, "procesos" el nodo antes de visitar la izquierda sub-árbol. Postorden Traversal es esencialmente la misma que la notación polaca inversa en la que los operandos (nodos hoja o sub-árboles) preceden el operador (el siguiente nodo sub-árbol superior).
Un corregido orden posterior recorrido algorith sería:
postordervisit(t)
{ if null(t) return;
postordervisit(right(t));
postordervisit(left(t);
process(t);
}
Esto visite la hoja o sub-nodos del árbol antes de visitar la raíz del sub-árbol.
Las banderas no son necesarios y deben ser evitados ya que un lector no debe modificar nada, y cualquier modificación no permitirían la concurrencia, por ejemplo. Aquí es una implementación de un orden post-iterativo traversal en C como una macro. Funciona para cualquier tipo de árbol con una configuración adecuada, y puede hacer también el post-orden inverso. toda la biblioteca, que también lleva a cabo un recorrido en preorden iterativo, es aquí .
#define W_TREE_FOR_EACH_POSTORDER(T,Child,self) \
W_DECLARE(W_CAT(Child,po1), T *Child) \
W_DECLARE(W_CAT(Child,po2), T* W_ID(node) = (self)) \
W_DECLARE(W_CAT(Child,po3), T** W_ID(stack) = NULL ) \
W_DECLARE(W_CAT(Child,po9), int W_ID(_finish_) = 0 ) \
if (W_ID(node) == NULL) \
; \
else \
W_BEFORE(W_CAT(Child,po4), goto W_LABEL(6,Child); ) \
while (!W_ID(_finish_)) \
W_BEFORE (W_CAT(Child,po5), \
W_LABEL(6,Child): \
while (W_ID(node)) { \
BOOST_PP_IF(W_REVERSED, \
W_TREE_FOR_EACH_IMMEDIATE_REVERSED(T,W_CAT(Child,_child), W_ID(node)) \
if (W_CAT(Child,_child,_ix) < W_TREE_GET_DEGREE(W_ID(node))-1) \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_CAT(Child,_child) ); \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) ); \
W_ID(node) = W_TREE_NEXT_RIGHTMOST(W_ID(node)); \
, /* else */ \
W_TREE_FOR_EACH_IMMEDIATE(T,W_CAT(Child,_child), W_ID(node)) \
if (W_CAT(Child,_child,_ix) > 0) \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_CAT(Child,_child) ); \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) ); \
W_ID(node) = W_TREE_NEXT_LEFTMOST(W_ID(node)); \
) \
} \
W_ID(node) = W_DYNAMIC_STACK_POP( W_ID(stack) ); \
BOOST_PP_IF(W_REVERSED, \
if (W_ID(node) && W_TREE_NEXT_LEFTMOST(W_ID(node)) \
&& W_DYNAMIC_STACK_PEEK_SAFE(W_ID(stack),NULL) == W_TREE_NEXT_LEFTMOST(W_ID(node)) ) { \
W_DYNAMIC_STACK_POP(W_ID(stack)); \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) ); \
W_ID(node) = W_TREE_NEXT_LEFTMOST(W_ID(node)); \
goto W_LABEL(6,Child); \
} \
, /* else */ \
if (W_ID(node) && W_TREE_NEXT_RIGHTMOST(W_ID(node)) \
&& W_DYNAMIC_STACK_PEEK_SAFE(W_ID(stack),NULL) == W_TREE_NEXT_RIGHTMOST(W_ID(node)) ) { \
W_DYNAMIC_STACK_POP(W_ID(stack)); \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) ); \
W_ID(node) = W_TREE_NEXT_RIGHTMOST(W_ID(node)); \
goto W_LABEL(6,Child); \
} \
) \
Child = W_ID(node); \
W_ID(node) = NULL; \
) \
W_AFTER(W_CAT(Child,po8), \
W_ID(_finish_) = W_DYNAMIC_STACK_IS_EMPTY(W_ID(stack)); \
if (W_ID(_finish_)) \
W_DYNAMIC_STACK_FREE(W_ID(stack)); \
) \
/**/
Se puede utilizar como esto . Para obtener invertido después de la orden, redefinir W_REVERSED a 1. Para cambiar el campo siguiente operación FETCH, redefinir W_TREE_NEXT(tree,ix) y para los árboles de grado variadic, redefinir W_TREE_GET_DEGREE(tree).
#include <wondermacros/tree/for_each.h>
struct bintree {
struct bintree* next[2];
const char* value;
};
struct bintree* root = ...
W_TREE_FOR_EACH_POSTORDER(struct bintree, node, root) {
printf("%s\n", node->value);
}
