Iterative Post Order -Durchquerung, ohne die besuchte Flagge zu halten
https://stackoverflow.com/questions/1350311
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Warum ist es notwendig, die besuchte Flagge für iterative Post -Bestellungen zu halten, und nicht für die Iterative für die unberührte oder vorbestellung.
Ist es möglich, postbestellverluste zu machen, ohne die besuchte Flagge zu halten?
Lösung
Hier ist ein Besuch nach der Bestellung:
postordervisit(t)
{ if not(leaf(t))
{ postordervisit(left(t);
postordervisit(right(t));
}
L1: process(t);
L2:
}
Es verwendet keine Flaggen. Warum ist Ihrer Meinung nach eine Flagge notwendig?
Vielleicht verstehe ich den Ausdruck "iterativen Postauftrags -Traversal" nicht. Wenn Sie nach Symmetrie glauben, dass "iterativer Vorbestellungen" keine Flagge benötigt, müsste Sie glauben, dass "iterativer Postreiztraversal" ebenfalls frei und umgekehrt ist.
EDIT: Mein schlechtes, muss spät in der Nacht sein. "Iterativ" bedeutet "Implementierung ohne Rekursion". Ok, also implementieren Sie Ihren eigenen Stapel Knoten. und Sie müssen implementieren, was zu einem Stapel von Rückgabedressen beträgt. Ich denke, die Flagge simuliert die Auswirkung der Rückgabemitteladresse, wenn man weiß, ob sie als nächstes zu L1 oder L2 gehen soll. Und da Sie dies für die Postbestellung benötigen, benötigen Sie es nach Symmetrie für Vorbestellungen.
Bearbeiten Oktober 2010: Mein schlechtes, der bereitgestellte Algorithmus war nicht nach der Bestellung. Überarbeitet.
Andere Tipps
Die iterative Version der postorder -durchführenden Version könnte implementiert werden, ohne besuchte Flags zu verwenden. Es ist nur schwieriger zu implementieren.
Hier finden Sie zwei Lösungen für den Iterativen Postorder -Durchlauf ohne Verwendung von besuchten Flags.
http://www.leetcode.com/2010/10/binary--post-order-traversal.html
Wenn wir mit dem einfachen rekursiven Postorderalgorithmus beginnen,
def postorder1(node, f):
# a:
if node is None:
return None
postorder1(node.left, f)
# b:
postorder1(node.right, f)
# c:
f(node)
Wir können die Funktion in drei Teile "A", "B" und "C" hacken und sie dann naiv in einen iterativen Algorithmus übersetzen, indem sie einen virtuellen Anrufstapel emulieren:
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)
Daraus beobachten wir, dass der Stapel nur auf drei Arten modifiziert werden kann:
[…, a] → […, b, a]
[…, b] → […, c, a]
[…, c] → […]
Dies impliziert das:
- "a" kann nur erscheinen höchstens einmal oben am Stapel, wohingegen
- "B" und "C" und erscheinen in der Mitte des Stapels, möglicherweise verschachtelt.
Daher müssen wir nicht wirklich "einen" im Stapel speichern - eine einzige Variable, die "A" speichern würde, würde ausreichen. Dies ermöglicht es uns, den naiven iterativen Algorithmus in die konventionellere Form zu vereinfachen:
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
Die Boolesche Flagge auf dem Stapel ist die „besuchte Flagge“. In diesem Beispiel speichern wir das Flag nicht direkt auf den Knoten, sondern in unserem Stapel, aber der Nettoeffekt ist der gleiche. Einige Varianten des Algorithmus verwenden stattdessen eine "zuletzt besuchte Knotenvariable". Dies erfordert jedoch eine Möglichkeit, Knoten für „Identität“ (Zeiger-/Referenzgleichheit) zu vergleichen, die wir hier nicht annehmen.
Diese Flagge ist eine wesentlich Ein Teil des Algorithmus, weil, wie in unserer Analyse zuvor erwähnt wurde, die Einträge von "B" und "C" am Stapel auf völlig willkürliche Weise erscheinen können. Wir brauchen etwas Art von Informationen, um uns zu sagen, ob wir nach rechts fahren oder anrufen sollten f.
Ich fand ein Problem in der Lösung des Benutzers 1337C0D3R: Es ist einfach eine Vorbestellung in umgekehrter Reihenfolge. Meine Lösung verwendet eine "aktive Liste", um die Knoten im Stapel zu markieren.
(Sie können das Mark -Flag im Stapel speichern. Wird diese Lösung separat veröffentlichen.)
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;
};
Ich glaube, der Algorithmus wird in früheren Posting für den Durchlauf von Port-Order angezeigt, da er den Knoten "verarbeitet", bevor er den linken Unterbaum besucht. Der postorderische Traversal ist im Wesentlichen die gleiche wie umgekehrte polnische Notation, bei der die Operanden (Blattknoten oder Unterbäume) dem Bediener vorausgehen (der nächste höhere Unterbaumknoten).
Ein korrigierter Postorder -Traversal -Algorith wäre:
postordervisit(t)
{ if null(t) return;
postordervisit(right(t));
postordervisit(left(t);
process(t);
}
Dies würde die Blatt- oder Unterbaumknoten besuchen, bevor sie die Wurzel des Unterbaums besuchen.
Flags sind nicht notwendig und sollten vermieden werden, da ein Leser nichts ändern sollte und eine Änderung beispielsweise keine Parallelität zulässt. Hier ist eine Implementierung einer iterativen Nachbestellung in C als Makro. Es funktioniert für jeden Baumtyp mit ordnungsgemäßer Konfiguration und kann auch die umgekehrte Post-Ordnung ausführen. Die gesamte Bibliothek, die auch einen iterativen Vorbestellungen implementiert, ist hier.
#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)); \
) \
/**/
Es kann benutzt werden so was. Um nach der Bestellung umgekehrt zu werden, definieren Sie neu W_REVERSED bis 1. Um den nächsten Feld abzuwechseln, definieren Sie neu W_TREE_NEXT(tree,ix) und für variadische Bäume definieren neu 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);
}
