数据结构实现 3.1：二分搜索树（C++版）

• 1. 概念及基本框架

• 2. 基本操作程序实现

• 2.1 增加操作

• 2.2 删除操作

• 2.3 查找操作

• 2.4 遍历操作

• 2.5 其他操作

• 3. 算法复杂度分析

• 3.1 增加操作

• 3.2 删除操作

• 3.3 查找操作

• 4. 完整代码

1. 概念及基本框架

二分搜索树 是一种 半线性结构 ，而且存储上属于 链式存储（即内存的物理空间是不连续的），是树形结构的一种。二分搜索树结构如下图所示：

首先，二分搜索树 作为 二叉树 的一种，有着二叉树的基本特性：
1.每个结点（ 根结点 除外）都有一个 前驱结点（即其父结点）。
2.每个结点至多有两个 后继结点（即其子结点）。
此外，二分搜索树还有一些特殊的特性：
1.每个结点 左孩子 及其后代的值都 小于 这个结点的值。
2.每个结点 右孩子 及其后代的值都 大于 这个结点的值。
3.结点的值 不重复 。
所以，能以二分搜索树结构存放的数据有着一条基本要：可比性 。
下面以一个我实现的一个简单的二分搜索树类来进一步理解二分搜索树。

和链表类似，首先设计一个 结点类 ，这个结点类包含 数据 和 指向左右两边结点的指针 。结点类的构造函数可以直接对结点赋值，然后利用结点类对象来创建一棵二叉搜索树。二叉搜索树类的设计如下：

这里为了避免重复设计就可以兼容更多数据类型，引入了 泛型 ，即 模板 的概念。（模板的关键字是 class 或 typename）

这里的 root 表示 根节点 ，m_size 表示 二分搜索树大小 。为了保护数据，这些变量都设置为 private 。
与链表不同的是，二分搜索树一般不需要引入 虚拟头结点 的概念。
实现了前面的程序之后，接下来就是一个二分搜索树的增、删、查以及一些其他基本操作，接下来利用代码去实现。

2. 基本操作程序实现

2.1 增加操作

首先，在类体内进行增加操作函数的原型说明。这里包括两个函数：
add (public)
add (private)
这里为什么这么做呢？因为对于树结构来讲，不管是增、删、改、查，还是遍历操作，根节点是一个很重要的结点。为了保护数据，这个结点一般对用户是屏蔽的，即用户不需要知道根节点就可以完成需要的操作。
而对于树结构来说，这些操作一般都是通过递归来实现的（某些操作使用了非递归的方式进行了实现），递归的时候往往需要结点参数，所以这里利用了一个 public 函数来调用另一个 private 函数实现操作，下面的操作也是这样。
注：树的操作也可以使用非递归的方式实现，这里只是为了方便代码编写以及理解，使用了递归的方式。同理，对于链表的操作而言，也可以使用递归的方式进行实现。

由于这些函数在类体外，所以每个函数头部必须添加一行代码：

表示该函数使用模板，下面同理。

注意理解这里私有的 add 函数，为了方便代码编写，特意加了返回值。如果不加返回值，函数是通过父结点连接要添加的子结点，而加了返回值就可以将子结点返回给父结点，操作更加简便。

2.2 删除操作

对于二分搜索树来说，为了保证删除操作完成后的树依旧是一棵二分搜索树，我们需要分三种情况讨论：
（1）欲删除结点左右子树均为空

若左右子树均为空，则直接删除该结点，并将其父结点指向删除结点的指针清空。

（2）欲删除结点左右子树仅一方为空

若左右子树仅一方为空，则删除该结点，并将该结点不为空的子树连接到删除结点的父结点指向删除结点的那一支。

（3）欲删除结点左右子树均不为空

若左右子树均不为空，就用删除结点的右边第一个结点的最左边的结点（即一直往左走，直到该结点的左子树为空的那个结点）来替换掉删除结点，然后删除掉该结点。而用来替换的那个结点的后代也注意需要维护，不能丢失。

同理，在类体内进行删除函数的原型说明。这里包括两个函数：
remove (public)
remove (private)
分别去实现它们。

2.3 查找操作

同样，查找操作也有两个函数：
contains (public)
contains (private)

2.4 遍历操作

树的遍历是一个很重要的概念，下面给出一张图来说明四种遍历的过程。
注：因为二叉树的遍历操作是通用的，所以这里并没有以二分搜索树为例子，而是一棵普通的二叉树。

二叉树的先（中或后）序遍历实际上表示的是结点被访问第几次会输出。
先序遍历表示第一次被访问时（橙色）会输出；
中序遍历表示第二次被访问时（绿色）会输出；
后序遍历表示第三次被访问时（黄色）会输出。
这三种遍历的递归版本比较容易实现，依靠输出位置的不同决定是哪一种遍历。这三种遍历实质上是一种 深度优先 遍历。而非递归版本比较难，下面也给出了一种程序实现方法。
注：这三种遍历的非递归版本利用调用栈来实现，这里我们使用了我们在 1.2 中实现的 数组栈 作为调用栈。
层序遍历表示一层一层（图中的蓝色虚线）的访问输出，使用的是非递归的方法，调用了一个队列来实现，层序遍历实质上是一种 广度优先 遍历。
注：层序遍历实现利用了我们在 1.4 中实现的 循环队列 作为调用队列。

这里遍历函数较多，一共有十个：
preOrder (public)：先序遍历
preOrder (private)
preOrder (public)：中序遍历
preOrder (private)
preOrder (public)：后序遍历
preOrder (private)
preOrderNR：先序遍历（非递归版本）
inOrderNR：中序遍历（非递归版本）
postOrderNR：后序遍历（非递归版本）
levelOrder：层序遍历
和前面的函数一样，递归版本的遍历函数有 public 和 private 两个，实现递归版本遍历的操作。然后又实现了三种遍历操作的非递归版本，以及层序遍历（非递归）。下面分别对它们进行实现。

2.5 其他操作

二分搜索树还有一些其他的操作，这些函数我在类体内进行了实现。
包括 二分搜索树大小 的查询等操作。

3. 算法复杂度分析

3.1 增加操作

因为二分搜索树的特有性质，这里平均复杂度是以 2 为底 n 的对数，简单写作 logn ，即其是对数级别的时间复杂度，下面的同理，这正是二分搜索树的优点。

3.2 删除操作

3.3 查找操作

总体情况：

因为二分搜索树的特有性质，所以操作的复杂度都是 O(logn) 级别的，和线性结构相比，（线性结构很多操作需要 O(n) 级别的时间复杂度）充分体现出二分搜索树这一结构的优点。

4. 完整代码

程序完整代码（这里使用了头文件的形式来实现类）如下：
其中，数组栈 类以及 循环队列 类的代码不再重复给出，如有需要，可以查看 1.2 和 1.4的内容。