二叉树的三种遍历非递归实现_二叉排序树是完全二叉树

二叉搜索树 —— 不能说完全没用，至少思想是经典的 　　前言 　　我们知道，「 顺序表 」 可以 「 快速索引 」 数据，而 「 链表 」 则可以快速的进行数据的「 插入 和 删除 」。那么，有没有一种数据结构，可以快速的实现 「 增 」「 删 」「 改 」「 查 」 呢？ 本文，我们就来聊一下一种 「 树形 」 的数据结构，它既有链表的快速插入与删除的特点，又有顺序表快速查找的优势。它就是：「 二叉搜索树 」



二叉搜索树的查找

二叉搜索树的删除

二叉搜索树的插入 　　一、二叉树的概念 　　在学习二叉搜索树之前，我们首先需要了解下什么是二叉树。英雄哪里出来：二叉树 —— 用递归来描述数据结构 　　二、二叉搜索树的概念 　　1、定义 　　二叉搜索树，又称为二叉排序树，二叉查找树，它满足如下四点性质： 　　1）空树是二叉搜索树； 2）若它的左子树不为空，则左子树上所有结点的值均小于它根结点的值； 3）若它的右子树不为空，则右子树上所有结点的值均大于它根结点的值； 4）它的左右子树均为二叉搜索树；

　　如图所示，对于任何一棵子树而言，它的根结点的值一定大于左子树所有结点的值，且一定小于右子树所有结点的值。 　　2、用途 　　从二叉搜索树的定义可知，它的前提是二叉树，并且采用了递归的方式进行定义，它的结点间满足一个偏序关系，左子树根结点的值一定比父结点小，右子树根结点的值一定比父结点大。 　　正如它的名字所说，构造这样一棵树的目的是为了提高搜索的速度，如果对二叉搜索树进行中序遍历，我们可以发现，得到的序列是一个递增序列。

　　3、数据结构 　　我们用孩子表示法来定义一棵二叉搜索树的结点。如下： 　　(1) 二叉搜索树结点的值，注意，这里的类型其实可以是任意类型，只要这种类型支持 关系运算符 的比较即可，本文为了把问题简单话，一律采用整数进行讲解。(2) 二叉搜索树结点的左儿子结点的指针，没有左儿子结点时，值为；(3) 二叉搜索树结点的右儿子结点的指针，没有右儿子结点时，置为； 　　4、结点创建 　　结点创建就是给结点分配一块内存，并且填充它的数据域和指针域，然后返回这个结点。C语言实现如下： 　　三、二叉搜索树的操作 　　1、查找 　　二叉搜索树的查找指的是：在树上查找某个数是否存在，存在返回，不存在返回。 　　1）算法原理 　　对于要查找的数，从根结点出发，总共四种情况依次判断： 　　1）若为空树，直接返回； 　　2）的值 等于 树根结点的值，则直接返回； 　　3）的值 小于 树根结点的值，说明对应的结点不在根结点，也不在右子树上，则递归返回左子树的 查找 结果； 　　4）的值 大于 树根结点的值，说明对应的结点不在根结点，也不在左子树上，则递归返回右子树的 查找 结果； 　　2）动图演示 　　如图所示，代表的是从一个二叉搜索树中查找一个值为 3 的结点。一开始， 3 比根结点 5 小，于是递归访问左子树；还是比子树的根结点 4 小，于是继续递归访问左子树；这时候比根结点 2 大，于是递归访问右子树，正好找到值为 3 的结点，回溯结束查找。

