作者qqmango (聽，是誰在唱歌)
看板Army-Sir
標題Re: [問題] 98計概二元搜尋樹
時間Sun Jan 31 21:49:09 2010
※ 引述《garfield11 (加菲貓)》之銘言：
: ※ 引述《dohard (最近很忙 請來電^^)》之銘言：
: : 3.將下列鍵值輸入,直接建立一個二元搜尋樹:368,115,121,88,741,762,801,34,41,511,3
: : 0 欲找鍵值為34的節點,從368節點為第一次起算,須經過幾次的比較
: : ans:4
: 1 368
: / \
: 2 115 741
: / \ / \
: 3 88 121 511 762
: / \
: 4 34 801
: / \
: 30 41
: BST規則是左小右大
因為BST看不太懂，所以就去上面找了資料。
解題的方法就是一個一個加上去，依照題目所給的順序輸入
好比這一題就是368,115,121,88,741,762,801,34,41,511,30
則建立BST第一步是以368開始(輸入的第一筆)
第1步，以368為根
368
第2步，用115跟368比，如果比368小，就放在左子樹上，比368大，
就放在右子樹。115 < 368，放左子樹
368
/
115
第3步，121，因為121比368小，所以放在368的左子樹上，
但因為368的直接的左子樹已經有115了，所以要再跟115比
因為121 > 115，所以放在115的右子樹。
368
/
115
\
121
第4步，88，依此類推，先跟368比，比368小，放在368的左子樹
然後再跟115比，比115小，放在115的左子樹。
368
/
115
/ \
88 121
然後重覆這些步驟，就可以畫出上一篇的圖了
--
台大校園捷運系統 ╭○長興基隆站 ╭○新月台─○新體站
均◎─◎─○─○─○─○─◎─○─○─○─○─○─○─○─◎─○─◎─╮
一公 校 大 小 生 健 總 電 停 辛 摩 計 思 新 小 校 校 ○水源站
價館 門 一 小 科 康 圖 機 機 亥 斯 中 亮 生 福 史 門
15站 前 女 福 館 中 站 系 坪 後 漢 站 館 大 站 館 前
元 心 館 門 堡 樓
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.145.44
※ 編輯: qqmango 來自: 61.231.145.44 (01/31 21:49)
1F：推 traces:喔喔!!感謝你 01/31 21:50
2F：推 apl02:所以最後是看所要的數值在哪一層 來決定要比較幾次嗎? 01/31 22:05
3F：推 hottim:強悍！簡單明瞭：） 01/31 22:20
4F：→ ilw4e:對 在幾層比幾次 01/31 22:39
5F：推 dohard:我懂了 感謝^^ 01/31 23:19
6F：推 OwenU06:懂了!! 感謝!! 01/31 23:20
7F：推 hunter1214:GOOD 簡單明瞭 01/31 23:57
8F：推 gygyman:一目了然!水! 02/01 01:06
9F：推 kimos:got it ! Thanks.. 02/01 01:27
11F：推 lingja:那如果一樣大要怎麼辦呢 01/16 17:22
12F：推 tomroy:感謝 01/16 19:51
13F：推 Fjchen:這篇超清楚! 01/17 19:07