【二叉树进阶】搜索二叉树（递归+非递归两种版本详解）_搜索树非递归查找

前言

二叉树在前面C数据结构阶段已经讲过，本节取名二叉树进阶是因为：

1. map和set特性需要先铺垫二叉搜索树，而二叉搜索树也是一种树形结构。
2. 二叉搜索树的特性了解，有助于更好的理解map和set的特性。
3. 二叉树中部分面试题稍微有点难度，在前面讲解大家不容易接受，且时间长容易忘。
4. 有些OJ题使用C语言方式实现比较麻烦，比如有些地方要返回动态开辟的二维数组，非常麻烦。

因此本节用C++语言对二叉树部分进行收尾总结。

我们之前学的普通的二叉树其实意义不大，因为如果只是用二叉树来存储数据的话，还不如直接用链表或者顺序表等这些顺序结构。

那二叉树搜索树相对来说，就比较有意义了。

1. 二叉搜索树的概念

那什么是二叉搜索树呢，先来了解一下它的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3. 它的左右子树也分别为二叉搜索树（即它的每一棵子树也满足其左子树所有结点的值都小于根结点的值，右子树的所有结点的值大于根结点的值）

为什么又叫二叉排序树呢？

仔细观察我们会发现如果对一棵搜索二叉树进行中序遍历的话

其实就能得到一个结点值的升序序列。

那了解了搜索二叉树的概念，接下来我们就来手撕一个搜索二叉树。

2. 二叉搜索树的结构

首先我们来定义一下结点和搜索二叉树的结构

我们之前定义一个模板类，一般都喜欢用T（type），但是在这里比较喜欢用K（key）

2.1 结点结构

2.2 树结构

相信大家很容易都能看懂，那这里我就不详细解释了。

3. 插入操作（非递归）

接下来我们来实现一下向搜索二叉树中插入元素的操作。

3.1 思路分析

首先对于搜索二叉树来说，它的插入应该有插入成功和插入失败（因为搜索二叉树一般不允许出现重复元素）两种情况。

我们来分析一下

首先看插入成功的情况：

在搜索二叉树中，要插入一个元素时，如果可以 插入，那么它插入的位置一定是确定的。
举个栗子

还是以这棵树为例，假设我们现在要插入一个12
那要怎么做呢？
其实就是从根结点开始，去找出那个合适的位置，然后把12放进去。
根结点的值是8，12大于8，所以应该去右子树找，8的右子树是10，12依然大于10，那再看10的右子树，是14，此时12小于14，所以就要往14的左子树，14的左子树为13，12小于13，所以再看13的左子树，是空。
所以，12就应该放在13的左子树上。

此时就插入成功了

那失败的情况呢？

比如，我们现在要插入一个13

首先还是根据大小去比较，找合适的位置，但是走到13的位置发现要插入的值和已经存在的值相等，那就直接return false，插入失败。

当然，如果插入的是第一个结点，那就不需要比较了，直接让它成为根结点。

3.2 代码实现

那我们来写一下代码

首先第一个插入的结点是比较特殊的，因为第一个要作为根结点：

那怎么判断是不是第一个插入的呢？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/421064?site