二叉搜索树建立、插入、删除、前继节点、后继节点之c++实现
一、前言
一直以来，都对树有关的东西望而却步。以前每次说要看一看，都因为惰性，时间就那么荒废掉了。今天下个决心，决定好好的数据结构中的东西看一下。不知道看这篇文章的你，是不是和我有同样的感受，空有一颗努力的心，却迟迟没有付出行动。如果是的话，如果也想好好的把树的知识巩固一下的话，就让我们一起好好儿地把知识点过一遍吧。本文争取让看完的每一个没有基础的同学，都能有所收获。在正文开始前，先给自己加个油。加油↖(^ω^)↗
二、二叉搜索树的定义
二叉搜索树是指，对于某一个节点而言，它左边的节点都小于或等于它。而它右边的节点都大于或等于它。借用一下网上的图片（懒得自己画图了，请见谅）。如下图所示，是一个二叉搜索树，大家可以自己找几个节点试一试验证一下这个定义。
三、二叉搜索树有关的常见的操作
1、建立；
2、插入一个节点；
3、删除一个节点；
4、找出最小和最大的节点；
5、找出某个节点的前继节点和后继节点。
前面4条所做的工作比较好理解，但要理解第一条所做的工作，则需要明白什么是前继节点和后继节点。下面我们就一起回顾一下什么是前继节点，什么是后继节点把。(^o^)/~，加油！
前继节点：某个节点的前继节点，是指比该节点小的所有节点中的最大的一个节点。如在上图中，比节点“8”小的节点有很多个，但是最大的一个节点为“7”，那么节点“7”则为节点“8”的前继节点；
后继节点：某个节点的后继节点，是指比该节点大的所有节点中的最小的一个节点。如在上如中，比节点“1”大的节点有很多歌，但是最小的一个节点为“3”，那么节点“3”则为节点“1”的后继节点。
【插入】下面我们来分别理解一下，每种操作实现的具体步骤。建立一个二叉搜索树，其实是插入n个节点。而插入一个节点，我们是这么做的：
- 如果一个节点小于根节点，且根节点的左孩子为空的话，那么直接将该节点作为根节点的左孩子；
- 如果一个节点小于根节点，但是根节点的左孩子不为的话，那么我们将根节点的左孩子作为新的根节点，递归进行1、2两步。
- 同理，我们可以知道该怎么处理一个节点大于根节点的情况。
- 在这里有一个特殊的情况需要说明一下，那就是如果碰到重复的节点，本文采用软插入和软删除的办法。即我们设置一个变量用来表示该节点出现的次数，如果要插入的节点已经在二叉搜索树中存在的话，那么我们只需要把这个节点出现的次数变量加1。
如下图所示
【最大值&最小值】
找一个二叉树的最大值和最小值比较简单，因为二叉树的最小值肯定在二叉树的最左边，最大值肯定在二叉树的最右边。我们只需要使用一个循环，一直分别循环到节点的左节点或右节点为空，则可以得到二叉树的最大值和最小值了。
如上图中，最小节点为2，最大节点为18.
【前继节点】找一个节点的前继节点，我们分为两种情况
- 若该节点有左孩子，那么前继节点则为以该节点的左孩子为根节点所寻找到的最大值；
- 若该节点没有左孩子，那么前继节点需要往上寻找节点为右孩子。
如上图中，12的前继节点为10。
【后继节点】找一个节点的后继节点，我们分为两种情况
- 若该节点有右孩子，那么前继节点则为以该节点的左孩子为根节点所寻找到的最小值；
- 若该节点没有右孩子，那么前继节点需要往上寻找节点为左孩子。
如上图中，3的后继节点为4。
【删除】删除一个节点，我们也分为三种情况
- 如果待删除的节点即没有左孩子，也没有右孩子的话，则直接删除该节点，但是请注意需要将相应的父节点的修改。如：如果待删除的节点是父节点的左孩子的话，那么需要将父节点的左孩子节点置为空；
- 如果待删除的节点只有一个孩子，那么直接用该孩子代替这个节点。这里，同样需要注意修改父节点。即，如果待删除是父节点的左孩子，且它只有一个右孩子，那么删除这个节点需要将父节点的左节点指向待删除节点的右孩子；
- 如果待删除的节点有两个孩子的话，我们可以选择使用该节点的前继节点或者后继节点来代替该节点。大家可以在笔下试一试，就会发现两种替代方式，都能保证更新之后的二叉树依然满足二叉搜索树的定义。
如下图所示
完整代码
#include "代码运行结果：