玩转二叉查找树

的内容，从根目录开始查询，结构如下：

• a图，需要5次;
• b图，需要3次;
• c图，需要8次;

由此可见，不同的形状，所需查找的次数是不一样的，关于这一点，后面我们在介绍平衡二叉查找树、红黑树这种数据结构的时候，会进行详细介绍。

虽然二叉查找树，在不同的形状下，查找效率不一样，但是它是学习其他树形结构的基础，了解了二叉查找树的算法，相信再了解其他二叉树结构会轻松很多。

二、算法思路

2.1、 新增

新增元素表示向二叉树中添加元素，比较简单。如果二叉树为空，默认第一个元素就是根节点，如果二叉树不为空，就以上面提到的特点为判断条件，进行左、右节点的



 

这种场景，稍微复杂一点，先定位到要删除的目标元素，根据左子节点内容一定小于当前节点内容特点，找到目标元素的左子树，通过递归遍历找到目标元素的左子树的右子树，找到最末端的元素之后，进行与目标元素进行替换，最后移除最末端元素。

2.4、 遍历

二叉树的遍历方式，分两类：

• 层次遍历，从根节点开始;
• 深度遍历，又分为前序、中序、后序遍历三种方式;

2.4.1、层次遍历

层次遍历，算法思路比较简单，从根节点开始，分层从左到右进行遍历元素。