大家好，我想问关于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 谢谢~~~