作者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