Cormen星号题:O(n)遍历二叉树,只能用O(1) extra space - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

Cormen星号题:O(n)遍历二叉树,只能用O(1) extra space

Cormen星号题:O(n)遍历二叉树,只能用O(1) extra space# Programming - 葵花宝典

e*e2008-07-11 07:07

1 楼

http://www.springerlink.com/content/x844231386773014/
"Supporting OpenMP on Cell "
Please mail to e****[email protected]
thanks

i*h2008-07-11 07:07

2 楼

这个是那本算法书二叉树一节后的题
网上查了下,除非节点带对父节点的指针才行,好象作弊了(这个额外的指针就是O(n)空
间了)
有答案么?
谢谢

N*d2008-07-11 07:07

3 楼

【在 e***e 的大作中提到】

: http://www.springerlink.com/content/x844231386773014/
: "Supporting OpenMP on Cell "
: Please mail to e****[email protected]
: thanks

c*t2008-07-11 07:07

4 楼

If the tree can be modified...
/ \ are downward arrows, * is the upward arrow, stored in either left
or right branch.
root := A
A
/ \
B C
/ \
D E
1.
A
* \
B C
/ \
D E
2.
A
* \
B C
* \
D E
3. then backup and visit E
A
* \
B C

【在 i***h 的大作中提到】

: 这个是那本算法书二叉树一节后的题
: 网上查了下,除非节点带对父节点的指针才行,好象作弊了(这个额外的指针就是O(n)空
: 间了)
: 有答案么?
: 谢谢

i*h2008-07-11 07:07

5 楼

你问到点子上了
要求是不能
[Cormen习题11.4-5] O(n) time, non-recursive, constant extra space, do not
modify the tree (even temporarily)
很刁难人啊

【在 c*****t 的大作中提到】

: If the tree can be modified...
: / \ are downward arrows, * is the upward arrow, stored in either left
: or right branch.
: root := A
: A
: / \
: B C
: / \
: D E
: 1.

c*t2008-07-11 07:07

6 楼

那么题目出错了 :)
100% 可以肯定。

【在 i***h 的大作中提到】

: 你问到点子上了
: 要求是不能
: [Cormen习题11.4-5] O(n) time, non-recursive, constant extra space, do not
: modify the tree (even temporarily)
: 很刁难人啊

l*u2008-07-11 07:07

7 楼

你肯定你看见了整个题目了?
就这个?
lz把原题找出来我们再下结论吧.

i*h2008-07-11 07:07

8 楼

Introduction to Algorithms
1990 MIT Press
Page 216
11.4-5 *
Write an O(n)-time nonrecursive procedure that, given an n-node binary tree,
prints out the key of each node. Use no more than constant extra space
outside of the tree itself and do not modify the tree, even temporarily,
during the procedure.

n*t2008-07-11 07:07

9 楼

哈哈，同学你被晃点了，CLRS那本书里面的binrary tree每个节点是带了
指向parent节点的指针的。

【在 i***h 的大作中提到】

: 这个是那本算法书二叉树一节后的题
: 网上查了下,除非节点带对父节点的指针才行,好象作弊了(这个额外的指针就是O(n)空
: 间了)
: 有答案么?
: 谢谢

l*u2008-07-11 07:07

10 楼

The problem doesn't specify how the binary tree is stored, and whether the
traversal has to be in certain order. These are the two areas you can
expand on. If the solution has to work for any binary tree implementation
and any traversal order, I think it simply does not exist.
You can certainly store a binary tree in a way so that it can be traversed
in O(n) time + O(1) space. Parent pointer is one simply way. Storing in a
continuous array is another. Or you can use sibling pointers. Etc.
In

【在 i***h 的大作中提到】

: Introduction to Algorithms
: 1990 MIT Press
: Page 216
: 11.4-5 *
: Write an O(n)-time nonrecursive procedure that, given an n-node binary tree,
: prints out the key of each node. Use no more than constant extra space
: outside of the tree itself and do not modify the tree, even temporarily,
: during the procedure.

i*h2008-07-11 07:07

11 楼

一语惊醒梦中人
原来不是我傻
而是我傻透了
多谢大家的讨论和指点

【在 n******t 的大作中提到】

: 哈哈，同学你被晃点了，CLRS那本书里面的binrary tree每个节点是带了
: 指向parent节点的指针的。

i*h2008-07-11 07:07

12 楼

Thanx

binary
node.

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

: The problem doesn't specify how the binary tree is stored, and whether the
: traversal has to be in certain order. These are the two areas you can
: expand on. If the solution has to work for any binary tree implementation
: and any traversal order, I think it simply does not exist.
: You can certainly store a binary tree in a way so that it can be traversed
: in O(n) time + O(1) space. Parent pointer is one simply way. Storing in a
: continuous array is another. Or you can use sibling pointers. Etc.
: In