1

inorder または pre-order 反復トラバーサルではなく、反復ポスト オーダー トラバーサルの Visited フラグを保持する必要があるのはなぜですか。

訪問済みフラグを保持せずにポストオーダートラバーサルを行うことは可能ですか?

4

6 に答える 6

3

ポストオーダートラバーサル反復バージョンは、訪問済みフラグを使用せずに実装できますが、実装はさらに困難です。

訪問済みフラグを使用せずに反復的なポストオーダートラバーサルを行うための2つのソリューションについては、ここを参照してください。

http://www.leetcode.com/2010/10/binary-tree-post-order-traversal.html

于 2010-10-28T22:12:31.933 に答える
0

私はユーザー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;
};
于 2011-03-01T23:41:01.070 に答える
0

左のサブツリーにアクセスする前にノードを「処理」するため、ポート順トラバーサルの以前の投稿で示されたアルゴリズムが含まれていると思います。Postorder Traversal は、オペランド (リーフ ノードまたはサブツリー) が演算子 (次に高いサブツリー ノード) の前にある逆ポーランド記法と本質的に同じです。

修正された postorder トラバーサル アルゴリズムは次のようになります。

postordervisit(t)
{   if null(t) return;    
    postordervisit(right(t));
    postordervisit(left(t);
    process(t);
}

これは、サブツリーのルートにアクセスする前に、リーフ ノードまたはサブツリー ノードにアクセスします。

于 2009-11-14T17:10:47.710 に答える
0

注文後の訪問は次のとおりです。

postordervisit(t)
{   if not(leaf(t))
    { postordervisit(left(t);
      postordervisit(right(t));
    }
L1: process(t);
        L2:
}

フラグは使用しません。なぜ旗が必要だと思いますか。

「反復的なポスト オーダー トラバーサル」というフレーズが理解できないかもしれません。対称的に、「反復的な事前順序トラバーサル」にフラグが必要ないと考える場合、「反復的な事後順序トラバーサル」もフラグなしであると信じなければならないと私は主張します。逆もまた同様です。

編集: 私の悪い、夜遅くする必要があります。「繰り返し」は「再帰なしで実装する」ことを意味します。では、独自のノード スタックを実装し、リターン アドレスのスタックに相当するものを実装する必要があります。フラグは、次に L1 に行くか L2 に行くかを知っている戻りアドレスの効果をシミュレートしていると思います。そして、これはポストオーダーに必要なので、対称性により、プレオーダーに必要です.

EDIT 2010 年 10 月: 繰り返しになりますが、提供されたアルゴリズムはポスト オーダーではありませんでした。改訂。

于 2009-08-29T03:04:47.397 に答える
0

リーダーは何も変更してはならないため、フラグは不要であり、回避する必要があります。たとえば、変更すると同時実行が許可されません。以下は、マクロとしての 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));                                         \
            )                                                                                  \
            /**/

こんな感じで使えます。逆のポストオーダーを取得するには、1 に再定義W_REVERSEDします。次のフィールド フェッチ操作を変更するには、再定義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);
}
于 2019-03-11T07:35:37.570 に答える