C++深入细致探究二叉搜索树

1、二叉搜索树的概念

 二叉搜索树又称二叉排序树，它可以是一颗空树，亦可以是一颗具有如下性质的二叉树：

  ①若根节点的左子树不为空，则左子树上的所有节点的值域都小于根节点的值

  ②若根节点的右子树不为空，则右子树上的所有节点的值域都大于根节点的值

  ③根节点的左右子树分别也是一颗二叉搜索树

例如下面的这棵二叉树就是一棵二叉搜索树：

注意：判定一棵二叉树是否为二叉搜索树一定要紧扣二叉搜索树的概念~

2、二叉搜索树的操作

声明：该文章讨论的是二叉搜索树中节点值唯一的情况。

二叉搜索树的查找

对于查找部分，充分利用二叉搜索树的特性，即右子树的value 大于根节点，左子树的value小于根节点。

例如：查找下图中的红色方框中的节点

以6对应的节点为列，查找过程主要经历如下几个步骤：

  ①6与根节点5比较，6 > 5,因此到5的右子树查找

&emsp;&emsp;①6与根节点7比较，6 < 7,因此到7的左子树查找

&emsp;&emsp;①6与根节点6比较，6 == 6,此时查找成功！

总结基本步骤：

若根节点不为空：

&emsp;&emsp;如果根节点的key == 查找的key----->返回true

&emsp;&emsp;如果根节点的key > 查找的key----->转到根节点的右子树查找

&emsp;&emsp;如果根节点的key < 查找的key----->转到根节点的左子树查找

否则（根节点为空了），直接返回false，表示树中不存在要查找的key

二叉搜索树的插入

主要分两大类的情况进行讨论：

1、树为空，直接插入

如下图所示：

2、树不空

①按照二叉搜索树的性质查找插入的位置

②插入新的节点

e.g:在下面的二叉搜索树中插入-1

第一步，查找插入位置：

&emsp;注意：要标记当前访问的节点的双亲，否则，就算找到了插入位置，由于无法访问其双亲，也是无法进行插入的。这里使用parent来标记当前访问节点的双亲节点。

具体过程如下图：

第二步，插入新节点

判断待插入节点(node)的值与parent标记的节点值的大小关系

if(node->value < parent->value)//新节点作为parent的左孩子
{
parent->left = node;
}
else//新节点作为parent的右孩子
{
parent->right = node;
}

来源：https://blog.csdn.net/Suk_god/article/details/124906501