【数据结构】二叉排序树大题（二叉排序树的构建，及平均查找长度ASL）
记录一下数据结构大题啊，在大题里面经常会有一个二叉排序树。题目中会给出一组结点，然后让你写出二叉排序树的构建过程，计算查找成功平均查找长度（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
下一篇：flink部署-1.15