Travessal de ordem pós -ordem iterativa sem manter a bandeira visitada
https://stackoverflow.com/questions/1350311
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Por que é necessário manter a bandeira visitada para travessia de pós -ordem iterativa e não para travessia iterativa de ordem ou pré -ordem.
É possível fazer travessia de pós -ordem sem manter a bandeira visitada?
Solução
Aqui está uma visita de pós-ordem:
postordervisit(t)
{ if not(leaf(t))
{ postordervisit(left(t);
postordervisit(right(t));
}
L1: process(t);
L2:
}
Não usa sinalizadores. Por que você acha que uma bandeira é necessária?
Talvez eu não entenda a frase "Traversal iterativa de pós -ordem". Por simetria, se você acha que "Traversal de pré-encomenda iterativa" não precisa de uma bandeira, afirmo que teria que acreditar "Traversal iterative Postorder Traversal" também é livre de bandeira e vice-versa.
EDIT: Meu mal, deve estar tarde da noite. "Iterative" Significado "implementar sem recursão". Ok, então você implementa sua própria pilha de nós, e Você deve implementar o que equivale a uma pilha de endereços de retorno. Eu acho que a bandeira está simulando o efeito do endereço de retorno, sabendo se deve ir para L1 ou L2 em seguida. E como você precisa disso para ordem postal, por simetria, você precisa para pré-encomenda.
EDITO OUTUBRO DE 2010: Meu mau novamente, o algoritmo fornecido não foi pós-ordem. Revisado.
Outras dicas
A versão iterativa travessia da Postome pode ser implementada sem o uso de sinalizadores visitados, é apenas mais difícil de implementar.
Veja aqui duas soluções para travessias iterativas do Postorder sem usar nenhum sinalizador visitado.
http://www.leetcode.com/2010/10/binary-tree-post-order-traversal.html
Se começarmos com o simples algoritmo de pós -encomenda recursivo,
def postorder1(node, f):
# a:
if node is None:
return None
postorder1(node.left, f)
# b:
postorder1(node.right, f)
# c:
f(node)
Podemos cortar a função em três partes "A", "B" e "C" e depois traduzi -la ingenuamente em um algoritmo iterativo, emulando uma pilha de chamadas 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 disso, observamos que a pilha só pode ser modificada de uma de três maneiras:
[…, a] → […, b, a]
[…, b] → […, c, a]
[…, c] → […]
Isso implica que:
- "A" só pode aparecer no máximo uma vez no topo da pilha, enquanto
- "B" e "C" e aparecem várias vezes no meio da pilha, possivelmente intercaladas.
Portanto, realmente não precisamos armazenar "A" dentro da pilha - uma única variável para armazenar "a" seria suficiente. Isso nos permite simplificar o algoritmo iterativo ingênuo na forma mais 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
A bandeira booleana na pilha é a "bandeira visitada". Neste exemplo, não armazenamos a bandeira diretamente nos nós, mas dentro da nossa pilha, mas o efeito líquido é o mesmo. Algumas variantes do algoritmo usam uma variável "último nó visitada", mas isso requer uma maneira de comparar nós para "identidade" (igualdade de ponteiro/referência), que não assumimos aqui.
Esta bandeira é um essencial Parte do algoritmo porque, como observado em nossa análise anteriormente, as entradas "B" e "C" na pilha podem aparecer de maneiras completamente arbitrárias. Nós precisamos algum tipo de informação para nos dizer se devemos atravessar para a direita ou ligar f.
Encontrei um problema na solução do usuário 1337C0D3R: É simplesmente uma pré-venda em ordem inversa. Minha solução usa uma "lista ativa" para marcar os nós na pilha.
(Você pode armazenar a bandeira da marca na pilha. Publicará essa solução separadamente.)
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;
};
Acredito que o show de algoritmos na postagem anterior para o Traversal da Ordem de Porto está em como "processa" o nó antes de visitar a sub-árvore esquerda. A Traversal da Postlears é essencialmente a mesma que a notação de polimento reverso em que os operando (nós da folha ou sub-árvores) precedem o operador (o próximo nó de sub-tree mais alto).
Um Algorith Traversal corrigido seria:
postordervisit(t)
{ if null(t) return;
postordervisit(right(t));
postordervisit(left(t);
process(t);
}
Isso visitaria os nós de folha ou sub-árvore antes de visitar a raiz da sub-árvore.
Os sinalizadores não são necessários e devem ser evitados, pois um leitor não deve modificar nada, e qualquer modificação não permitiria simultaneidade, por exemplo. Aqui é uma implementação de uma travessia de pós-ordem iterativa em C como uma macro. Funciona para qualquer tipo de árvore com configuração adequada e pode fazer também a ordem de pós-venda invertida. Toda a biblioteca, que também implementa uma travessia de pré-encomenda iterativa, é aqui.
#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)); \
) \
/**/
Isso pode ser usado assim. Para ser revertido após a ordem, redefinir W_REVERSED para 1. Para alterar a próxima operação de busca de campo, redefinir W_TREE_NEXT(tree,ix) e para árvores de grau variadas, 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);
}
