為什麼這篇後序走訪鄉民發文收入到精華區：因為在後序走訪這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者peggypiano (大N)看板Programming標題[問題] 森林的後序走訪時間Sat ...
後序走訪 在 Mia /TZUYULIN Instagram 的最讚貼文
2021-09-24 01:59:03
Δ 陳又凌可愛又繽紛的插圖， 結合史大 @starcheng1019 的立體結構， 變成一本好有趣的繪本。 怎麼這麼厲害。 又凌的插圖讓人對地圖突然很有興趣， 畫的都能當地理課本用了。 比起照片，插圖更為吸引人！ 再結合立體結構變的更生動有趣。 一打開就吸引小孩立刻上前來關心。 （實在超怕被弄壞）...
大家好，我想問關於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: 我也覺得你是對的 115.82.16.46 12/10 15:10
推 asd456fgh778: 走B的是不是有問題啊 115.82.16.46 12/10 15:18
推 asd456fgh778: 欸不對 B的左子樹 爲空 所以輸出B 115.82.16.46 12/10 15:27
→ asd456fgh778: 是我有問題啊... 115.82.16.46 12/10 15:27
→ asd456fgh778: 奇怪到底怎麼回事.. 115.82.16.46 12/10 15:28
推 asd456fgh778: 可是B是C的根 那應該要先輸出D才對 115.82.16.46 12/10 15:29