4．给定无序表D={18,88,15,93,35,51,60,17,22},用二叉排序树查找法在D中查找51.现要求：（1）试画出二叉排序树,并画出查找过程；（3分）（2）求出其成功的平均查找长度ASL.（4分）

Question

4．给定无序表D={18,88,15,93,35,51,60,17,22},用二叉排序树查找法在D中查找51.现要求：
（1）试画出二叉排序树,并画出查找过程；（3分）
（2）求出其成功的平均查找长度ASL.（4分）

Answer 1

(1)树如下（查找过程已标红）：
         18
15/            \88
    \17   35/     \93
          22/\51
                  \60
(2)

查找长度：
ASL=(1*1+2*2+3*3+4*2+5*1)/9=3