【数据结构】搜索二叉树的介绍与算法原理解析及实现

前言：有关一些二叉树的基础概念可以看看我之前的文章【数据结构】二叉树基本概念及堆的C语言模拟实现，虽然那篇文章和本篇文章的关系大概只有二叉与树，本文要实现的搜索二叉树主要是以非递归的方式来实现增、删、查

1. 搜索二叉树介绍

1.1 搜索二叉树概念介绍

二叉搜索树也可以叫做搜索二叉树，怎么叫取决于你，顾名思义它是一颗二叉树但搜索二叉树具有以下几个特殊的性质

1. 左子树所有节点 < 当前节点
2. 右子树所有节点 > 当前节点
3. 它的左右⼦树也分别为⼆叉搜索树
4. 二叉树可以支持插入相同的值，也可以不支持相同的值，这点要看使用的场景来决定，我这里实现的搜索二叉树并不支持插入相同值的元素

1.2 搜索二叉树性能分析

根据前面对搜索二叉树性质的观察，不难发现这颗树在搜索上有着比较明显的优势，这也正对应着它的名字，这颗树是为了搜索而生的。当要查找一个元素时，理想情况下当这颗树的形状比较的接近满二叉树（也就是比较平衡）时，它的查找就会变得像是二分查找那样效率很高
T ( N ) = O ( l o g N ) T(N)=O(logN)T(N)=O(logN)
但是当情况变得比较的极端时，这个二叉树有可能会退化成一个类似链表的结构，就像是如下图：

这个时候，再想去查找里面的某个元素时，时间复杂度就为最坏情况下的：
T ( N ) = O ( N ) T(N)=O(N)T(N)=O(N)
但是这种比较极端的情况毕竟比较的少，所以它的查找平均时间复杂度为：
O ( l o g N ) O(logN)O(logN)
因此关于搜索二叉树的性能可以总结成下面的表格：

为了解决这种极端的情况，有些比较高级的数据结构对搜索二叉树进行了升级，使得这颗树获得了自动保持平衡的能力，也就是红黑树、AVL树、B树，但这里我们先不做介绍，想要了解这些高级的数据结构还是先得把基础给打好，从实现这个不平衡的搜索二叉树开始，后面再慢慢过渡到高级的数据结构

2. 搜索二叉树的实现算法逻辑

2.1 搜索二叉树插入元素

插入元素比较的简单，主要是分为两种情况：

1.当树为空树的时候：

2.当树不为空，那就按照二叉搜索树的性质来走，让这个值每遍历到一个结点，让这个值和这个结点的值做比较，如果值要比较小，就往该结点的左孩子走，反正如果要大就往该结点的右孩走，当找到空位置时就直接插入就可以了：

3.下面我实现的二叉搜索树是不支持重复元素的，所以到时候发现重复元素就直接退出了，想要允许重复元素的话也可以，往左走还是往右走随你，但是一定要保证逻辑一致，不然就全乱了

2.2 查找元素

查找元素相比于插入元素的逻辑来说更加的简单，首先从根部的位置开始，如果元素比该结点大就往右左，如果小就往左走，发现相等了就退出并返回true, 如果都找到空了还是没有就说明该树没有这个元素的结点，返回一个false即可

但是有一点需要注意，如果实现的是一颗支持存放相同元素的搜索二叉树时，就要把迭代改成DFS，并且以中序遍历到的第一个元素为准，比如在下面的图中，存在着两个结点3那就返回中序遍历的第一个结点（也就是1的右孩子）：

2.3 搜索二叉树的删除

这里是搜索二叉树的难点，也是搜索二叉树比较核心的操作之一，这里就先把算法逻辑给交代下。但是实际实现上有很多种细节需要处理也是让我调了挺久，且需要分出很多种情况来处理反正我写的时候，就代码实现来说我都套了有5层的 if、else 了，当然大多数代码就只是在复读机，把逻辑想清楚CV一下改改还是很快的。

想要删除树的某个结点时，主要分为下面的四种情况：

1. 要删除的结点的左右子树都为空时，也就是为叶子结点时，这是最好处理的情况直接把该结点删除就可以了，比如这里我们想要删除结点1，直接delete掉该结点即可：

2.当要删除的结点（N）左孩子为空，右孩子不为空时，我们可以把 N 结点的父亲指向 N 的那个的指针，让它直接指向 N 的右孩子：

