Итеративный обход почтового порядка без сохранения посещенного флага
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:
}
Он не использует никаких флагов.Как вы думаете, зачем нужен флаг?
Возможно, я не понимаю фразу «итеративный обход почтового порядка».По симметрии, если вы думаете, что «обход итеративного предварительного заказа» не нуждается в флаге, я утверждаю, что вам нужно поверить, что «итеративное обход после заказа» также не содержит флага, а наоборот.
РЕДАКТИРОВАТЬ:Плохо, должно быть, поздно вечером.«Итеративный» означает «реализовать без рекурсии».Итак, вы реализуете свой собственный стек узлов. и вам нужно реализовать то, что представляет собой стек обратных адресов.Я думаю, что флаг моделирует эффект обратного адреса, зная, ходить ли на L1 или L2.А раз вам это нужно для постзаказа, то по симметрии оно вам нужно и для предзаказа.
РЕДАКТИРОВАТЬ Октябрь 2010 г.:Еще раз извините, предоставленный алгоритм не был пост-заказом.Пересмотрено.
Другие советы
Итеративную версию обхода постпорядка можно реализовать без использования посещенных флагов, просто ее сложнее реализовать.
Здесь представлены два решения для итеративного обхода постпорядка без использования посещенных флагов.
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», а затем наивно перевести ее в итерационный алгоритм, эмулируя виртуальный стек вызовов:
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» появляются любое количество раз в середине стека, возможно, чередуясь.
Следовательно, нам на самом деле не нужно хранить «а» внутри стека — достаточно одной переменной для хранения «а».Это позволяет нам упростить наивный итерационный алгоритм до более традиционной формы:
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);
}
