作者MarkHero (Mark)
看板TransCSI
標題[問題] 關於二元樹的前序、中序、後序追蹤法
時間Tue Apr 12 14:39:38 2011
最近開始讀到演算法的基礎東西了，
但是對這從來沒碰過的東西總是非常陌生，
特別是最近看到的前序、中序、後序追蹤的部分，
前序追蹤法我看了很久才搞懂他的邏輯，
但中序就越來越難懂了，上網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也沒問題!!!!!
麻煩各位前輩幫我用簡單一點的方式解釋一下中序跟後序的規則....
我不想在這裡就澆熄我對資工的熱情阿!!!!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.64.233
※ MarkHero:轉錄至看板 ask 04/12 14:40
推 nosignal90:我是把它們都變成最小單位的三角形,當初也研究好久XD 04/12 19:05
推 windverb:你可以用畫線的方式來圍繞整個樹 04/13 17:39
→ windverb:1.用中序的話就在每個節點畫↓的箭頭 04/13 17:41
推 windverb:2.由左往右畫一條每個節點都會經過的線 04/13 17:43
→ windverb:畫法像你把手掌貼在紙上畫輪廓一樣 04/13 17:44
→ windverb:這樣一直從樹根左邊畫回樹根右邊 04/13 17:44
→ windverb:畫的線都都要經過每個節點下方的箭頭 04/13 17:46
→ windverb:照順序從左邊開始判斷每個被經過的節點就是中序了 04/13 17:47
→ windverb:抱歉用講得很難讓人明白= = 04/13 17:47
推 EEspresso:還有一種方法是用 遇到了幾次在解 的 我們資結老師有教 04/15 00:09
推 EEspresso:比較簡單的理解方法 就是tree用逆時針畫一圈 遇到一次就 04/15 00:12
→ EEspresso:標上1 遇到第2次標上2 遇到第3次標上3 然後preorder就是 04/15 00:14
→ EEspresso::第一次遇到依逆時針列出 inorder:第二次遇到的列出 04/15 00:15
→ EEspresso:postorder:就是最後一次遇到的列出 不過我都沒照這個xd 04/15 00:16