🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

各位考研小伙伴们晚上好呀，接下来几篇文章将会为大家讲解下动态查找表的内容，动态查找表是一块很重要且比较难理解的内容，希望通过我们接下来几篇文章的讲解，大家都能更好的理解这部分内容，下面就开始我们的讲解吧！

一、基本概念

什么是动态查找表？

动态查找表即：表结构是在查找过程中动态生成的。对于给定的值key，若表中存在其关键字等于key的记录，则查找成功，否则插入关键字等于key的记录。

二、二叉排序树的查找

查找步骤：

（1）查找当前结点T，如果T为空或T结点的值等于key，返回当前结点；

（2）如果当前结点T的值小于key，在T的右子树继续进行查找，转到步骤1；

（3）如果当前结点T的值大于key，在T的左子树继续进行查找，转到步骤1；

举例分析：

假设有关键字序列（34，76，45，18，26，54，92），由这组记录关键字生成的二叉排序树为：

（1）查找45，先比较34，再比较76，再比较45相等则查找成功，比较次数为3次；

（2）查找92，先比较34，然后比较76，再比较92相等查找成功，比较次数为3次；

（3）查找30，先比较34，然后比较18，然后比较26，查找失败，比较次数为3次；

 需要注意查找的比较次数，考试经常会考比较次数。

三、二叉排序树的插入

插入步骤：

（1）首先使用查找算法查找当前二叉树中是否有待插入结点，返回待插入结点位置的指针（如果可以插入，会记录父结点的指针）；

（2）如果返回的父节点值为空，即：当前二叉排序树为空，则插入节点为根结点；

（3）如果当前值查找成功，即：当前二叉排序树中存在待插入值，则不再插入；

（4）如果返回待插入结点的父结点，则根据父结点的值进行插入；

（5）如果父节点大于待插入结点的值，则待插入结点为父结点的左孩子，否则为右孩子；

注意：新插入的结点总是叶子结点；

四、总结

二叉排序树作为考研中的一个重点，需要对其查找、插入、删除的原理熟练掌握，只有明白了算法的原理遇到对应的题目才能灵活处理。好了，今天先分享到这里，后面会对二叉排序树的删除以及平均查找长度进行讲解，敬请期待！

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