文章目录
前言
普通的二叉树的增删查改是没有任何意义的；
所以当我们给树加以一些规则他就会发挥很大的作用；
二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
- 它的左右子树也分别为二叉搜索树；
- 默认情况下二叉树排序树的数据是不可以有冗余的，相同的数据是不可以再二叉搜索树里；
比如这颗二叉搜索树：
二叉搜索树，又叫搜索二叉树，也叫二叉排序树，都是根据中序排序该树，会得到有序升序序列而来的；
二叉搜索树存储数据的目的：为了查找，一颗长的好的二叉搜索树，有着极高的查找效率；
对于有个n个结点的二叉树：
查找效率最好可以达到O(logn);也就是树的高度嘛！
这是什么概念：100w个结点：只需要查找20次；10亿个结点只需要查找30次；
但是最坏也可以达到O(n)；这个一般都是出现在树长得不好情况；比如一些出现左单支右但单支，这直接退化成链表得形式了，虽然他们也满足二叉排序树的定义，但是这个查找效率就退到了O(n);
总结：一颗好的二叉树搜索树，查找效率达到O(logn),坏的二叉搜索树查找效率退化到了O(n);
好的二叉树，一般都接近完全二叉树的模样；
坏的二叉树，一般都解决单分支二叉树多的模样；
二叉搜索树的结构
# pragma once
//二叉排序树的结点
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key; //值域
BSTreeNode(const K& key)
:_left(nullptr),
_right(nullptr),
_key(key)
{}
};
//二叉排序树
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree() //构造函数
:_root(nullptr)
{}
private:
Node* _root;
};
二叉排序树的插入
/*
向二叉搜树插入数据，一定插入到叶子结点的位置
这个操作就类似单链表的插入链接好关系即可
*/
bool Insert(const K& key){
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* prev = nullptr;
Node* cur = _root;
//寻找要插入的位置
while (cur){
if (cur->_key < key){
prev = cur;
cur = cur->_right;
}
else if (cur->_key > key){
prev = cur;
cur = cur->_left;
}
else{
return false;
}
}
//退出循环表示cur到空，那么就开辟要插入结点的值
cur = new Node(key);
//到底链接到prev的左子树还是右子树，那么就判断以下叭
if (prev->_key < key){
prev->_right = cur;
}
else{
prev->_left = cur;
}
return true;
}
设计为返回bool目的为的是：插入二叉树已有值的结点，不插入；
插入的演示：
测试插入函数：
void testBSTree(){
BSTree<int> bs;
int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 ,5,5,5,5,5,5};
for (auto& e : a){
bs.Insert(e);
}
bs.InOrder();
}
int main(){
testBSTree();
return 0;
}
这里使用了InOrder中序遍历，这个函数也是封装再BSTree里面，很简单的；
测试结果:
虽然有重复的值，但是也没有被插进去
二叉搜索树的查找
二叉树的查找太简单了，要在二叉搜索树查找key,key比遍历到树当前结点的值域大，就往树的右边找，反之往左边找；
//查找
bool Find(const K& key){
if (_root->_key == key)
return true;
while (_root){
if (_root->_key < key){
_root = _root->_right;
}
else if (_root->_key > key){
_root = _root->_left;
}
else{
return true;
}
}
return false;
}
二叉搜索树的删除
二叉排序树需要考虑三种删除的情况：
- 删除的结点没有左右孩子
- 删除的结点只有一个孩子
- 删除的结点左右孩子都有
其中，删除的结点没有左右孩子，可以归到删除结点只有一个孩子的身上去；
而删除的结点只有一个孩子又分为删除的结点有左孩子和有孩子；
总结下来二叉排序树的删除，需要考虑这两种情况：
1.当我们删除的结点只有一个孩子时候：
如何删除呢？
我们可以考虑使用链表的方式删除，在链表操作中，我们删除一个结点，就是找到这个要删除的结点，同时找到要删除结点的前驱，让这个前驱指向要删除结点的后继我们就达到了删除的目的；
联想到二叉排序树的删除，我们也是找到要删除的结点，同时找到要删除结点的父节点，让父节点指向要删除结点的孩子就行；
但是重点来了，二叉树和链表最大的不同点是，二叉树是有两个指针域的，就是左孩子指针域和右孩子指针域，而链表只有一个后继指针域；这个说明什么问题呢？
这说明我们删除结点时候，它父节点的左指针域指向要删除结点的左孩子还是右孩子呢？它父节点的右指针域是要指向要删除结点的有孩子还是左孩子呢？ 这都是们需要考虑的问题；
所以总结下来：
当我们要删除的结点只有一个孩子时候：
1. 要删除的结点是父节点的左孩子，那么就让该父节点的左指针域指向要删除结点的左孩子，或者右孩子；
2. 要删除的结点是父节点的右孩子，那么就让父节点的右指针域指向要删除结点的左孩子或者右孩子；
比如下面的删除逻辑：删除的结点左指针为空的情况！（删除结点右指针和它的逻辑一致的）
删除8：它是父节点的右孩子，就让父节点的右指针域指向要删除结点的左孩子或者有孩子；那要指向哪个孩子，取决于要删除结点 8 的左孩子或者右孩子是不是有值；
删除1：它是父节点的左孩子，就让父节点的左指针域指向要删除结点的左孩子或者右孩子；那要指向哪个孩子，取决于要删除结点 1 的左孩子或者右孩子是不是有值；
视乎上面的逻辑很没有问题：但是当我们要删除的结点是根结点时候，我们要删除的结点就没有父节点了；，此时还是用上面的删除逻辑，只会导致空指针越界的问题：所以我们需要考虑到空指针的情况：
这样处理就很完美的解决父节点为空指针的问题；
2 .当我们要删除的结点只左右孩子都存在的时候：
我们就使用替代法删除：如何做呢？
替代法：只要我们找到要删除结点的左子树的最大值，或者右子树的最小值，使用它去替代要删除的结点，再去删除左子树的最大值，或者右子树的最小值就可以；这样我们又转化为删除只有一个孩子结点的情况了
我们一般使用的思路是：找右子树的最小值去替代要删除的结点（当然你找左子树的最大值也行）；
为什么这种方式可行呢？
因为这是二叉排序树，二叉排序树的特点是，根节点值一定比左子树所有值要大，右子树要所有制要小；所以当我们要删除的结点都有左右孩子时候，只要找到右子树的最小值（因为右子树的最小值肯定是比要删除结点要大的值，并且比要删除结点左子树的所有值都要大，并要删除结点右子树的所有值要小）替换成要删除的结点即可；
举个例子：
删除二叉排序树的5结点
所以现在是问题是如何找到要删除结点右子树的最小结点呢？
上面的代码逻辑看着好像没什么问题？
因为删除5，那么就5右子树的最小结点6，把5替换成为6，再删除6；此时5的右树的最小结点好像肯定是左树；
但是你想以下：假如我要删除7呢？
7的右子树的最小结点还是左树吗？不是啊，因为7的右子树最小结点就是8了，我们就把7替换成8，再删除8，此时我们的minParent就是nullptr，那么上面代码逻辑就出问题了；
其实我们只要修改以下minParent为： minParent = cur;
所以删除的逻辑代码全部面貌：
//删除
bool Erase(const K& key){
Node* prev = nullptr;
Node* cur = _root;
while (cur){
if (cur->_key < key){
prev = cur;
cur = cur->_right;
}
else if (cur->_key > key){
prev = cur;
cur = cur->_left;
}
else{//找到key，开始删除
//1.删除的结点左结点为空
if (cur->_left == nullptr){
if (prev == nullptr)
_root = cur->_right;
else{
//判断 prev是左指针链接还是有指针要链接
if (prev->_left == cur)
prev->_left = cur->_right;
else
prev->_right = cur->_right;
}
delete cur; //释放要删除的结点
}
//1.删除的结点右结点为空
else if (cur->_right == nullptr){
if (prev == nullptr)
_root = cur->_left;
else{
//判断 prev是左指针链接还是有指针要链接
if (prev->_left == cur)
prev->_left = cur->_left;
else
prev->_right = cur->_left;
}
delete cur; //释放要删除的结点
}
else{ //要删除的结点左右子树不为空
/*思路：只要找到要删除结点的左子树最大值，或者右子树的最小值，用它来替换要删的结点cur
//再把左子树最大值，或者右子树最小值删掉即可；
//上面步骤做成功后，就可以满足要删的结点（被替换后的），左子树小于它，右子树也小于它
*/
//这里采用思路去右子树找最小值来替代(也就是去右子树中找最左结点注意这个最左结点不一定是叶子，但是最左结点的左子树一定为null)
//Node* minParent = nullptr; 直接赋值为空，可能会有空指针访问出错问题，这个问题会出现在，要删除结点的右子树没有左子树情况
Node* minParent = cur; //右子树最小值结点的父节点
Node* minRight = cur->_right; //minRight表示要删除删除结点的右子树最小的值
//右子树的最小值，可能是在它的左子树那，所以我们只要迭代去找到左子树即可
while (minRight->_left){
minParent = minRight;
minRight = minRight->_left;
}
//退出循环，表示找到了minRight
//把minRigth的值替换到要删除的结点cur
cur->_key = minRight->_key;
//替换成功后，要删除cur的变成要把minRihgt删除了，
//那么就是处理minRight的父节点minParent左右指针的链接关系了
//对于minRight的结点，我们只能保证它的左指针是nullptr，不能保证右指针一定为nullptr，可能也有结点
if (minParent->_left == minRight)
minParent->_left = minRight->_right;
else //这里处理的是要删除结点的cur右子树没有左子树的情况
minParent->_right = minRight->_right;
delete minRight;
}
return true;
}
}
return false;
}
二叉排序树的插入，删除，查找的递归实现
//递归版本的插入接口
bool InsertR(const K& key){
return _InsertR(_root, key);
}
//递归版本的查找接口
Node* FindR(const K& key){
return _FindR(_root, key);
}
//递归版本的删除接口
bool EraseR(const K& key){
return _EraseR(_root, key);
}
//递归版本的插入的子函数
//递归版本的问题，假如是有序插入很容易overflow
bool _InsertR(Node*& root, const K& key){
if (root == nullptr){ //当root == nullptr 时候，root同时也是即将要插入结点的 父节点的左右指针域
root = new Node(key);
}
if (key > root->_key){
return _InsertR(root->_right, key);
}
else if (key < root->_key){
return _InsertR(root->_left, key);
}
else{
return false;
}
}
//递归版本的查找的子函数
Node* _FindR(Node* root, const K& key){
if (root == nullptr){
reuturn nullptr;
}
if (key > root->_key){
return _Find(root->_right, key);
}esle if (key < root->_key){
return _Find(root->_key, key);
}
else{
return root;
}
}
//递归版本的删除子函数
bool _EraseR(Node*& root, const K& key){
if (root == nullptr){
return false;
}
//如果删除的结点不是根，那么就去左右子树找来删
if (root->_key < key){
return _EraseR(root->_right, key);
}
else if (root->_key > key){
return _EraseR(root->_left, key);
}
else{ //找到删除的结点root， root虽然是要删除的结点，但是同时也是要删除结点的父节点的左右指针域
Node* del = root;
if (root->_left ==nullptr ){
root = root->_right;
}
else if (root->_right == nullptr){
root = root->_left;
}
else{ //要删除的结点左右都不为空
Node* minRight = root->_right;
while (minRight->_left){
minRight = minRight->_left;
}
//把右子树的最小结点替换到要删除的结点中
std::swap(minRight->_key, del->_key);
//递归去要删除结点的右子树删除就可以啦
return _EraseR(root->_right, key);
}
delete del;
return true;
}
}
二叉排序树的代码所有实现
# pragma once
//二叉排序树的结点
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key; //值域
BSTreeNode(const K& key)
:_left(nullptr), _right(nullptr),
_key(key)
{}
};
//二叉排序树
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree() //构造函数
:_root(nullptr)
{}
/*
向二叉搜树插入数据，一定插入到叶子结点的位置
这个操作就类似单链表的插入链接好关系即可
*/
bool Insert(const K& key){
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* prev = nullptr;
Node* cur = _root;
//寻找要插入的位置
while (cur){
if (cur->_key < key){
prev = cur;
cur = cur->_right;
}
else if (cur->_key > key){
prev = cur;
cur = cur->_left;
}
else{
return false;
}
}
//退出循环表示cur到空，那么就开辟要插入结点的值
cur = new Node(key);
//到底链接到prev的左子树还是右子树，那么就判断以下叭
if (prev->_key < key){
prev->_right = cur;
}
else{
prev->_left = cur;
}
return true;
}
//查找
bool Find(const K& key){
Node* cur = _root;
if (cur->_key == key)
return true;
while (cur){
if (cur->_key < key){
cur = cur->_right;
}
else if (cur->_key > key){
cur = cur->_left;
}
else{
return true;
}
}
return false;
}
//删除
bool Erase(const K& key){
Node* prev = nullptr;
Node* cur = _root;
while (cur){
if (cur->_key < key){
prev = cur;
cur = cur->_right;
}
else if (cur->_key > key){
prev = cur;
cur = cur->_left;
}
else{//找到key，开始删除
//1.删除的结点左结点为空
if (cur->_left == nullptr){
if (prev == nullptr)
_root = cur->_right;
else{
//判断 prev是左指针链接还是有指针要链接
if (prev->_left == cur)
prev->_left = cur->_right;
else
prev->_right = cur->_right;
}
delete cur; //释放要删除的结点
}
//1.删除的结点右结点为空
else if (cur->_right == nullptr){
if (prev == nullptr)
_root = cur->_left;
else{
//判断 prev是左指针链接还是有指针要链接
if (prev->_left == cur)
prev->_left = cur->_left;
else
prev->_right = cur->_left;
}
delete cur; //释放要删除的结点
}
else{ //要删除的结点左右子树不为空
/*思路：只要找到要删除结点的左子树最大值，或者右子树的最小值，用它来替换要删的结点cur
//再把左子树最大值，或者右子树最小值删掉即可；
//上面步骤做成功后，就可以满足要删的结点（被替换后的），左子树小于它，右子树也小于它
*/
//这里采用思路去右子树找最小值来替代(也就是去右子树中找最左结点注意这个最左结点不一定是叶子，但是最左结点的左子树一定为null)
//Node* minParent = nullptr; 直接赋值为空，可能会有空指针访问出错问题，这个问题会出现在，要删除结点的右子树没有左子树情况
Node* minParent = cur; //右子树最小值结点的父节点
Node* minRight = cur->_right; //minRight表示要删除删除结点的右子树最小的值
//右子树的最小值，可能是在它的左子树那，所以我们只要迭代去找到左子树即可
while (minRight->_left){
minParent = minRight;
minRight = minRight->_left;
}
//退出循环，表示找到了minRight
//把minRigth的值替换到要删除的结点cur
cur->_key = minRight->_key;
//替换成功后，要删除cur的变成要把minRihgt删除了，
//那么就是处理minRight的父节点minParent左右指针的链接关系了
//对于minRight的结点，我们只能保证它的左指针是nullptr，不能保证右指针一定为nullptr，可能也有结点
if (minParent->_left == minRight)
minParent->_left = minRight->_right;
else //这里处理的是要删除结点的cur右子树没有左子树的情况
minParent->_right = minRight->_right;
delete minRight;
}
return true;
}
}
return false;
}
//中序遍历；
void InOrder(){
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root){
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root;
};
二叉排序树的应用
二叉排序树的应用有两种使用场景
- key模型的场景：主要是用来查找key值是否存在；
- key/val模型的场景：主要用来通过查找key值就找到val；key和val是强相关的；
而对于我们那上面的实现代码，就是key模型：
我们只要简单的修改上面的代码就可以达到key /val的模型，其实就是给该key模型的二叉排序树增加多了一个val的成员，查找，插入，删除，依旧是对key进行操作；
二叉排序树Key/Val模型代码书写
namespace KV{
//二叉排序树的结点
template<class K,class V>
struct BSTreeNode
{
BSTreeNode<K,V>* _left;
BSTreeNode<K,V>* _right;
K _key; //值域
V _val;
BSTreeNode(const K& key,const V& val)
:_left(nullptr), _right(nullptr),
_key(key),
_val(val)
{}
};
//二叉排序树
template<class K,class V>
class BSTree
{
typedef BSTreeNode<K,V> Node;
public:
BSTree() //构造函数
:_root(nullptr)
{}
/*
向二叉搜树插入数据，一定插入到叶子结点的位置
这个操作就类似单链表的插入链接好关系即可
*/
bool Insert(const K& key,const V& val){
if (_root == nullptr)
{
_root = new Node(key,val);
return true;
}
Node* prev = nullptr;
Node* cur = _root;
//寻找要插入的位置
while (cur){
if (cur->_key < key){
prev = cur;
cur = cur->_right;
}
else if (cur->_key > key){
prev = cur;
cur = cur->_left;
}
else{
return false;
}
}
//退出循环表示cur到空，那么就开辟要插入结点的值
cur = new Node(key,val);
//到底链接到prev的左子树还是右子树，那么就判断以下叭
if (prev->_key < key){
prev->_right = cur;
}
else{
prev->_left = cur;
}
return true;
}
//查找
Node* Find(const K& key){
Node* cur = _root;
if (cur->_key == key)
return cur;
while (cur){
if (cur->_key < key){
cur = cur->_right;
}
else if (cur->_key > key){
cur = cur->_left;
}
else{
return cur;
}
}
return nullptr;
}
bool Erase(const K& key){
Node* prev = nullptr;
Node* cur = _root;
while (cur){
if (cur->_key < key){
prev = cur;
cur = cur->_right;
}
else if (cur->_key > key){
prev = cur;
cur = cur->_left;
}
else{//找到key，开始删除
if (cur->_left == nullptr){
if (prev == nullptr)
_root = cur->_right;
else{
//判断 prev是左指针链接还是有指针要链接
if (prev->_left == cur)
prev->_left = cur->_right;
else
prev->_right = cur->_right;
}
delete cur; //释放要删除的结点
}
else if (cur->_right == nullptr){
if (prev == nullptr)
_root = cur->_left;
else{
//判断 prev是左指针链接还是有指针要链接
if (prev->_left == cur)
prev->_left = cur->_left;
else
prev->_right = cur->_left;
}
delete cur; //释放要删除的结点
}
else{ //要删除的结点左右子树不为空
/*思路：只要找到要删除结点的左子树最大值，或者右子树的最小值，用它来替换要删的结点cur
//再把左子树最大值，或者右子树最小值删掉即可；
//上面步骤做成功后，就可以满足要删的结点（被替换后的），左子树小于它，右子树也小于它
*/
//这里采用思路去右子树找最小值来替代(也就是去右子树中找最左结点注意这个最左结点不一定是叶子，但是最左结点的左子树一定为null)
//Node* minParent = nullptr; 直接赋值为空，可能会有空指针访问出错问题，这个问题会出现在，要删除结点的右子树没有左子树情况
Node* minParent = cur; //右子树最小值结点的父节点
Node* minRight = cur->_right; //minRight表示要删除删除结点的右子树最小的值
//右子树的最小值，一定是在它的左子树那，所以我们只要迭代去找到左子树即可
while (minRight->_left){
minParent = minRight;
minRight = minRight->_left;
}
//退出循环，表示找到了minRight
//把minRigth的值替换到要删除的结点cur
cur->_key = minRight->_key;
//替换成功后，要删除cur的变成要把minRihgt删除了，
//那么就是处理minRight的父节点minParent左右指针的链接关系了
//对于minRight的结点，我们只能保证它的左指针是nullptr，不能保证右指针一定为nullptr，可能也有结点
if (minParent->_left == minRight)
minParent->_left = minRight->_right;
else //这里处理的是要删除结点的cur右子树没有左子树的情况
minParent->_right = minRight->_right;
delete minRight;
}
return true;
}
}
return false;
}
//中序遍历；
void InOrder(){
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root){
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " "<<root->_val;
_InOrder(root->_right);
}
private:
Node* _root;
};
}
测试：
#include<iostream>
#include"BinarySearchTree.h"
#include<string>
using namespace std;
namespace KV{
void testBSTree(){
// 字典KV模型
BSTree<string, string> dict;
dict.Insert("sort", "排序");
dict.Insert("left", "左边");
dict.Insert("right", "右边");
dict.Insert("map", "地图、映射");
//...
string str;
while (cin >> str)
{
BSTreeNode<string, string>* ret = dict.Find(str);
if (ret)
{
cout << "对应中文解释：" << ret->_val << endl;
}
else
{
cout << "无此单词" << endl;
}
}
}
}
int main(){
//K::testBSTree();
KV::testBSTree();
return 0;
}
key/val模型的二叉排序树，能够通过查找key值，找到对应的val；
