作者psalms945 (10B)
看板Grad-ProbAsk
标题[理工] 96成大 资工所 程式设计
时间Sat Mar 6 10:43:48 2010
http://ppt.cc/;S0T
我想问资料结构第3题的第一小题
关於forest postorder
我的答案是 BDCGJKHIFEA
不知道答案对不对
不太了解forest postorder 是怎麽走访的
洪兔对forest postorder 的讲法是
每一颗子树走完,再从最後一颗tree之root往回走访各树之root
指的是对每一颗tree作postorder走访再往回走访各树之root的意思吗?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.136.240.66
※ 编辑: psalms945 来自: 220.136.240.66 (03/06 10:54)
1F：推 samfox:1.子树 2.其他树 3.root 递回 dcbkjigfea 我的答案 03/06 11:37
2F：→ psalms945:k,j 2点为何先走访k? 03/06 12:00
3F：→ fef92:参考洪兔的 结果跟原po相同 03/06 12:18
4F：推 holik0123:最後那Complete threaded 是只要画threaded还是? 03/06 13:31
5F：推 crazyjoe:加上threaded 03/06 16:23
6F：→ samfox:因为j为root时 1.j的子树 2.其他树 3.才是j。jk都是h的子树 03/06 17:44
7F：→ psalms945:1F 那种走访有参照哪里的吗? 还是有其他题目可以理解的? 03/06 17:53
洪兔给的题目
A F I
/ | \ / \
B C D G H
/
E
他给的postorder是 EBCDGHIFA
依照1F的走访 应该是 EDCBHGIFA
# Forest postorder traversal
* If F is empty, then return
* Traverse the subtrees of the first tree in tree postorder
* Traverse the remaining tree of F in postorder
* Visit the root of the first tree of F
刚刚找到的
※ 编辑: psalms945 来自: 220.136.240.66 (03/06 18:07)→ samfox:我有上洪兔，可是我笔记里面没带到这个，是後来看我朋友上 03/06 18:13
8F：→ samfox:别的老师的笔记，我在确认一下好了。 03/06 18:13
9F：→ bensome0624:照你给的英文讲法,洪兔这题应该是EDCBHGIFA 03/06 20:17
10F：→ bensome0624:然後本题应该是和1F一样是DCBKJIHGFEA 03/06 20:19
Traverse the subtrees of the first tree in tree postorder中
tree postorder 不是先走left child 再走right child吗?
这样走完E後B没有right child了 应该是选自己本身B 为何是选D?? 还是误解英文的意思??
※ 编辑: psalms945 来自: 220.136.240.66 (03/06 20:35)
11F：→ bensome0624:B-E,C,D三个子树,先追踪B的子树,再追踪其他子树(C,D) 03/06 20:38
12F：→ bensome0624:最後再追踪第一棵树的root(也就是B) 03/06 20:39
洪兔有提到 forest的postorder不等於binary tree的postorder
他给了以下2个答案来说明2种postorder不相同
forest postorder:EBCDGHIFA 也就是我刚刚打的
forest画成binary tree的postorder:EDCBHGIFA ==>竟然是依照1F的走访0.0
所以....间接说明1F得那种走访并不是forest的postorder??
※ 编辑: psalms945 来自: 220.136.240.66 (03/06 21:10)
13F：→ zkdzvy22:我记得是不一定相同 不是一定不相同 不过我不会证明(摊手 03/06 21:16
14F：→ bensome0624:你给的英文说明应该来自圣经本,结果和二元树追踪相同 03/06 21:17
15F：→ bensome0624:Knuth版本才是追踪完一棵再追踪下一棵,可是如果你的补 03/06 21:18
16F：→ bensome0624:习班给的说明是你上面PO的,应该就是1F走法而不是Knuth 03/06 21:21
Knuth有提到2种走访相不相同的问题吗?
那个英文版是上网找的不是洪兔给的
洪兔只丢了一句话=>每一颗子树走完再从最後一颗tree之root往走访各树之root
※ 编辑: psalms945 来自: 220.136.240.66 (03/06 21:40)
※ 编辑: psalms945 来自: 220.136.240.66 (03/06 21:42)