已知有如下一个关键字序列{96,47,104,32,73,136,15,38,90,180},按照上述插入顺序构造一棵二叉排序树,则请给出二叉排序树的构造过程,说明其深度,并在等概率的条件下求出平均查找长度。

admin2010-04-24  25

问题 已知有如下一个关键字序列{96,47,104,32,73,136,15,38,90,180},按照上述插入顺序构造一棵二叉排序树,则请给出二叉排序树的构造过程,说明其深度,并在等概率的条件下求出平均查找长度。

选项

答案根据二叉排序树的生成过程,我们可以得到如下二叉排序树的构造结果: 此二叉排序树的深度(即高度)为4,在二叉树上,要找到第i层上的结点恰好需要比较i次,而在此二叉排序树上,第1,2,3,4层上分别有1,2,3,4个结点,则在等概率的条件下,查找成功的平均查找长度为: [*]

解析
转载请注明原文地址:https://kaotiyun.com/show/Z0Ax777K
本试题收录于: 数据结构题库理工类分类
0

相关试题推荐
最新回复(0)