[問題] 森林的後序走訪

看板Programming作者peggypiano (大N)時間8年前 (2016/12/10 14:55)推噓4(4推 0噓 2→)

留言6則, 1人參與討論串1/1

大家好，我想問關於Forest postorder的問題，在Fundamentals of Data Structures in C++這本書裡有提到Forest畫出相對的二元樹後的postorder 跟 Forest 的 postorder 結果有可能會不一樣課本裡的例子是 A E G /|\ | / \ B C D F H I 它對應的binary tree A / \ B E \ / \ C F G \ / D H \ I Forest Postorder的規則定義如下: 1. If F is empty then return. 2. Traverse the subtrees of the first tree of F in forest postorder. 3. Traverse the remaining trees of F in forest postorder. 4. Visit the root of the first tree of F. Binary tree 的 postorder的走訪規則: LRV: 先走訪左子樹與右子樹後才拜訪這個節點我和我同學做出來的兩種走訪順序一樣QQ 都是 DCBFIHGEA 老師現在也有點不太確定森林的走訪順序應該是怎樣我Google到之前有人在ptt問過 https://www.ptt.cc/bbs/Grad-ProbAsk/M.1267843430.A.E99.html 照裡面的洪兔寫法應該會是BCDFHIGEA (forest postorder) 我還有google到一個簡報裡寫得更怪是 BCDFEHIGA 不知道是有其他例子才是兩種走訪寫出來會不一樣嗎?還是? 因為照上面的那個定義每次都會因為Forest postorder裡又Forest postorder 遞迴的方式下去，最後都會碰到空子樹然後return最後就是倒著輸出根部過程: Now: (A樹) (E樹) (G樹) -> 樹林後序法走訪第一棵樹的子樹 -(3) 也就是 B C D Now: B C D -> 樹林後序法走訪第一棵樹(B)的子樹(空的) ...return -> 樹林後序法走訪其餘子樹(C D) -(2) Now: C D -> 樹林後序法走訪第一棵樹(C)的子樹(空的) ...return -> 樹林後序法走訪其餘子樹(D) -(1) Now: D -> 樹林後序法走訪第一棵樹(D)的子樹(空的) ...return -> 樹林後序法走訪其餘子樹(空的)...return -> 走訪第一顆樹的樹根(D) Output: D 接回(1)式 Now: C D -> 走訪第一顆樹的樹根(C) OutPut: DC 接回(2)式 Now: B C D -> 走訪第一顆樹的樹根(B) Output: DCB 接回(3)式 Now: (A樹) (E樹) (G樹) -> 樹林後序法走訪其餘子樹 (E樹) (G樹) -(8) Now: (E樹) (G樹) -> 樹林後序法走訪第一棵樹(E樹)的子樹(F) -(4) Now: F -> 樹林後序法走訪第一顆樹(F)的子樹(空的)...return -> 樹林後序法走訪其餘子樹(空的)...return -> 走訪第一顆樹的樹根(F) Output:DCBF 接回(4)式 Now: (E樹) (G樹) -> 樹林後序法走訪其餘子樹(G樹) -(7) Now: G樹 -> 樹林後許法走訪第一顆樹(G)的子樹(H I) -(6) Now: H I -> 樹林後許法走訪第一顆樹(H)的子樹(空的)....return -> 樹林後序法走訪其餘子樹(I) -(5) Now: I -> 樹林後許法走訪第一顆樹(I)的子樹(空的)....return -> 樹林後序法走訪其餘子樹(空的)...return -> 走訪第一顆樹的樹根(I) Output:DCBFI 接回(5)式 Now:H I -> 走訪第一顆樹的樹根(H) Output:DCBFIH 接回(6)式 Now: G樹 -> 樹林後序法走訪其餘子樹(空的)...return -> 走訪第一顆樹的樹根(G) Output:DCBFIHG 接回(7)式 Now: (E樹) (G樹) -> 走訪第一顆樹的樹根(E) Output:DCBFIHGE 接回(8)式 Now: (A樹) (E樹) (G樹) -> 走訪第一顆樹的樹根(A) Output:DCBFIHGEA 麻煩大家幫我看看QQ 謝謝~~~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.22.70 ※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1481352949.A.D25.html