　　3）源码详解 　　(1) 这个函数用于查找以为根结点的树中是否存在值为这个结点；(2) 空树是不可能存在值为的结点的，直接返回；(3) 一旦发现有值为的结点，直接返回；(4) 的值 小于 树根结点的值，说明对应的结点不在根结点，也不在右子树上，则递归返回左子树的 查找 结果；(5) 的值 大于 树根结点的值，说明对应的结点不在根结点，也不在左子树上，则递归返回右子树的 查找 结果； 　　2、插入 　　二叉搜索树的插入指的是：将给定的值生成结点后，插入到树上的某个位置，并且保持这棵树还是二叉搜索树。 　　1）算法原理 　　对于要插入的数，从根结点出发，总共四种情况依次判断： 　　1）若为空树，则创建一个值为的结点并且返回； 　　2）的值 等于 树根结点的值，无须执行插入，直接返回根结点； 　　3）的值 小于 树根结点的值，那么插入位置一定在 左子树，递归执行插入左子树的过程，并且返回插入结果作为新的左子树； 　　4）的值 大于 树根结点的值，那么插入位置一定在 右子树，递归执行插入右子树的过程，并且返回插入结果作为新的右子树； 　　2）动图演示 　　如图所示，代表的是将一个值为 3 的结点插入到一个二叉搜索树中。一开始， 3 比根结点 5 小，于是递归插入左子树；还是比子树的根结点 4 小，于是继续递归插入左子树；这时候比根结点 2 大，于是递归插入右子树，右子树为空，则直接生成一个值为 3 的结点，回溯结束插入。

　　3）源码详解 　　(1) 函数用于将值为的结点插入到以为根结点的子树中；(2) 如果是空树，则创建一个值为的结点并且返回；(3) 的值 等于 树根结点的值，无须执行插入，直接返回根结点；(4) 的值 小于 树根结点的值，那么插入位置一定在 左子树，递归执行插入左子树的过程，并且返回插入结果作为新的左子树；(5) 的值 大于 树根结点的值，那么插入位置一定在 右子树，递归执行插入右子树的过程，并且返回插入结果作为新的右子树； 　　3、删除 　　二叉搜索树的删除指的是：在树上删除给定值的结点。 　　1）算法原理 　　删除值为的结点的过程，从根结点出发，总共四种情况依次判断： 　　1）空树，不存在结点直接返回空树； 　　2）的值 小于 树根结点的值，则需要删除的结点一定不在右子树上，递归调用删除左子树的对应结点； 　　3）的值 大于 树根结点的值，则需要删除的结点一定不在左子树上，递归调用删除右子树的对应结点； 　　4）的值 等于 树根结点的值，相当于是要删除根结点，这时候又要分三种情况： 　　4.1）当前树只有左子树，则直接将左子树返回，并且释放当前树根结点的空间； 　　4.2）当前树只有右子树，则直接将右子树返回，并且释放当前树根结点的空间； 　　4.3）当左右子树都存在时，需要在右子树上找到一个值最小的结点，替换新的树根，而其它结点组成的树作为它的子树，并且在子树中删掉这个最小的结点，而这一步删除的过程正是继续递归调用结点删除的过程； 　　2）动图演示 　　如图所示，下图展示的是，从这棵树删除根结点 5 的过程。首先，由于它有左右儿子结点，所以这个过程，根结点并不是真正的删除。而是从右子树中找到最小的结点 6，替换根结点，并且从根结点为 7 的子树中删除 6 的过程。由于 6 没有子结点所以这个过程就直接结束了。

