已知一个长度为12的线性表 (Dec,Feb,Nov,Oct,Jul,Sept,Aug,Apr,May,Jun,Jan,Mar) (1）按照线性表中数据元素第一个字母的先后顺序构造出一棵二叉排序树。 (2)若每个数据元素的查找概率均等，查找此二叉排序树中任何一个结点的平均查找长 度。 3)若对线性表中的数据元素按照字典顺序从小到大排列，再采用折半查找方法进行查 找，则查找其中任意一个数据元素的平均查找长度是多少?

1. 按照线性表中数据元素第一个字母的先后顺序构造出一棵二叉排序树，其结构如下：

Dec
\
Feb
\
Nov
/ \
Jul Oct
\
Sept
/
Aug
/ \
Apr May
/ \
Jun Jan
/
Mar

2. 若每个数据元素的查找概率均等，则查找此二叉排序树中任何一个结点的平均查找长度为：

(1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 + 4 + 5) / 12 = 2.92

3. 若对线性表中的数据元素按照字典顺序从小到大排列，再采用折半查找方法进行查找，则查找其中任意一个数据元素的平均查找长度为：

log2(12) ≈ 3.58