[問題] 關於二元樹的前序、中序、後序追蹤法

作者: MarkHero (Mark)   2011-04-12 14:39:38
最近開始讀到演算法的基礎東西了,
但是對這從來沒碰過的東西總是非常陌生,
特別是最近看到的前序、中序、後序追蹤的部分,
前序追蹤法我看了很久才搞懂他的邏輯,
但中序就越來越難懂了,上網GOOGLE了一下,
發現:
左→中→右或是左→根→右,是個關鍵,
但我始終搞不懂一些東西(下面會詳述我的問題)
網路上有些大大很厲害,寫了一些簡易的理解法,
但我卻越看越迷糊(可能我理解力或邏輯性蠻差的吧..)
有些特別的記憶法:
1.三人成行(那湊不滿三人或是其中一人重複怎辦?)
2.兒子擺兩邊、爸爸放中間(這勉強看得懂)
3.由低到高(這大概是最了解的部分了XD)
4.逐步收納(有時候最上層反而很快就被收進去,為什麼@@?)
我的問題是這樣的
A
/  \
B C
/  \ / \
D E F G
/  \  |
H I J
他的中序是這樣:HDI B JE A FCG
按照規則來說HDI我是完全沒問題,
但B完以後,按照左中右的概念,應該是BAC才對不是嗎!?
怎麼會突然跳到JE,而且E連結J的地方是直線(書上真的這樣畫)
直線我要怎麼看阿(崩潰!!!)
FCG也沒問題!!!!!
麻煩各位前輩幫我用簡單一點的方式解釋一下中序跟後序的規則....
我不想在這裡就澆熄我對資工的熱情阿!!!!!
作者: nosignal90 (NoSignal)   2011-04-12 19:05:00
我是把它們都變成最小單位的三角形,當初也研究好久XD
作者: windverb (哈哈哈)   2011-04-13 17:39:00
你可以用畫線的方式來圍繞整個樹1.用中序的話就在每個節點畫↓的箭頭2.由左往右畫一條每個節點都會經過的線畫法像你把手掌貼在紙上畫輪廓一樣這樣一直從樹根左邊畫回樹根右邊畫的線都都要經過每個節點下方的箭頭照順序從左邊開始判斷每個被經過的節點就是中序了抱歉用講得很難讓人明白= =
作者: EEspresso (我要吃!!!)   2011-04-15 00:09:00
還有一種方法是用 遇到了幾次在解 的 我們資結老師有教比較簡單的理解方法 就是tree用逆時針畫一圈 遇到一次就標上1 遇到第2次標上2 遇到第3次標上3 然後preorder就是:第一次遇到依逆時針列出 inorder:第二次遇到的列出postorder:就是最後一次遇到的列出 不過我都沒照這個xd

Links booklink

Contact Us: admin [ a t ] ucptt.com