Question

数据结构，折半查找判定树

对于数列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（ ）。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（ ）。
【解答】8，59/15

8是怎么样算得。那个59/15 是怎么画得，为什么我算得时 49/15

Answer 1

判定树的构造方法
⑴当n=0时，折半查找判定树为空；
⑵当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。

Answer 2

你的二叉排序树可能画错了吧，我算得也是59/15

追问

把你画得给我看看吧。麻烦你了

追答

图如下