原文内容来自免费考研论坛，请点击查看全文
http://bbs.freekaoyan.com/viewthread.php?tid=186067
我原来是直接带公式O(log2^n) ,那么结果就是O(log2^12),结果答案确是 37/12.
我又看了书上这部分内容,后来我用 ASL=1/n(1x1 2x2 ...)这个公式算出来了,确实为37/12. 是不是先算高度h,然后就用这个公式算,如果不是满2叉树,则最后一层结点数另算.是这样做的么? 我原来的做法错误是否因为O(log2^n)这个只是它的大O表示法而已?
---------------------------------
构造12节点的二叉判定树,第一层是1个节点,第二层是2个节点,第三层是4个节点,第四层是5个节点,因此查找成功时的平均查找长度ASL是(1*1 2*2 3*4 4*5)/12=37/12,即每层的节点个数乘以该层的所在的层数,再除以总的节点数目,而O(log2^n) 只是用来估算的,用于定性的分析.
---------------------------------
谢谢,证实了我的想法
---------------------------------
============================================
查找成功时的平均查找长度ASL即每层的节点个数乘以该层的所在的层数,
再除以总的节点数目,用于定量分析；
而O(log2^n) 只是用来估算的,用于定性的分析.
============================================

---------------------------------
楼上的回答很正确,支持!