问个问题post order traveral using interation - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个问题post order traveral using interation

问个问题post order traveral using interation# JobHunting - 待字闺中

l*r2010-03-08 08:03

1 楼

请教大家， post order traveral using interation ，怎么做最好呢？能不能在结
点里记录是否visit 过呢？
in-order 和pre-order的不用记录，但是post-order的还是没有想出来。

r*u2010-03-08 08:03

2 楼

current = root; //start traversal at root node
v = 0;
if(current is NULL)‏
the binary tree is empty
if(current is not NULL)‏
push current into stack;
push 1 onto stack;
current = current->llink;
while(stack is not empty)‏
if(current is not NULL and v is 0)‏
{
push current and 1 onto stack;
current = current->llink;
}

【在 l*********r 的大作中提到】

: 请教大家， post order traveral using interation ，怎么做最好呢？能不能在结
: 点里记录是否visit 过呢？
: in-order 和pre-order的不用记录，但是post-order的还是没有想出来。

B*t2010-03-08 08:03

3 楼

not tested code.
void postOrderTraveral(Node *root) {
stack s;
Node *pre, *cur;
cur = root;
while(!s.empty()||cur) {
while(cur) {
s.push(cur->right);
cur = cur->left;
}
cur = s.top();
if(cur==pre||cur->right==NULL) {
visit(cur);
pre = cur;
cur = NULL;
s.pop()
}
else cur = cur->left;
}
}

h*02010-03-08 08:03

4 楼

I guess LZ's meaning is to use "iteration"? but not "interaction"?

【在 l*********r 的大作中提到】

b*h2010-03-08 08:03

5 楼

用两个stack
void nonrec_postorder()
{
stack stk1;
stack stk2;
if(root != NULL)
stk1.push(root);
while(!stk1.empty()) {
Node* tmp = stk1.top();
stk1.pop();
stk2.push(tmp);
if(tmp->left != NULL)
stk1.push(tmp->left);
if(tmp->right != NULL)
stk1.push(tmp->right);
}
while(!stk2.empty()) {
printf("%d ", stk2.top()->ke

f*r2010-03-08 08:03

6 楼

Needs a stack & one per-element flag.
void postOrderTraversal(Tree *head) {
Stack s;
head->settag(0);
s.push(head);
while (!s.empty()) {
Tree *node = s.top();
if (node->left == NULL && node->right == NULL ||
node->tag() == 1) {
print node->value;
s.pop();
}
if (node->right != NULL) {
s.push(node->right);
}
if (node->left != NULL) {
s.push(node->left);
}
node->settag(1);
}
}

l*r2010-03-08 08:03

7 楼

哦，必须要用到per-order flag是吧，如果不用，有没有办法呢？

l*r2010-03-08 08:03

8 楼

哦，没有看到两个stack的solution. 好办法，谢谢。

l*s2010-03-08 08:03

9 楼

个人意见：
1) flag per node: 需要修改数据结构。当然，可以用 hash table来代替，但总觉得
不 elegant；
2）two stacks: 好主意，代码很好写，很 elegant。但用的空间相对多一些，至少是
O(n)
3）只用一个 stack，同时用一个 prev 表示前一个被打印的。代码也比较好写，就是
得判断一些 case，没有两个stack 来得漂亮。但空间相对少。如果树是 balanced的话
，只要 O(logn) [直观地，每个level最多只有2两个结点同时在栈中]。
4）在栈中设置一些特殊标志：当遇到特殊标志，我们就知道栈顶结点应该要打印了。
idea 很不错，直观，代码也好写， elegant。空间最好的情况也是 O(logn)。

【在 l*********r 的大作中提到】

: 哦，没有看到两个stack的solution. 好办法，谢谢。