【数据结构】二叉排序树大题（二叉排序树的构建，及平均查找长度ASL）

Source

记录一下数据结构大题啊，在大题里面经常会有一个二叉排序树。题目中会给出一组结点，然后让你写出二叉排序树的构建过程，计算查找成功平均查找长度（asl）和查找成功平均查找长度。

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。（定义来自百度百科）

二叉排序树的性质

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）对二叉排序树做中序遍历会得到递增的有序序列。

给出一组结点

一般在题目中都按照给出的顺序进行二叉树排序

1、空集（有的需要写出是空集，有的第一步就从步骤2开始，看学校要求吧）

2、第一个结点是40，将40作为根节点

在这里插入图片描述

3、插入结点72，72>40，写在40的右子树。

在这里插入图片描述

4、插入结点38，38<40，写在左子树。

在这里插入图片描述

5、插入结点35，35<40，判断在左子树这边，35<38，所以在38这个结点的左子树。

在这里插入图片描述

6、插入结点67，67>40，67<72，写在72的右子树。

在这里插入图片描述

7、插入结点51，51>40，51<72，51<67，写在67的右子树。

在这里插入图片描述

8、插入结点90，90>40，90>72，写在72的左子树。

在这里插入图片描述

9、插入结点8，8<40，8<35，写在35的右子树。

在这里插入图片描述

10、插入结点55，55>40，55<72，55<67，55>51，写在51的左子树。

在这里插入图片描述

11、插入结点21，21<40，21<35，21>8，写在8的左子树。

在这里插入图片描述

二叉排序树平均查找长度为：

ASL（成功）= ∑（本层高度*本层元素结点个数）/结点总数。

以上述二叉排序树为例，在成功的条件下：
第一层结点，一个结点，查找一次
第二层，两个结点，查找两次
第三层，三个结点，查找三次
第四层，两个结点，查找两次
第五层，两个结点，查找两次
结点总数为10
ASL（成功）=（1×1+2×2+3×3+4×2+5×2）/ 10 = 3.2

ASL（失败）= ∑（本层高度*本层补上的叶子个数）/ 补上的叶子总数

以上述二叉排序树为例，在失败的条件下：
红色格子就是补上的叶子结点
在这里插入图片描述

补上的叶子总数是11
ASL（不成功）=（2×1+3×4+4×2+5×4）/ 11 = 42/11

作者：只识闲人不识君
日期：2022.03.19