(0 + 7 ) / 2 = 3 -> 34
( 3 + 7 ) / 2 = 5 -> 62
( 5 + 7 ) / 2 = 6 -> 74
( 6 + 7 ) / 2 = 7 -> 85
我们写程序一般来说从0开始。
查找不成功就是从查找位置开始直到一个位置为空需要比较的次数。
比如：
62
/ \
30 74
/ \
15 56
/
48
找到所有的外结点，也就是查找失败的点，然后计算ASL
就你的BST，结果如下：
15的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、30、15一共3次
48的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、30、15、48一共4次
56的右子树为空，也就是右子树是外结点，失败时需要比较62、30、56一共3次
74的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、74一共2次
因此外结点总数为2 *3 + 1 = 7 （其实这个数量一定是关键字个数加1）
所以ASL = (2 * 3 + 2 * 4 + 1 * 3 + 2 * 2) / 7 = 21 / 7 = 3。
扩展资料：查找步骤：
二叉树
若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。
平均情况分析（在成功查找两种的情况下）：
在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数
参考资料来源：百度百科-二叉排序树
欢迎分享，转载请注明来源：优选云
微信扫一扫
支付宝扫一扫
