Question

数据结构题目

试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。
（1）试画出插入完成之后的二叉排序树（6分）
（2）假设每个元素的查找概率相等,试计算查找成功时的平均查找长度（4分）
（3）若查找元素17,将依次与哪些元素比较？查找结果如何？ （5分）

Answer 1

（2）：10/3

(3):10-12-15-19

查找失败！

Answer 2

(1)
10
/ \
8 12
/ \ \
5 9 20
\ / \
6 15 25
\
19
(2)(1+2*2+3*3+3*4+5)/10=3.1
(3)将依次与10,12,20,15,19比较,最终查找失败