　　3）源码详解 　　3.1）接口简介 　　在介绍二叉搜索树的结点删除算法前，我们首先需要知道以下四个接口： 　　(1) ：查找为根的树中，值最小的那个结点的值，根据二叉搜索树的性质，如果左子树存在，则必然存在更小的值，递归搜索左子树；如果左子树不存在，则根结点的值必然最小，直接返回，具体实现见下文；(2) ：在为根的树中，删除值为的结点，是我们需要实现的删除接口，具体实现见下文；(3) ：在为根的树中，将根结点删除，并且使得剩下的树还是二叉搜索树，具体实现见下文； 　　3.2）查找最小结点 　　(1) 如果左子树存在，则递归调用左子树的查找最小结点接口；(2) 如果左子树不存在，则当前根结点的值一定是最小的，直接返回接口； 　　3.3）删除给定结点 　　(1) 如果为空树，则直接返回空结点；(2) 如果需要删除的结点，是这棵树的根结点，则直接调用接口，下文会介绍它的实现；(3) 如果需要删除的结点的值 小于 树根结点的值，则需要删除的结点必定在左子树上，递归调用左子树的删除，并且将返回值作为新的左子树的根结点；(4) 如果需要删除的结点的值 大于 树根结点的值，则需要删除的结点必定在右子树上，递归调用右子树的删除，并且将返回值作为新的右子树的根结点；(5) 最后，返回当前树的根结点； 　　3.4）删除给定二叉搜索树的根结点，并且返回新的树根 　　(1) 如果左子树为空，则用右子树做为新的树根；(2) 如果右子树为空，则用左子树作为新的树根；(3) 否则，当左右子树都为非空时，利用，从右子树上找出最小的结点，作为新的根，并且在右子树中删除对应的结点，删除过程就是递归调用的过程； 　　4、构造 　　二叉搜索树的构造就是：给定一个数组序列，构造出一个棵二叉搜索树。 　　1）算法原理 　　原理比较简单，一开始是一棵空树，然后遍历数组，对每个素生成一个结点，不断执行插入操作，并且返回新的树根，就完成了构造的过程。 　　2）源码详解 　　(1) 初始化空树；(2) 根据数组给定顺序执行插入树的操作； 　　插入过程需要明确一点，就是如果给定的数组是严格递增，或者严格递减，就会导致每次插入都要遍历树的所有结点，这样就使得整个插入过程的时间复杂度变成了 O(n^2)，改善的方法有几种： 方法1：随机将数组打乱顺序，再执行插入； 方法2：每次插入后，变换成平衡树，对于平衡树相关内容，下篇文章会详细讲解； 　　四、二叉搜索树的遍历 　　1、先序遍历 　　给定一个某个二叉搜索树的先序遍历序列，构造出一棵二叉搜索树，方法如下： 　　1）首先，考虑先序遍历的特点：先访问根结点，再依次访问左右子树；所以，第一个结点一定是根结点； 　　2）然后，数组往后遍历的过程中，遇到的所有小于当前根结点的结点，都必然是左子树上的结点，后面的结点必然是右子树的（当然，如果检测到后面的结点有比这个根结点小的，则这个序列无法构造出一棵二叉搜索树）； 　　3）遍历找到左右子树的分界点后，就可以进行左右子树递归计算了，注意递归时返回构造完的子树的根结点。 　　2、中序遍历 　　二叉搜索树的中序遍历是最常用的，一棵二叉搜索树的中序遍历是一个递增序列。 　　递增序列是存在单调性的，所以可以利用这个特性，在有效的时间内找出这棵树的第 k 大结点。 　　3、后序遍历 　　给定一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果，方法如下： 　　1）从后序遍历的定义出发，先左子树，再右子树，最后根结点。所以，这个序列的最后一个素，一定是根结点，且所有小于它的素作为左子树，所有大于它的素作为右子树。 　　2）如果能够分成这样两部分，则递归计算左右子树； 　　3）否则，在出现第一个大于 最后一个素的情况下，又出现小于 最后一个素的情况，则表示这是一种非法情况，直接返回。 　　五、二叉搜索树的总结 　　纵观二叉搜索树的查找、插入 和 删除。完全取决于二叉搜索树的形状，如果是完全二叉树或者接近完全二叉树，则这三个过程都是
的，如果是斜树，则三个过程近似操作线性表，为
。



　　关于 「 二叉搜索树 」 的内容到这里就结束了。如果还有不懂的问题，可以通过 「 万人千题 」上的联系方式联系作者，线上沟通交流。 　　本文所有示例代码均可在以下 github 上找到：github.com/WhereIsHeroFrom/Code_Templates