企源知识库

设有一组关键字值序列{e，b，d，f，a，g，c}现要求：
（1）根据二叉排序树的创建方法构造出相应的二叉排序树(关键字值的大小按字母表顺序计)；
（2）计算等概率情况下在该二叉排序树上查找成功的平均查找长度ASL。
【正确答案】：

【答案】（1）构造出的二叉排序树下图。

（2）ASL=（1×1+2×2+3×3+1×4）/7=18/7。
解析：二叉排序树：左孩子