题目

依次输入元素：10,8,16,5,20,7,12,19,试生成一棵二叉排序树.(1) 画出建立的二叉排序树.(2) 假定每个元素的查找概率相等,计算查找成功时的平均查找长度.

提问时间：2021-03-28

答案

你是要算法还是本题答案?
本题答案为
10
8 16
5 12 20
7 19
算法为：
步骤：若根结点的关键字值等于查找的关键字,成功.
否则,若小于根结点的关键字值,递归查左子树.
若大于根结点的关键字值,递归查右子树.
若子树为空,查找不成功.
平均情况分析（在成功查找两种的情况下）
在一般情况下,设 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 个结点二叉分类树的平均查找长度.P(3) = （1+2+2）/ 3 = 5/3
P(2) = （1+2）/ 2 = 3/2
∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
n
二叉树
-1
∴ P（n）= ∑ P（n,i）/ n