基于中序有序的二叉搜索树
什么是二叉搜索树
二叉搜索树是普通二叉树的升级，普通二叉树除了存储数据以外好像没有别的优势了，但是二叉搜索树不同，如果对搜索树采用中序遍历得到的结果是一串有序的数字。
二叉搜索树又称为二叉排序树，它要么是一棵空树，要么是一棵具有以下特点的树：
1.如果它的左子树不为空，那么它左子树上所有节点的值都小于根节点的值 2.如果它的右子树不为空，那么它右子树上所有节点的值都小于根节点的值 3.它的左右子树也是一棵二叉搜索树
它的结构如下：
template<class K>
struct BSTreeNode
{
//树的节点包含它的左子树和右子树指针以及这个节点中的值
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
//来个构造函数高一下子
BSTreeNode(int key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
class BSTree
{
public:
typedef BSTreeNode<K> Node;
private:
Node*_root；
};二叉搜索树的中序遍历
因为中序遍历得到的结果是一串有序的数字列，所以对于二叉搜索树而言中序遍历才是王道。但是因为中序遍历要从根节点开始，也就说要给函数传根节点，但是根节点作为成员变量是私有的，所以这里采用了嵌套的方式(将真正的中序遍历函数私有化，放出一个公有的调用接口）：
void Inorder()
{
//中序遍历
_Inorder(_root);
cout << endl;
}
private:
//因为中序遍历需要根作为参数，为了保持封装，在这里嵌套一下
void _Inorder(Node *root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_key << " ";
_Inorder(root->_right);
}二叉搜索树的查找
在一棵二叉搜索树中搜索一个元素，最坏的结果也就是O(N)，但如果这个搜索树一个接近完全二叉树的情况，则只需要查找高度次。
在这里插入图片描述
如果是一棵接近完全二叉，查找复杂度为O(logN)，目前我学过的查找中只有二分能达到这样的效率，但是二分有诸多限制，反而不如搜索二叉树来的强大。 所以后面还有平衡二叉树等对结果做进一步的限制，能大大的提升查找的效率
查找的非递归写法
在搜索树中查找某一个值，如果这个值比根节点的值要小，就往根的左子树中找；如果比根节点的值要大，就往右子树中找。
bool Find(const K& key)
{
if (_root == nullptr)
return false;
else
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
cur = cur->_left;
else if (cur->_key < key)
cur = cur->_right;
else
{
return true;
}
}
}
return false;
}查找的递归写法
//为了不破坏封装，这个函数要被设置成私有的
Node* _FindR(Node* root, const K& val)
{
//递归式查找
if (root == nullptr)
return nullptr;
if (root->_key > val)
{
return _FindR(root->_left, val);
}
else if (root->_key < val)
{
return _FindR(root->_right, val);
}
return root;
}
//这个是暴露在外面的公有接口
bool FindR(const K& val)
{
return _FindR(_root, val) == nullptr ? false : true;
}二叉搜索树的插入
向搜索树中插入不能破坏搜索树的结构，所以不能插入和树种元素相同的值
非递归
//二叉搜索树中序遍历结果是有序的数列，不允许往其中插入相同的值，插入删除不允许破坏结构
//它左孩子的值比根小，右孩子比根大
bool Insert(const K& key)
{
//插入，分为空树插入和非空树插入
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
else
{
//如果要插入的这个值比当前值要大就往右边走，否则就往左边走
Node* cur = _root;
Node* parent = cur;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;//不允许插入相同的值
}
}
//找到要插入的位置了，将值插入进去
cur = new Node(key);
//还要判断一下把这个节点链接在parent的左边还是右边
if (parent->_key > key)
parent->_left = cur;
else if (parent->_key < key)
parent->_right = cur;
}
return true;
}1.如果是向空树中插入，就直接new一个新节点作为根节点 2.如果是向非空树种插入，首先要找到插入位置，如果在寻找位置的时候发现相同值，直接返回false 3.找到合适位置以后，要将该节点与树链接起来，所以要提前准备一个父节点指针标记插入位置的父节点
递归
递归写法的唯一难处就是在于任何标记插入位置的父节点，这里我们可以采用引用的方式，这个引用用到这里真是妙绝
//递归插入的公共接口
bool InsertR(const K&val)
{
return _InsertR(_root, val);
}
//递归插入的私有函数
bool _InsertR(Node*& root, const K& val)//这里这个引用巨tm牛逼
{
if (root == nullptr)
{
//空就直接插入
root = new Node(val);
return true;
}
Node* cur = root;
while (cur)
{
if (cur->_key > val)
return _InsertR(cur->_left, val);
else if (cur->_key < val)
return _InsertR(cur->_right, val);
else
return false;//不允许相同的元素插入
}
}这里为什么给一个引用就能直接链接上呢？主要还是因为这一层的
root是上一层root->left或者root->right的别名
在这里插入图片描述
二叉搜索树的删除
删除操作是二叉搜索树种最难的一个，因为它涉及到的情况相对比较多
1.如果这个要被删除的节点有一个子树是空树，那么只要将不为空的子树交给被删除节点的父节点即可（这种方法又叫托孤），当然也不能排除这个要被删除的节点是根节点 2.如果这个被删除的节点的左右子树都不为空，那么就不能直接删除，我采用的是替换法删除，找该节点左子树中的最大值或者右子树的最小值作为替换值，然后将替换值的那个节点删除
非递归
bool Erase(const K& val)
{
//要删除这个节点，首先要找到这个节点
Node* cur = _root;
Node* parent =cur;
while (cur)
{
if (cur->_key > val)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < val)
{
parent = cur;
cur = cur->_right;
}
else
{
//这是找到节点了,开始删除，删除大概可以分为两种情况：1.它有一个空节点：托孤 2.它没有空节点：替换法删除
//有一个节点为空，判断是这个节点的哪个节点是空
if (cur->_left == nullptr)
{
//不排除cur是根节点
if (cur == _root)
{
_root = cur->_right;
}
else if (parent->_left == cur)//不是根节点，判读一下它是父节点的左孩子还是右孩子
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;//要把节点释放掉
}
else
{
//这是最后一种情况，要删除的节点两边都不为空，要找该节点左子树的最大节点或者右子树的最小节点来替换
Node* minRight = cur->_right;
while (minRight->_left)
{
parent = minRight;
minRight = minRight->_left;
}
//将值替换
cur->_key = minRight->_key;
//最左节点可能有右孩子，所以不能直接将最左节点删除
if (parent->_left == minRight)
parent->_left = minRight->_right;
else
parent->_right = minRight->_right;
delete minRight;
}
return true;
}
}
return false;
}递归
//递归删除的公共接口
bool EraseR(const K& val)
{
return _EraseR(_root, val);
}
bool _EraseR(Node*& root, const K& val)
{
if (root == nullptr)
return false;
Node* cur = root;
Node* parent = cur;
if (cur->_key > val)
return _EraseR(root->_left, val);
else if (cur->_key < val)
return _EraseR(root->_right, val);
else
{
//找到节点，删除
Node* del = root;//因为这里用的是引用的原因，不用再去记录父节点
if (root->_left == nullptr)
root = root->_right;
else if (root->_right == nullptr)
root = root->_left;
else
{
Node* rightMin = root->_right;
while (rightMin->_left != nullptr)//找到被删除节点的右树最小节点
{
rightMin = rightMin->_left;
}
root->_key = rightMin->_key;//找到了交换key
//对子树进行递归删除
return _EraseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归
}
delete del;
return true;
}
}二叉搜索树的使用场景
k模型
k模型就是以key作为关键码，结构中只需要存储key值即可。key模型的应用场景有很多，比如查找一本书中的错别字（将词库导入树种，再将书种的每个词去树中搜索一遍，找不到是错别字），比如鉴定一个车牌是否是该停车场的用户（只要将登记的车牌导入搜索树中，当有车来的时候将该车的车牌作为key值去树中检索以下即可）等。二叉搜索树就是一种key模型。
#pragma once
#include<iostream>
using namespace std;
//写一个二叉搜索树
namespace wbm
{
template<class K>
struct BSTreeNode
{
//树的节点包含它的左子树和右子树指针以及这个节点中的值
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
//来个构造函数高一下子
BSTreeNode(int key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
//有了单个节点，再来搞一下子结构
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
~BSTree()
{
//循环遍历释放节点，因为要传根节点，这里也考虑使用嵌套
Destory(_root);
_root = nullptr;
}
//二叉搜索树中序遍历结果是有序的数列，不允许往其中插入相同的值，插入删除不允许破坏结构
//它左孩子的值比根小，右孩子比根大
bool Insert(const K& key)
{
//插入，分为空树插入和非空树插入
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
else
{
//如果要插入的这个值比当前值要大就往右边走，否则就往左边走
Node* cur = _root;
Node* parent = cur;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;//不允许插入相同的值
}
}
//找到要插入的位置了，将值插入进去
cur = new Node(key);
//还要判断一下把这个节点链接在parent的左边还是右边
if (parent->_key > key)
parent->_left = cur;
else if (parent->_key < key)
parent->_right = cur;
}
return true;
}
//递归插入
bool InsertR(const K&val)
{
return _InsertR(_root, val);
}
//查找,找到返回节点，找不到返回空
bool Find(const K& key)
{
if (_root == nullptr)
return false;
else
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
cur = cur->_left;
else if (cur->_key < key)
cur = cur->_right;
else
{
return true;
}
}
}
return false;
}
bool FindR(const K& val)
{
return _FindR(_root, val) == nullptr ? false : true;
}
bool Erase(const K& val)
{
//要删除这个节点，首先要找到这个节点
Node* cur = _root;
Node* parent =cur;
while (cur)
{
if (cur->_key > val)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < val)
{
parent = cur;
cur = cur->_right;
}
else
{
//这是找到节点了,开始删除，删除大概可以分为两种情况：1.它有一个空节点：托孤 2.它没有空节点：替换法删除
//有一个节点为空，判断是这个节点的哪个节点是空
if (cur->_left == nullptr)
{
//不排除cur是根节点
if (cur == _root)
{
_root = cur->_right;
}
else if (parent->_left == cur)//不是根节点，判读一下它是父节点的左孩子还是右孩子
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;//要把节点释放掉
}
else
{
//这是最后一种情况，要删除的节点两边都不为空，要找该节点左子树的最大节点或者右子树的最小节点来替换
Node* minRight = cur->_right;
while (minRight->_left)
{
parent = minRight;
minRight = minRight->_left;
}
//将值替换
cur->_key = minRight->_key;
//最左节点可能有右孩子，所以不能直接将最左节点删除
if (parent->_left == minRight)
parent->_left = minRight->_right;
else
parent->_right = minRight->_right;
delete minRight;
}
return true;
}
}
return false;
}
//删除的递归
bool EraseR(const K& val)
{
return _EraseR(_root, val);
}
void Inorder()
{
//中序遍历
_Inorder(_root);
cout << endl;
}
private:
//因为中序遍历需要根作为参数，为了保持封装，在这里嵌套一下
void _Inorder(Node *root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_key << " ";
_Inorder(root->_right);
}
Node* _FindR(Node* root, const K& val)
{
//递归式查找
if (root == nullptr)
return nullptr;
if (root->_key > val)
{
return _FindR(root->_left, val);
}
else if (root->_key < val)
{
return _FindR(root->_right, val);
}
return root;
}
bool _InsertR(Node*& root, const K& val)//这里这个引用巨tm牛逼
{
if (root == nullptr)
{
//空就直接插入
root = new Node(val);
return true;
}
Node* cur = root;
while (cur)
{
if (cur->_key > val)
return _InsertR(cur->_left, val);
else if (cur->_key < val)
return _InsertR(cur->_right, val);
else
return false;//不允许相同的元素插入
}
}
bool _EraseR(Node*& root, const K& val)
{
if (root == nullptr)
return false;
Node* cur = root;
Node* parent = cur;
if (cur->_key > val)
return _EraseR(root->_left, val);
else if (cur->_key < val)
return _EraseR(root->_right, val);
else
{
//找到节点，删除
Node* del = root;//因为这里用的是引用的原因，不用再去记录父节点
if (root->_left == nullptr)
root = root->_right;
else if (root->_right == nullptr)
root = root->_left;
else
{
Node* rightMin = root->_right;
while (rightMin->_left != nullptr)//找到被删除节点的右树最小节点
{
rightMin = rightMin->_left;
}
root->_key = rightMin->_key;//找到了交换key
//对子树进行递归删除
return _EraseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归
}
delete del;
return true;
}
}
void Destory(Node* root)
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
private:
Node* _root=nullptr; //不写构造，直接给缺省值
};
}kv模型
kv模型其实是一种Key/Value模型，也就是指根据key值去查找value，单这种模型的一个节点中不但要存储key值还需要村粗value。这种模型的使用场景也常见，比如检索一个学生在图书馆借了多少本书（将学号作为key值检索，因为key值和value存储在一起，所以只要搜索到key就可以获取到value）。二叉搜索树不但可以作为key模型，还可以添加一个模板参数作为key/value模型。
namespace KV
{
template <class K,class V>
struct BSTreeNode
{
BSTreeNode(const K& key,const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_value(value)
{}
BSTreeNode<K,V>* _left;
BSTreeNode<K,V>* _right;
K _key;
V _value;
};
template <class K,class V>
struct BSTree
{
typedef BSTreeNode<K,V> Node;
BSTree()
:_root(nullptr)
{}
//插入节点
bool Insert(const K& key,const V& value)
{
if (_root == nullptr)
{
_root = new Node(key,value);//BSTreeNode对象中存放key值
}
else
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else//说明数字重复
return false;
}
cur = new Node(key, value);
//判断插入节点放在parent节点的左子树还是右子树
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
}
return true;
}
bool InsertR(const K& key,const V& value)
{
return _InsertR(_root, key, value);
}
//中序遍历
void InOrder()//因为外部取不到_root,所以这里套了一层调用函数
{
_InOrder(_root);
std::cout << std::endl;
}
//查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
return cur;
}
return nullptr;
}
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
//找到要删除的节点
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else//说明找到要删除的节点了
{
//开始分析三种情况
if (cur->_left == nullptr)//被删除节点左孩子为空。
{
if (cur == _root)//需要判断cur等于根节点的情况，否则else中parent空指针解引用了
{
_root = _root->_right;
}
else
{
if (parent->_left == cur)//确定cur是parent的左还是右，再进行“托孤”
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)//被删除节点左孩子不为空,右孩子为空
{
if (cur == _root)
{
_root = _root->_left;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
}
else//被删除节点左右孩子均不为空
{
//左右孩子均不为空，就需要左子树的最大值或右子树的最小值选出来当新根
Node* rightMin = cur->_right;//这里选用右树的最小值进行更换
Node* rightMinParent = cur;
while (rightMin->_left != nullptr)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
//std::swap(cur->_key, rightMin->key);//用std的交换对自定义类型可能比较慢
cur->_key = rightMin->_key;//还是用赋值好一点，即使是自定义类型，肯定有写赋值重载
cur->_value = rightMin->_value;
if (rightMinParent->_left == rightMin)//两种情况，第一种如图删除8，实际干掉9位置，需要将10的左连至9的右
rightMinParent->_left = rightMin->_right;
else if (rightMinParent->_right == rightMin)//第二种如图删除10，实际干掉14，需要将10的右连至14的右
rightMinParent->_right = rightMin->_right;
delete rightMin;
}
return true;
}
}
return false;
}
bool EraseR(const K& key)
{
return _EarseR(_root, key);
}
private:
Node* _root;
void _InOrder(Node* _root)
{
if (_root == nullptr)
{
return;
}
_InOrder(_root->_left);
std::cout << _root->_key << " "<<_root->_value;
_InOrder(_root->_right);
}
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)
return nullptr;
if (root->_key < key)
{
return _FindR(root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
return root;
}
bool _InsertR(Node*& root, const K& key, const V& value)//形参是root的引用
{
if (root == nullptr)
{
root = new Node(key,value);//因为root是父节点左/右孩子的别名，直接修改别名，链接关系存在，不用考虑父子节点连接关系
return true;
}
if (root->_key < key)
return _InsertR(root->_right, key，value);
else if (root->_key > key)
return _InsertR(root->_left, key，value);
else
return false;
}
bool _EarseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
return _EarseR(root->_right, key);
else if (root->_key > key)
return _EarseR(root->_left, key);
else//说明找到了要删除的节点,无需考虑root的父亲为空
{
Node* del = root;
if (root->_left == nullptr)
root = root->_right;
else if (root->_right == nullptr)
root = root->_left;
else//root左右子树均不为空
{
Node* rightMin = root->_right;
while (rightMin->_left != nullptr)//找到右树最小节点
{
rightMin = rightMin->_left;
}
root->_key = rightMin->_key;
root->_value = rightMin->_value;
return _EarseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归
}
delete del;
return true;
}
}
};
}
void testKV1()//中英互译
{
KV::BSTree<std::string, std::string> dic;
dic.Insert("data", "数据");
dic.Insert("algorithm", "算法");
dic.Insert("map", "地图、映射");
dic.Insert("Linux", "一款开源免费的操作系统");
std::string str;
while (std::cin >> str)
{
KV::BSTreeNode<std::string, std::string>* ret = dic.Find(str);
if (ret != nullptr)
{
std::cout << "中文翻译：" << ret->_value << std::endl;
}
else
std::cout << "查找失败！" << std::endl;
}
}
void testKV2()//用于统计次数
{
std::string arr[] = { "数学", "语文", "数学", "语文", "数学",
"数学", "英语","数学", "英语", "数学", "英语" };
KV::BSTree<std::string, int> count;
for (auto& e : arr)
{
KV::BSTreeNode<std::string, int>* ret = count.Find(e);
if (ret != nullptr)
{
ret->_value++;
}
else
{
count.Insert(e,1);
}
}
count.InOrder();
}当然在现实中如果涉及到大量的数据，我想一般都是通过数据来存储的，毕竟如果不是强制定时将数据刷新到磁盘中的话，程序的数据都是在内存中的，一旦断电，就容易发生数据丢失。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-10-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
