訪問済みフラグを保持しない反復的なポストオーダートラバーサル
https://stackoverflow.com/questions/1350311
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
インオーダーまたはプレオーダーの反復トラバーサルではなく、ポストオーダーの反復トラバーサルに対して訪問済みフラグを保持する必要があるのはなぜですか。
訪問済みフラグを保持せずにポストオーダートラバーサルを行うことは可能ですか?
解決
注文後の訪問は次のとおりです。
postordervisit(t)
{ if not(leaf(t))
{ postordervisit(left(t);
postordervisit(right(t));
}
L1: process(t);
L2:
}
フラグは使用しません。なぜ旗が必要だと思いますか?
おそらく私は、「反復的なポストオーダートラバーサル」という言葉を理解していません。対称性により、「反復的な予約注文トラバーサル」にはフラグが必要でないと思われる場合、「反復ポストオーバートラバーサル」もフラグがないと信じなければならないと主張します。
編集：悪いけど、もう夜遅いはずだ。「反復」とは「再帰なしで実装する」という意味です。OK、それでは独自のノードのスタックを実装します。 そして リターンアドレスのスタックに相当するものを実装する必要があります。このフラッグは、リターンの効果をシミュレートしているのだと思う。 次にL1に行くかL2に行くかを決める。そして、これは事後注文に必要なので、対称性により、事前注文にも必要になります。
2010 年 10 月編集:残念なことに、提供されたアルゴリズムはポストオーダーではありませんでした。改訂。
他のヒント
ポストオーダー トラバーサルの反復バージョンは、訪問済みフラグを使用せずに実装できますが、実装がより困難になるだけです。
訪問済みフラグを使用せずに反復的な事後順序トラバーサルを行うための 2 つのソリューションについては、こちらを参照してください。
http://www.leetcode.com/2010/10/binary-tree-post-order-traversal.html
単純な再帰事後順序アルゴリズムから始めると、
def postorder1(node, f):
# a:
if node is None:
return None
postorder1(node.left, f)
# b:
postorder1(node.right, f)
# c:
f(node)
関数を「a」、「b」、「c」の 3 つの部分に分割し、仮想コール スタックをエミュレートすることで単純に反復アルゴリズムに変換できます。
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)
このことから、スタックは次の 3 つの方法のいずれかでのみ変更できることがわかります。
[…, a] → […, b, a]
[…, b] → […, c, a]
[…, c] → […]
これは次のことを意味します:
- 「a」のみが表示されます スタックの一番上に一度だけ, 、 一方
- 「b」と「c」は、スタックの中央に何度でも出現し、場合によってはインターリーブされます。
したがって、実際にはスタック内に「a」を格納する必要はありません。「a」を格納する単一の変数で十分です。これにより、単純な反復アルゴリズムをより従来的な形式に単純化できます。
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
スタック上のブール型フラグは「訪問済みフラグ」です。この例では、フラグをノードに直接保存せず、スタック内に保存しますが、最終的な効果は同じです。アルゴリズムの一部の変形では、代わりに「最後に訪問したノード」変数を使用しますが、それにはノードの「同一性」(ポインタ/参照の等価性) を比較する方法が必要ですが、ここではそれを想定しません。
この旗は、 不可欠 これはアルゴリズムの一部であるため、以前の分析で述べたように、スタック上の "b" および "c" エントリは完全に任意の方法で出現する可能性があります。必要です いくつかの 右方向にトラバースすべきか、電話をかけるべきかを教えてくれる情報のようなもの f.
ユーザーのソリューションに問題が見つかりました 1337c0d3r:それは単に逆の順序で予約注文するだけです。私のソリューションでは、「アクティブ リスト」を使用してスタック内のノードをマークします。
(マークフラグをスタックに保存できます。その解決策は別途投稿します。）
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;
};
以前の投稿でポート順序トラバーサルについて示したアルゴリズムは、左側のサブツリーにアクセスする前にノードを「処理」するものであると思います。ポストオーダー トラバーサルは基本的に逆ポーランド記法と同じで、オペランド (リーフ ノードまたはサブツリー) が演算子 (次に高いサブツリー ノード) の前にあります。
修正された事後探索アルゴリズムは次のようになります。
postordervisit(t)
{ if null(t) return;
postordervisit(right(t));
postordervisit(left(t);
process(t);
}
これにより、サブツリーのルートにアクセスする前に、リーフまたはサブツリーのノードにアクセスします。
たとえば、リーダーは何も変更すべきではなく、変更すると同時実行が許可されないため、フラグは必要ではなく、使用しないようにする必要があります。 ここ これは、C での反復的なポストオーダー トラバーサルをマクロとして実装したものです。これは、適切な構成を備えた任意のツリー タイプで機能し、ポストオーダーを逆にすることもできます。ライブラリ全体は、反復的な事前順序トラバーサルも実装しており、次のようになります。 ここ.
#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)); \
) \
/**/
使用できます このような. 。事後順序を逆転するには、再定義します W_REVERSED 1に。次のフィールドフェッチ操作を変更するには、再定義します。 W_TREE_NEXT(tree,ix) 可変次数ツリーの場合は、再定義します 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);
}
