Re: [問題] 關於二元樹的前序、中序、後序追蹤法
※ 引述《MarkHero (Mark)》之銘言：
: 最近開始讀到演算法的基礎東西了，
: 但是對這從來沒碰過的東西總是非常陌生，
: 特別是最近看到的前序、中序、後序追蹤的部分，
: 前序追蹤法我看了很久才搞懂他的邏輯，
: 但中序就越來越難懂了，上網GOOGLE了一下，
: 發現：
: 左→中→右或是左→根→右，是個關鍵，
: 但我始終搞不懂一些東西(下面會詳述我的問題)
: 網路上有些大大很厲害，寫了一些簡易的理解法，
: 但我卻越看越迷糊(可能我理解力或邏輯性蠻差的吧..)
: 有些特別的記憶法：
: 1.三人成行(那湊不滿三人或是其中一人重複怎辦?)
: 2.兒子擺兩邊、爸爸放中間(這勉強看得懂)
: 3.由低到高(這大概是最了解的部分了XD)
: 4.逐步收納(有時候最上層反而很快就被收進去，為什麼@@?)
: 我的問題是這樣的
: A
: ／ ＼
: B C
: ／ ＼ ／ ＼
: D E F G
: ／ ＼ |
: H I J
中序追蹤順序是：左→中→右
以A為"中"時，HDIBJE是A的"左"小樹，FCG是A的右小樹。
以B為"中"時，HDI是B的"左"小樹，JE是B的"右"小樹。
以D為"中"時，H是D的"左"小樹，I是D的"右"小樹。所以寫法是左H中D右I→HDI
要從左邊最小的樹寫起，所以先寫 左：HDI 中：B 右：JE
(至於是JE還是EJ要看J是E的左小樹還是右小樹)
所以應該看成 {[(HDI) B (JE)] A [FCG] }
: 他的中序是這樣：HDI B JE A FCG
: 按照規則來說HDI我是完全沒問題，
: 但B完以後，按照左中右的概念，應該是BAC才對不是嗎!?
: 怎麼會突然跳到JE，而且E連結J的地方是直線(書上真的這樣畫)
: 直線我要怎麼看阿(崩潰!!!)
: FCG也沒問題!!!!!
: 麻煩各位前輩幫我用簡單一點的方式解釋一下中序跟後序的規則....
: 我不想在這裡就澆熄我對資工的熱情阿!!!!!
這樣會不會很難懂啊?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.120.43.32
※ 編輯: minimatsumi 來自: 122.120.43.32 (04/14 19:12)
推
05/31 19:29, , 1F
05/31 19:29, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：