大家好，我想問關於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://webptt.com/m.aspx?n=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://webptt.com/m.aspx?n=bbs/Programming/M.1481352949.A.D25.html