解:(1)若查 二分查 找给定值为20的元 找判定 素,依次与表中 树 25,10,15,20元素比 较,共比较4次。 (2)若查找给定值为26的元素,依次与25,30,28元素比较, 共比较3次 (3)在查找成功时,会找到图中某个圆形节点,则成功 时的平均查找长度: 1x1+2×2+4×3+4×4 ASLSucc= 3 在查找不成功时会找到图中某个方形节点则不成功时 的平均查找长度 ASLunsucc≈4×3+8×4 =3.67 1225 10 30 2 15 28 35 3 20 29 40 二分查 找判定 树 （2）若查找给定值为26的元素，依次与25,30,28元素比较， 共比较3次。 （3）在查找成功时，会找到图中某个圆形节点，则成功 时的平均查找长度： 3 11 1 1 2 2 4 3 4 4 ASLsucc＝ ＝  +  +  +  解：（1）若查 找给定值为20的元 素 , 依 次 与 表 中 25,10,15,20 元素比 较，共比较4次。 在查找不成功时,会找到图中某个方形节点,则不成功时 的平均查找长度： 3.67 12 4 3 8 4 ASLunsucc ＝ ＝  + 