방문 깃발을 유지하지 않고 반복적 인 사후 주문
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 년 10 월 편집 : 다시 나쁘게, 제공된 알고리즘은 사후 주문이 아닙니다. 수정.
다른 팁
포스트 주문 트래버스 반복 버전은 방문한 플래그를 사용하지 않고 구현할 수 있습니다. 구현하기가 더 어렵습니다.
방문한 깃발을 사용하지 않고 반복 우편 주문형 순서를위한 두 가지 솔루션은 여기를 참조하십시오.
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] → […]
이것은 다음을 의미합니다.
- "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
스택의 부울 깃발은 "방문 된 깃발"입니다. 이 예에서는 플래그를 노드에 직접 저장하지 않지만 스택 안에는 순 효과가 동일합니다. 알고리즘의 일부 변형은 대신 "마지막으로 방문한 노드"변수를 사용하지만 여기에서 가정하지 않는 "Identity"(포인터/참조 평등)의 노드를 비교하는 방법이 필요합니다.
이 깃발은 an입니다 필수적인 이전 분석에서 언급 한 바와 같이 스택의 "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;
};
포트 주문 Traversal에 대한 이전 게시물에서 알고리즘 쇼가 왼쪽 하위 트리를 방문하기 전에 노드를 "프로세스"하기 때문에 표시됩니다. 포스트 주문 트래버스는 기본적으로 오페라 (잎 노드 또는 하위 트리)가 연산자 (다음 상위 하위 트리 노드)보다 우선하는 역 광택 표기법과 동일합니다.
수정 된 우편 주문형 트래버스 알고리즘은 다음과 같습니다.
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);
}
