二叉排序树平均检索长度的计算
-
要计算二叉树首先需要先分层,关于如何分层,我们可以用到以下两个思路:
第一:层次遍历是要用到队列的,每层入队列的时候,可以将每层的开始和结尾做标记start和end,出队列出到end的时候,就是下一层开始了,就可以求出所有层的元素个数。这种分层方法在所有的二叉树中都可以使用;
第二:对于这种二叉排序树,根据其特点,每层都是从小到大的顺序排列,并且下一层的第一个一定比这一层的最后一个要小,所以,这个特点也可以作为分层依据。在层次遍历的同时,设一个max变量,如果值比max大,那么把该值赋值给max然后接着遍历,只要值比max小,就是新的一层,把该值赋给max之后开始新的计数。这种方法一般来说是比较常用的。
遇到相关的例子时,首先,我们需要先补全二叉树,可以看到有12个非成功的结点,这里我假设每个非成功查找结点概率相同,然后深度为3的非成功结点有4个,深度为4的非成功结点有8个。所以答案就是34+48。
西南地区IT社群(QQ)
- 云南
- 【昆明网页设计交流吧】243627302
- 【昆明nodejs交流吧】 243626749
- 【VUE】838405306
- 【云南程序员总群】343606807
- 【昆明UI设计】104031254
- 【云南软件外包】15547313
- 贵州
- 【PHP/java源码/站长交流群】55692114
- 四川
- 【成都Java/JavaWeb交流】86669225
- 【vaScript+PHP+MySql】116270060
- 【UI设计/设计交流学习群】135794928
- 重庆
- 【诺基亚 JAVA游戏博物馆】 559479780
- 【PHP,Java,Python,C++接单】 442103442
- 西藏