après l'ordre traversal itératives sans garder le drapeau visité
https://stackoverflow.com/questions/1350311
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Pourquoi est-il nécessaire de garder le drapeau visité pour traversal de commande post itérative et non pour l'ordre afinde ou pré traversal itérative.
Est-il possible de le faire après l'ordre traversal sans garder le drapeau visité?
La solution
Voici une visite post-commande:
postordervisit(t)
{ if not(leaf(t))
{ postordervisit(left(t);
postordervisit(right(t));
}
L1: process(t);
L2:
}
Il n'utilise pas de drapeaux. Pourquoi pensez-vous qu'un drapeau est nécessaire?
Peut-être que je ne comprends pas la phrase, « post itérative ordre traversal ». Par symétrie, si vous pensez que « itérative précommande traversal » n'a pas besoin d'un drapeau, Je soutiens que vous auriez à croire « itérative postorder traversal » est également drapeau libre, et vice-versa.
EDIT: Mon mauvais, doit être tard dans la nuit. « Itératifs » qui signifie « mettre en œuvre sans récursion ». OK, donc vous implémentez votre propre pile de noeuds, et vous avez à mettre en œuvre ce qui équivaut à une pile d'adresses de retour. Je pense que le drapeau simule l'effet du retour répondre à savoir si d'aller à L1 ou L2 suivant. Et puisque vous en avez besoin pour ordre post, par symétrie dont vous avez besoin pour pré-commande.
EDIT Octobre 2010: Mon nouveau mal, l'algorithme n'a pas été fourni après l'ordre. Révisée.
Autres conseils
Postorder traversal version itérative pourrait être mise en œuvre sans utiliser des drapeaux visités, il est un peu plus difficile à mettre en œuvre.
Voir ici pour deux solutions pour traversal postorder itérative sans utiliser de drapeaux visités.
http://www.leetcode.com/ 2010/10 / arbre binaire post-ordre traversal.html
Si nous commençons par l'algorithme simple postorder récursive,
def postorder1(node, f):
# a:
if node is None:
return None
postorder1(node.left, f)
# b:
postorder1(node.right, f)
# c:
f(node)
on peut couper la fonction en trois parties « a », « b » et « c », puis traduire en un naïvement algorithme itératif par une pile d'émulant appel virtuel:
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)
De là, nous observons que la pile ne peut être modifié dans l'une des trois façons suivantes:
[…, a] → […, b, a]
[…, b] → […, c, a]
[…, c] → […]
Ceci implique que:
- "a" ne peut apparaître que au plus une fois au sommet de la pile , alors que
- « b » et « c » et apparaître un certain nombre de fois dans le milieu de la pile, éventuellement entrelacées.
Par conséquent, nous ne avons pas vraiment besoin de stocker « un » à l'intérieur de la pile - une seule variable pour stocker « un » serait suffisant. Cela nous permet de simplifier l'algorithme itératif naïve dans la forme plus conventionnelle:
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
Le drapeau booléen sur la pile est le « drapeau visité ». Dans cet exemple, nous ne stockons pas le drapeau directement sur les nœuds, mais dans notre pile, mais l'effet net est le même. Certaines variantes de l'algorithme utilisent un « dernier nœud visité » variable à la place, mais cela nécessite un moyen de comparer les noeuds pour « identité » (pointeur / égalité de référence), que nous ne supposons pas ici.
Ce drapeau est un essentiel de l'algorithme car, comme il est indiqué dans notre précédente analyse, les entrées « b » et « c » sur la pile peut apparaître de manière complètement arbitraire. Nous avons besoin certains genre d'information pour nous dire que nous devrions traverser ou appeler f droite.
J'ai trouvé un problème dans la solution de l'utilisateur 1337c0d3r : il est tout simplement une précommande dans l'ordre inverse. Ma solution utilise une « liste active » pour marquer les noeuds dans la pile.
(Vous pouvez stocker le drapeau de la marque dans la pile. Signalera cette solution séparément.)
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;
};
Je crois que le spectacle de l'algorithme dans l'affichage précédent pour traversal port est en ordre comme il « processus » le nœud avant de visiter le sous-arbre gauche. Postorder Traversal est essentiellement la même que la notation polonaise inverse, dans lequel les opérandes (noeuds de feuille ou sous-arbres) précéder l'opérateur (le prochain noeud de sous-arbre supérieur).
Une correction postorder traversal algorith serait:
postordervisit(t)
{ if null(t) return;
postordervisit(right(t));
postordervisit(left(t);
process(t);
}
visiterait les feuilles ou les nœuds sous-arbre avant de se rendre à la racine du sous-arbre.
Les drapeaux ne sont pas nécessaires et doivent être évités car un lecteur ne doit pas modifier quoi que ce soit, et toute modification ne permettrait pas à la concurrence, par exemple. est une mise en œuvre d'un ordre post-itérative traversal en C comme une macro. Il fonctionne pour tout type d'arbre avec une bonne configuration, et peut aussi faire le post-ordre inverse. La bibliothèque entière, qui met également en œuvre une traversal précommande itérative, est .
#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)); \
) \
/**/
Il peut être utilisé comme celui-ci . Pour obtenir inversé après ordre, redéfinir W_REVERSED à 1. Pour modifier le champ suivant l'opération Fetch, redéfinir W_TREE_NEXT(tree,ix) et pour les arbres de degré variadique, redéfinir 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);
}
