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

看板TransCSI作者 (Mark)時間13年前 (2011/04/12 14:39), 編輯推噓5(5推 0噓 9→)
留言14則, 3人參與, 最新討論串1/2 (看更多)
最近開始讀到演算法的基礎東西了， 但是對這從來沒碰過的東西總是非常陌生， 特別是最近看到的前序、中序、後序追蹤的部分， 前序追蹤法我看了很久才搞懂他的邏輯， 但中序就越來越難懂了，上網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
推
04/12 19:05, , 1F
我是把它們都變成最小單位的三角形,當初也研究好久XD
04/12 19:05, 1F
推
04/13 17:39, , 2F
你可以用畫線的方式來圍繞整個樹
04/13 17:39, 2F
→
04/13 17:41, , 3F
1.用中序的話就在每個節點畫↓的箭頭
04/13 17:41, 3F
推
04/13 17:43, , 4F
2.由左往右畫一條每個節點都會經過的線
04/13 17:43, 4F
→
04/13 17:44, , 5F
畫法像你把手掌貼在紙上畫輪廓一樣
04/13 17:44, 5F
→
04/13 17:44, , 6F
這樣一直從樹根左邊畫回樹根右邊
04/13 17:44, 6F
→
04/13 17:46, , 7F
畫的線都都要經過每個節點下方的箭頭
04/13 17:46, 7F
→
04/13 17:47, , 8F
照順序從左邊開始判斷每個被經過的節點就是中序了
04/13 17:47, 8F
→
04/13 17:47, , 9F
抱歉用講得很難讓人明白= =
04/13 17:47, 9F
推
04/15 00:09, , 10F
還有一種方法是用 遇到了幾次在解 的 我們資結老師有教
04/15 00:09, 10F
推
04/15 00:12, , 11F
比較簡單的理解方法 就是tree用逆時針畫一圈 遇到一次就
04/15 00:12, 11F
→
04/15 00:14, , 12F
標上1 遇到第2次標上2 遇到第3次標上3 然後preorder就是
04/15 00:14, 12F
→
04/15 00:15, , 13F
:第一次遇到依逆時針列出 inorder:第二次遇到的列出
04/15 00:15, 13F
→
04/15 00:16, , 14F
postorder:就是最後一次遇到的列出 不過我都沒照這個xd
04/15 00:16, 14F
‣ 更多 MarkHero 的文章
文章代碼(AID): #1De_EjJk (TransCSI)
‣ 更多 MarkHero 的文章
文章代碼(AID): #1De_EjJk (TransCSI)