数据结构是计算机考研的重要内容之一，数据结构的核心考点较多，复习较困难。为了帮助大家更好的了解和复习备考，小编为大家整理了2024计算机考研数据结构高频考点：二叉排序树的详细内容，一起来看看吧。
2024计算机考研数据结构高频考点：二叉排序树
　　一、定义
　　二叉排序树，又称“二叉查找树”，一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：左子树结点值<根节点值<右子树根节点值。
　　左子树上所有结点的关键字小于根结点，右子树上所有结点的关键字大于根结点，左右子树又各是一颗二叉排序树，中序遍历可得到递增有序数列。
　　二、查找操作
　　非递归实现，递归简单但效率低。
　　1.非递归形式：
　　1.若树非空，目标值与根节点的值进行比较：
　　若相等，则查找成功。
　　若小于根节点，则在左子树上查找，否则在右子树上查找。
　　查找成功，则返回结点指针。
　　如果最后一个结点也是错误的，那么就会执行：否则指向右子树查找，明知右子树为null，所以返回的就是null。
　　2.递归形式实现查找：
　　由于二叉排序树的递归特性，我们也可以用递归方式来实现查找。
　　三、插入
　　插入的新结点一定是某个叶结点(只有树为空的时候才会插入)。
　　四、构造
　　即使插入元素相同,顺序不同时,构造的BST也不同。
　　五、删除
　　叶子结点:直接删除，不会破坏二叉排序树的性质。
　　i只有一棵左/右子树:让i的子树成为i父结点的子树,替代i位置
　　i有左右两棵子树:令i的中序直接后继/前驱代替i,再删去直接后继/前驱,转换为1,2情况
　　六、查找效率分析
　　查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度。
　　平均查找长度ASL=(每层个数*对应层数)/总个数
　　较坏情况:类似有序单链表O(n)
　　较好情况:平衡二叉树O(㏒₂n)
　　查找过程:与二分查找类似,但二分查找的判定树唯一。
　　以上内容整理于网络，仅供参考。
　　以上就是学姐为大家整理的【2024计算机考研数据结构高频考点：二叉排序树】的全部内容！想了解更多关于考研的相关信息，请关注高顿考研官网查询，祝大家考研成功。另外，小编为2024考研的小伙伴们准备了丰富的学习资料，点击下方蓝色小卡片即可获取哦~
相关阅读
延伸阅读



展开全文