3.和第二种情况类似，当要删除的结点（N）右孩子为空，左孩子不为空时，我们可以把 N 结点的父亲指向 N 的那个的指针，让它直接指向 N 的左孩子：

4.当要删除的结点 N 的左右都不为空时，会面临一种尴尬的境地，就是删除了 N 之后，N 的两个孩子没有安身之地，所以我们就不能用上面的两种方法。因此我们需要使用替换法来解决这个问题，那么我们要使用哪个结点来替换呢？ 观察搜索二叉树的性质不能发现，想要不破坏搜索二叉树的性质我们只能找到 N 的左子树的最大结点，或者是右子树的最小结点，然后与 N 结点做替换，接着再把 N 替换到的那个位置删除掉即可：

3. 搜索二叉树的代码实现

下面我们就来实现这个搜索二叉树，首先先让我们定义出单个结点的结构体与搜索二叉树这个类，这里为了更加的灵活且兼容更多的数据类型，我这里就都统一实现成模板，这样编译器就可以根据我们的需要实例化出我们需要存放指向数据的对象

3.1 结点与树的类定义

树结点的定义：

template<typenameK>structTreeNode{K _key;TreeNode<K>*_left;TreeNode<K>*_right;TreeNode(constK&key):_key(key),_left(nullptr),_right(nullptr){}};

二叉搜索树的定义：

