Iterativo traversal ordine post senza mantenere visitato bandiera
https://stackoverflow.com/questions/1350311
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Perché è necessario per mantenere la bandiera visitato per iterativa traversal ordine postale e non per ordine simmetrico o pre ordine attraversamento iterativo.
E 'possibile fare dopo traversal ordine senza tenere bandiera visitato?
Soluzione
Ecco una visita post-ordine:
postordervisit(t)
{ if not(leaf(t))
{ postordervisit(left(t);
postordervisit(right(t));
}
L1: process(t);
L2:
}
Non usa alcun flag. Perché pensi che una bandiera è necessaria?
Forse non capisco la frase, "iterativo posta ordine di attraversamento". Per simmetria, se si pensa che "preordine attraversamento iterativo" non ha bisogno di una bandiera, I conti si avrebbe a credere "iterativo traversal postorder" è anche libera bandiera, e viceversa.
EDIT: Il mio male, deve essere a tarda notte. "Iterativo" che significa "attuare senza ricorsione". OK, in modo da implementare il proprio stack di nodi, e è necessario implementare ciò che equivale a una pila di indirizzi di ritorno. Credo che la bandiera sta simulando l'effetto del ritorno affrontare sapendo se andare a L1 o L2 successivo. E dal momento che avete bisogno di questo per ordine post, per simmetria ne avete bisogno per il pre-ordine.
EDIT ottobre 2010: Il mio male di nuovo, l'algoritmo fornito non era post-ordine. Revised.
Altri suggerimenti
versione iterativa postorder attraversamento potrebbe essere attuato senza l'utilizzo di bandiere visitati, è solo più difficile da attuare.
Vedi qui per due soluzioni per iterativa attraversamento postorder senza l'uso di bandiere visitati.
http://www.leetcode.com/ 2010/10 / binary-tree-post-ordine-traversal.html
Se cominciamo con il semplice algoritmo ricorsivo postorder,
def postorder1(node, f):
# a:
if node is None:
return None
postorder1(node.left, f)
# b:
postorder1(node.right, f)
# c:
f(node)
possiamo tagliare la funzione in tre parti "a", "b" e "c", e quindi ingenuamente tradurlo in un algoritmo iterativo emulando uno stack chiamata virtuale:
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)
Da questo si osserva che la pila può essere modificato solo in uno dei tre modi:
[…, a] → […, b, a]
[…, b] → […, c, a]
[…, c] → […]
Ciò implica che:
- un "" può apparire solo al massimo una volta in cima alla pila , mentre
- "b" e "c" e apparire qualsiasi numero di volte in mezzo stack, possibilmente intercalata.
Quindi, noi non realmente bisogno di memorizzare "a" all'interno della pila - una singola variabile per memorizzare "a" sarebbe sufficiente. Questo ci permette di semplificare l'algoritmo iterativo ingenuo nella forma più convenzionale:
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
Il flag booleano sullo stack è la “bandiera visitato”. In questo esempio, non archiviamo la bandiera direttamente sui nodi, ma all'interno il nostro stack, ma l'effetto netto è lo stesso. Alcune varianti dell'algoritmo di utilizzare un “Ultima visita nodo” variabile, invece, ma che richiede un modo per confrontare i nodi per “identità” (puntatore / uguaglianza di riferimento), che non ci assumiamo qui.
Questa bandiera è un essenziale parte dell'algoritmo, perché, come notato nella nostra precedente analisi, la "b" e "c" voci sullo stack può apparire in modi completamente arbitrari. Abbiamo bisogno di alcuni tipo di informazioni di dirci se dobbiamo attraversare verso destra o chiamare f.
Ho trovato un problema nella soluzione di utente 1337c0d3r : si tratta semplicemente di un pre-ordine in ordine inverso. La mia soluzione utilizza una "lista attiva" per contrassegnare i nodi nello stack.
(è possibile memorizzare la bandiera segno nella pila. Pubblicheremo questa soluzione separatamente).
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;
};
Credo che lo spettacolo algoritmo in precedente post per la porta-ordine di attraversamento è come esso "processi" il nodo prima di visitare il sub-albero sinistro. Postorder attraversamento è essenzialmente lo stesso come Reverse Polish Notation in cui gli operandi (nodi foglia o sub-alberi) precedere l'operatore (superiore successivo nodo sub-tree).
Un corretto postorder attraversamento algoritmo potrebbe essere:
postordervisit(t)
{ if null(t) return;
postordervisit(right(t));
postordervisit(left(t);
process(t);
}
Ciò visitare i nodi foglia o sub-albero prima di visitare la radice del sotto-albero.
Bandiere non sono necessari e dovrebbero essere evitati dal momento che un lettore non deve modificare nulla, e ogni modifica non permetterebbero la concorrenza, per esempio. Qui è un'implementazione di un post-ordine iterativo attraversamento in C come macro. Funziona per qualsiasi tipo di albero con una corretta configurazione, e può fare anche il post-ordine inverso. L'intera libreria, che implementa anche un iterativo attraversamento pre-ordine, è qui .
#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)); \
) \
/**/
Può essere utilizzato come questo . Per ottenere invertito post-ordine, ridefinire W_REVERSED a 1. Per modificare il campo successivo recuperare il funzionamento, ridefinire W_TREE_NEXT(tree,ix) e per gli alberi di laurea variadic, ridefinire 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);
}
