اجتياز ترتيب ما بعد الترتيب التكراري دون الاحتفاظ بالعلم الذي تمت زيارته

Question

لماذا من الضروري الاحتفاظ بالعلم الذي تم زيارته لتجاوز الترتيب التكراري وليس للمرور التكراري أو المسبق.

هل من الممكن القيام بعبارة ما بعد الطلب دون الاحتفاظ بالعلم المزيف؟

Answer 1

إليك زيارة ما بعد الطلب:

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

لا يستخدم أي أعلام. لماذا تعتقد أن العلم ضروري؟

ربما لا أفهم العبارة ، "اجتياز الترتيب التكراري". من خلال التماثل ، إذا كنت تعتقد أن "اجتياز التكراري المسبق" لا يحتاج إلى علامة ، فأنا أؤكد أنه يتعين عليك أن تصدق أن "اجتياز Postorder التكراري" خالٍ من العلم ، والعكس بالعكس.

تحرير: سيئتي ، يجب أن تتأخر في الليل. "التكرار" المعنى "تنفيذ دون عودة". حسنًا ، لذلك تقوم بتنفيذ مجموعة العقد الخاصة بك ، و يجب عليك تنفيذ ما يصل إلى مجموعة من عناوين الإرجاع. أعتقد أن العلم يحاكي تأثير عنوان الإرجاع مع العلم ما إذا كان سيتم الذهاب إلى L1 أو L2 التالي. وبما أنك بحاجة إلى هذا للترتيب الناشر ، فأنت في التماثل تحتاجه للطلب المسبق.

تحرير أكتوبر 2010: سيئتي مرة أخرى ، لم تكن الخوارزمية المقدمة بعد الطلب. مراجعة.

Answer 2

يمكن تنفيذ إصدار Postorder Traversal التكراري دون استخدام الأعلام التي تمت زيارتها ، فمن الصعب تنفيذها.

انظر هنا للحصول على حلين لتجاوز Postorder التكراري دون استخدام أي أعلام زيارة.

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

Answer 3

إذا بدأنا بخوارزمية ما بعد الحدود العودية البسيطة ،

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" ، ثم ترجمتها بسذاجة إلى خوارزمية تكرارية عن طريق محاكاة مكدس مكالمة افتراضية:

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)

من هذا نلاحظ أنه لا يمكن تعديل المكدس إلا في واحدة من ثلاث طرق:

[…, a] → […, b, a]
[…, b] → […, c, a]
[…, c] → […]

وهذا يعني أن:

• "أ" يمكن أن تظهر فقط على الأكثر مرة في الجزء العلوي من المكدس, ، بينما
• "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.

Answer 4

لقد وجدت مشكلة في حل المستخدم 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;
};

Answer 5

أعتقد أن عرض الخوارزمية في النشر السابق لالتقاط المنفذ هو "يعالج" العقدة قبل زيارة الشجرة الفرعية اليسرى. يعد اجتياز Postorder هو نفس الترميز البولندي العكسي الذي تسبق فيه المعاملات (العقد الأوراق أو الأشجار الفرعية) المشغل (عقدة الشجرة الفرعية الأعلى التالية).

ستكون خوارزف اجتياز ما بعد الحدود المصححة:

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

هذا من شأنه أن يزور العقد الأوراق أو الشجرة الفرعية قبل زيارة جذر الشجرة الفرعية.

Answer 6

الأعلام ليست ضرورية ويجب تجنبها لأن القارئ يجب ألا يعدل أي شيء ، ولن يسمح أي تعديل بالتزامن ، على سبيل المثال. هنا هو تنفيذ اجتياز ما بعد الترتيب التكراري في 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);
}