用序列(46,68,45,139,70,58,101,10,88,94)建立一个二叉排序树,画出该树,并求在等概率情况下查找成功的平均查找长度

二叉排序树:
二叉排序树要么是 空二叉树,要么具有如下特点:
二叉排序树中,如果其根结点有左子树,那么 左子树 上所有结点的值都 小于 根结点的值;
二叉排序树中,如果其根结点有右子树,那么 右子树 上所有结点的值都 大小 根结点的值;
二叉排序树的 左右子树也要求都是二叉排序树

推荐观看视频:
https://www.bilibili.com/video/BV1nJ411V7bd?p=146

画图:

如何验证自己画的二叉树为二叉排序树?可以通过对树进行 中序遍历 ,得到的序列为有序的就说明对了,因为要符合结点左右子树都是二叉排序树的特性。

求在等概率情况下查找成功的平均查找长度

ASL = 每个结点的深度相加除以结点个数

ASL = (1*1+2*2+3*3+4*4)/10=3

本文地址:https://blog.csdn.net/qq_44880154/article/details/110505574