Итеративный обход почтового заказа без сохранения флага посещения

Question

Почему необходимо сохранять флаг посещения для итеративного обхода после заказа, а не для итеративного обхода по порядку или по заказу.

Можно ли выполнить обход заказа без сохранения флага посещения?

Answer 1

Итеративная версия прохождения заказа может быть реализована без использования посещенных флагов, это просто сложнее реализовать.

См. Здесь два решения для итеративного обхода после заказа без использования посещенных флагов.

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

Answer 2

Если мы начнем с простого рекурсивного алгоритма пост-заказа,

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] → […]

Это означает, что:

• "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.

Answer 3

Флаги не нужны и их следует избегать, так как читатель не должен ничего изменять, а любая модификация, например, не допускает параллелизма. Здесь - это реализация итеративного обхода после заказа в 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);
}

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

Вот визит после заказа:

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

Флаги не используются. Как вы думаете, зачем нужен флаг?

Может быть, я не понимаю фразу "итеративный обход почтового заказа". По симметрии, если вы думаете, что «итеративный обход предзаказа» не нуждается в флаге, Я утверждаю, что вы должны верить, что «итеративный обход пост-заказа» также флаг свободен, и наоборот.

РЕДАКТИРОВАТЬ: мой плохой, должно быть, поздно ночью. «Итеративный», означающий «реализовать без рекурсии». Итак, вы реализуете свой собственный стек узлов, и , вы должны реализовать то, что равно сумме адресов возврата. Я думаю, что флаг имитирует эффект возврата адрес, зная, перейти ли к L1 или L2 дальше. И так как вам нужно это для почтового заказа, по симметрии вам это нужно для предварительного заказа.

РЕДАКТИРОВАТЬ Октябрь 2010 года: опять плохо, предоставленный алгоритм не был после заказа. Перераб.