[理工] [資結]-成大96-資工所

看板Grad-ProbAsk作者 (10B)時間16年前 (2010/03/06 10:43), 編輯推噓3(3推 0噓 13→)
留言16則, 7人參與, 最新討論串1/1
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)
推
03/06 11:37, , 1F
1.子樹 2.其他樹 3.root 遞迴 dcbkjigfea 我的答案
03/06 11:37, 1F
→
03/06 12:00, , 2F
k,j 2點為何先走訪k?
03/06 12:00, 2F
→
03/06 12:18, , 3F
參考洪兔的 結果跟原po相同
03/06 12:18, 3F
推
03/06 13:31, , 4F
最後那Complete threaded 是只要畫threaded還是?
03/06 13:31, 4F
推
03/06 16:23, , 5F
加上threaded
03/06 16:23, 5F
→
03/06 17:44, , 6F
因為j為root時 1.j的子樹 2.其他樹 3.才是j。jk都是h的子樹
03/06 17:44, 6F
→
03/06 17:53, , 7F
1F 那種走訪有參照哪裡的嗎? 還是有其他題目可以理解的?
03/06 17:53, 7F
洪兔給的題目 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
→
03/06 18:13, , 8F
別的老師的筆記，我在確認一下好了。
03/06 18:13, 8F
→
03/06 20:17, , 9F
照你給的英文講法,洪兔這題應該是EDCBHGIFA
03/06 20:17, 9F
→
03/06 20:19, , 10F
然後本題應該是和1F一樣是DCBKJIHGFEA
03/06 20:19, 10F
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)
→
03/06 20:38, , 11F
B-E,C,D三個子樹,先追蹤B的子樹,再追蹤其他子樹(C,D)
03/06 20:38, 11F
→
03/06 20:39, , 12F
最後再追蹤第一棵樹的root(也就是B)
03/06 20:39, 12F
洪兔有提到 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)
→
03/06 21:16, , 13F
我記得是不一定相同 不是一定不相同 不過我不會證明(攤手
03/06 21:16, 13F
→
03/06 21:17, , 14F
你給的英文說明應該來自聖經本,結果和二元樹追蹤相同
03/06 21:17, 14F
→
03/06 21:18, , 15F
Knuth版本才是追蹤完一棵再追蹤下一棵,可是如果你的補
03/06 21:18, 15F
→
03/06 21:21, , 16F
習班給的說明是你上面PO的,應該就是1F走法而不是Knuth
03/06 21:21, 16F
Knuth有提到2種走訪相不相同的問題嗎? 那個英文版是上網找的不是洪兔給的 洪兔只丟了一句話=>每一顆子樹走完再從最後一顆tree之root往走訪各樹之root ※ 編輯: psalms945 來自: 220.136.240.66 (03/06 21:40) ※ 編輯: psalms945 來自: 220.136.240.66 (03/06 21:42)
‣ 更多 psalms945 的文章
文章代碼(AID): #1BaS5cwP (Grad-ProbAsk)