template<typenameK>classBSTree{typedefTreeNode<K>Node;public://///private:Node*_root=nullptr;};

3.2 插入函数

boolInsert(constK&key){if(_root==nullptr){_root=newNode(key);returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{//实现一共不允许重复元素的二叉树，所以//找到相同的元素就直接返回returnfalse;}}cur=newNode(key);if(parent->_key<key)parent->_right=cur;elseparent->_left=cur;returntrue;}

3.2 查找函数

boolFind(constK&key)const{Node*cur=_root;while(cur){if(cur->_key<key){cur=cur->_right;}elseif(cur->_key>key){cur=cur->_left;}else{returntrue;}}returnfalse;}

3.3 删除函数

boolErase(constK&key){Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else// cur->_key == key{if(cur->_left==nullptr){// 处理下边界情况if(cur==_root){_root=cur->_right;deletecur;returntrue;}// 如果 cur 是 parent 的左孩子// 就把 parent 的 _left 链接上 cur 的 _rightif(parent->_left==cur){parent->_left=cur->_right;}else{parent->_right=cur->_right;}deletecur;returntrue;}elseif(cur->_right==nullptr){if(cur==_root){_root=cur->_left;deletecur;returntrue;}if(parent->_left==cur){parent->_left=cur->_left;}else{parent->_right=cur->_left;}deletecur;returntrue;}else// 要删除的结点有两个孩子的情况{// replaceParent要初始化成 cur, 否则// 当 _root == cur 时后面会引发空指针访问Node*replaceParent=cur;Node*replace=cur->_right;while(replace->_left)// 我这里找的是右子数中最小的{replaceParent=replace;replace=replace->_left;}cur->_key=replace->_key;if(replaceParent->_left==replace)replaceParent->_left=replace->_right;elsereplaceParent->_right=replace->_right;deletereplace;returntrue;}}}returnfalse;}

删除函数这里要考虑一下当 cur == _root 时的特殊情况，否则就会引发空指针访问的问题，剩下的东西我在注释里也有写，我这里就不在赘述了

3.4 中序遍历、构造拷贝、析构函数、赋值重载

// 让他强制生成默认构造BSTree()=default;BSTree(constBSTree&t){_root=copy(t._root);}BSTree<K>&operator=(BSTree<K>t){std::swap(this->_root,t._root);return*this;}~BSTree(){_root=Destroy(_root);}voidInOrder()const{_InOrder(_root);std::cout<<std::endl;}void_InOrder(constNode*cur)const{if(cur==nullptr)return;_InOrder(cur->_left);std::cout<<cur->_key<<' ';_InOrder(cur->_right);}Node*copy(constNode*cur){if(cur==nullptr){returnnullptr;}Node*newNode=newNode(cur->_key);newNode->_left=copy(cur->_left);newNode->_right=copy(cur->_right);returnnewNode;}Node*Destroy(Node*cur){if(cur==nullptr){returnnullptr;}cur->_left=Destroy(cur->_left);cur->_right=Destroy(cur->_right);deletecur;returnnullptr;}

这里要解释一下，为什么要专门写Destroy、copy、_InOrder这些小函数，首先这些小函数都是被private修饰的，而剩下的则全是被public修饰的，之所以这样设计是我想要通过递归来实现拷贝、 析构、 遍历， 而想要实现这样我又需要穿入_root但这样不安全，我不期望外界可以访问到这个_root，除了写一个getRoot函数外，我还可以通过上面的方法封装一层，这样就相对来说比较的安全

4. 搜索二叉树key / value 版的实现

搜索二叉树key / value 与普通的搜索二叉树的差别很小，只不过一个结点中多了value，你可以选择这个值是否可以被修改，我这里想要value可以被修改，所以在Find中我返回那个结点的指针，其他普通几乎都是直接 CV 一下上面的带么再简单改改就可以了，我这里就直接贴代码了：

#pragmaonce#include<iostream>namespaceKey_val{template<typenameK,typenameV>structTreeNode{K _key;V _value;TreeNode<K,V>*_left;TreeNode<K,V>*_right;TreeNode(constK&key,constV&valude):_key(key),_value(valude),_left(nullptr),_right(nullptr){}};template<typenameK,typenameV>classBSTree{typedefTreeNode<K,V>Node;public:// 让他强制生成默认构造BSTree()=default;BSTree(constBSTree&t){_root=copy(t._root);}BSTree<K,V>&operator=(BSTree<K,V>t){std::swap(this->_root,t._root);return*this;}~BSTree(){_root=Destroy(_root);}boolInsert(constK&key,constV&value){if(_root==nullptr){_root=newNode(key,value);returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{//实现一共不允许重复元素的二叉树，所以//找到相同的元素就直接返回returnfalse;}}cur=newNode(key,value);if(parent->_key<key)parent->_right=cur;elseparent->_left=cur;returntrue;}boolErase(constK&key){Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else// cur->_key == key{if(cur->_left==nullptr){// 处理下边界情况if(cur==_root){_root=cur->_right;deletecur;returntrue;}// 如果 cur 是 parent 的左孩子// 就把 parent 的 _left 链接上 cur 的 _rightif(parent->_left==cur){parent->_left=cur->_right;}else{parent->_right=cur->_right;}deletecur;returntrue;}elseif(cur->_right==nullptr){if(cur==_root){_root=cur->_left;deletecur;returntrue;}if(parent->_left==cur){parent->_left=cur->_left;}else{parent->_right=cur->_left;}deletecur;returntrue;}else// 要删除的结点有两个孩子的情况{// replaceParent要初始化成 cur, 否则// 当 _root == cur 时后面会引发空指针访问Node*replaceParent=cur;Node*replace=cur->_right;while(replace->_left)// 我这里找的是右子数中最小的{replaceParent=replace;replace=replace->_left;}cur->_key=replace->_key;cur->_value=replace->_value;if(replaceParent->_left==replace)replaceParent->_left=replace->_right;elsereplaceParent->_right=replace->_right;deletereplace;returntrue;}}}returnfalse;}// key/value 支持修改 val 所以这里稍作改动返回那个结点Node*Find(constK&key)const{Node*cur=_root;while(cur){if(cur->_key<key){cur=cur->_right;}elseif(cur->_key>key){cur=cur->_left;}else{returncur;}}returnnullptr;}voidInOrder()const{_InOrder(_root);std::cout<<std::endl;}private:void_InOrder(constNode*cur)const{if(cur==nullptr)return;_InOrder(cur->_left);std::cout<<cur->_key<<"->:"<<cur->_value<<' ';_InOrder(cur->_right);}Node*copy(constNode*cur){if(cur==nullptr){returnnullptr;}Node*newNode=newNode(cur->_key,cur->_value);newNode->_left=copy(cur->_left);newNode->_right=copy(cur->_right);returnnewNode;}Node*Destroy(Node*cur){if(cur==nullptr){returnnullptr;}cur->_left=Destroy(cur->_left);cur->_right=Destroy(cur->_right);deletecur;returnnullptr;}Node*_root=nullptr;};}

5.总结

本篇文章主要还是为了学习 红黑树 、AVL树、B树打基础，我们这里实现的搜索二叉树除了删除元素那里有点绕其他的地方也还好，几乎都在前面的文章都有涉猎过。

完