Re: [閒聊] 預官
※ 引述《logteng ()》之銘言：
: 更 我計概看不太懂啦!!
: 預官跟國考只差兩三天
: 劉小諭你說說看要怎麼辦
前幾天在看研究所考題有講到binary tree
記得之前考預官有考 考預官前一年考古題也有 如果知道這是在幹嘛的話還滿簡單的
二元樹 定義就算了 大概長這樣
A
/ \
B C
/ \ / \
D E F G
一律從中間開始寫成一串表示
中序是 左下做完-自己-右下做
前序是 自己-左下做-右下做
後序是 左下做-右下做-自己
所以上面
中序 DBEAFCG (A的左下->B的左下->"D"(做完回上層)->"B"(自己)->(做右下)"E"
(做完回上層->A的左下都做完->"A"->(做A的右下)->C的左下開始->"F"...
前序 ABDECFG
後序 DEBFGCA
預官考試好像給一個某序 然後問哪一個是他的另一序吧
這樣考很爛 要花滿多時間算的 (因為題目沒法畫成唯一的tree)
考試的時候就畫題目的tree 然後根據選項的走法 刪不合的吧
至於要怎麼從字串變tree 恩
前序第一個一定是root 後序最後一個一定是root
中序的話 如果左右數量相等 則中間的是root
大概這樣去推
不然反正計概這科時間應該剩很多 就畫上面那個圖用題目的字母去去填 XD
(要記得考慮空的)
如果給前序 ABCDEFGH
就會知道 A在root
跟中序CDBEAGFH 比較 可以知道 CDBE在左邊 FGH在右邊
跟後序DCEBGHFA 比較 拿前序第二個B去看 就知道後序在B之前的DCEB在左邊
之後左右邊繼續做 就可以推出
A
/ \
B F
/ \ / \
C E G H
\
D
大概是這樣....
就算學會了也才多兩分 還是去看"海龍海虎海獅海豹海象海熊"哪些是潛艇的名字比較快XD
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.73.91.192
推
01/19 00:01, , 1F
01/19 00:01, 1F
討論串 (同標題文章)