作者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)