大家好，我想问关於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/cn.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/cn.aspx?n=bbs/Programming/M.1481352949.A.D25.html