Question

数据结构学科提问：已知如下所示长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）

试按表中元素的顺序依次插入一查初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。网上有这道题的答案。我无法上传。> <但是我不知道这答案是怎么出来的。求教。

Answer 1

你要求的排序二叉树是时间序的还是字典序的？

追答

以字典序为序所对应的排序二叉树
Jan
/ \
Feb Mar
/ / \
Apr June May
\ / \
Aug July Sep
\ /
Dec Oct
/
Nov
ASL：树中第1层的结点1个，第2层的结点2个，第3层的结点3个，第4层的结点3个，第5层的结点2个，第6层的结点1个。所以平均查找长度为：（1*1+2*2+3*3+4*3+5*2+6*1）/12=42/12=3.5