依次输入元素：10,8,16,5,20,7,12,19,试生成一棵二叉排序树.(1)画出建立的二叉排序树.(2)假定每个元素的查找概率相等,计算查找成功时的平均查找长度.
1人问答
问题描述：
依次输入元素：10,8,16,5,20,7,12,19,试生成一棵二叉排序树.(1)画出建立的二叉排序树.(2)假定每个元素的查找概率相等,计算查找成功时的平均查找长度.
蔡则苏回答：
你是要算法还是本题答案?
本题答案为
10
816
51220
719
算法为：
步骤：若根结点的关键字值等于查找的关键字,成功.
否则,若小于根结点的关键字值,递归查左子树.
若大于根结点的关键字值,递归查右子树.
若子树为空,查找不成功.
平均情况分析（在成功查找两种的情况下）
在一般情况下,设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
八字精批
八字合婚
八字起名
八字财运
2024运势
测终身运
姓名详批
结婚吉日
数学推荐
![已知xy=-2,x—y=3,求代数式(-3xy—7y)+[4x—3(xy+y—2x)]的值](/UploadFile/wdimg/2007/694507114/94/2897494965.jpg)
数学推荐
最新更新
精品分类
优秀数学推荐
热门数学
邮箱： 
