[問題] 森林的後序走訪

[peggypiano (大N)]

大家好，我想問關於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
推 asd456fgh778: 我也覺得你是對的
推 asd456fgh778: 走B的是不是有問題啊
推 asd456fgh778: 欸不對 B的左子樹 爲空 所以輸出B
→ asd456fgh778: 是我有問題啊...
→ asd456fgh778: 奇怪到底怎麼回事..
推 asd456fgh778: 可是B是C的根 那應該要先輸出D才對