目录
一、二叉搜索树概念
二叉搜索树也叫做二叉排序树，它要么是一棵空树，要么具有以下性质:
（1）若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
（2）若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
（3）它的左右子树也分别为二叉搜索树
如下就是二叉搜索树，对于任何一个节点，它的左子树的所有节点值都比它小，它的右子树的所有节点值都比它大：
int a[] = {9,6,15,4,13,5,1,20,8,27};
总结：在左子树值比根小，右子树值比根大。 当树走中序遍历时，序列都是有序的。
二叉搜索树的结构定义：
#include<iostream>
using namespace std;
//树的节点可以支持多种类型
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;//根
};
二、二叉搜索树操作（非递归）
1.二叉搜索树的查找
（非递归）
二份查找借助排序查找，二叉搜索树借助结构
查找的时间复杂度，最坏查找高度次，就可以确认一个值在不在树中：
（1）当树接近完全二叉树或满二叉树 ，时间复杂度为O(N):
（2）查找的时间复杂度
最坏为O(N)
，如下这种情况：
因此二叉搜索树在极端情况下没办法保证效率。
（1）查找
查找比较简单：
①key比当前节点值大，向左走
②key比当前节点值小，向右走
③key等于当前节点值，找到了
//查找
Node* Find(const K& key)
{
Node* cur = _root;
if (cur->_key > key)//比当前节点小，就向左走
{
cur = cur->_left;
}
else if (cur->_key < key)//比当前节点大，就向右走
{
cur = cur->_right;
}
else
{
return cur;//找到了，返回
}
return nullptr;
}
（2）中序遍历
由于根节点的访问限定符是私有的，那么在main函数中要终须遍历一棵树时，就无法将二叉搜索树的对象根节点传给中序遍历，因为类外面访问不到私有成员。
因此可以这样考虑：这个二叉搜索树对象是有根节点的，可以考虑在里面套一层，给套在里面的函数传参_root ，去递归调用自己:
//内层函数使用_root
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);//递归调用自己
cout << root->_key << " ";
_Inorder(root->_right);//递归调用自己
}
//先调不传参数的InOrder
void InOrder()
{
//把_root传给子函数，让子函数去使用_root
_InOrder(_root);
cout << endl;
}
2.二叉搜索树的插入（非递归）
插入节点分两步：
（1）找位置
①key比当前节点值大，向左走
②key比当前节点值小，向右走
③key等于当前节点值，该节点值已经存在，插入失败
（2）插入
①key比父亲节点值小就插入父亲左子树
②key比父亲节点值大就插入父亲右子树
由于插入后，要将节点链接到树中，因此要定义parent节点，用来链接新节点：
//插入
bool Insert(const K& key)
{
//1.树为空
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//2.树不为空 非递归方式，两步：（1）找位置 （2）插入节点
//(1)找位置
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
{
return false;//树里面已经有这个节点了，就返回flase
}
}
//(2)插入节点
cur = new Node(key);
if(parent->_key > key)//比父亲节点值小就连接在父亲左子树
{
parent->_left = cur;
}
else
{
parent->_right = cur;//比父亲节点值大就连接在父亲右子树
}
return true;
}
3.二叉搜索树的删除（非递归）
（1）找位置
①key比当前节点值大，向左走
②key比当前节点值小，向右走
③key等于当前节点值，找到了，准备删除
（2）删除，有两种删除方法：非递归和递归
非递归删除:
①该节点没有孩子，即该节点是叶子节点，删除节点后把父亲指向自己的指针置空
②该节点有一个孩子，就把该节点的孩子节点的链接给该节点的父亲，顶替自己的位置，①可以当成②的特殊情况
③该节点有两个孩子，找比它自己的左孩子大，比它自己的右孩子小的节点替换它（也就是拿它的左子树的最大节点或右子树的最小节点替换它），替换之后，该节点就只有一个孩子或没有孩子了，就变成①或②了。
//删除
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)//比当前节点小，就往左走
{
parent = cur;//记录父亲位置
cur = cur->_left;
}
else if (cur->_key < key)//比当前节点大，就往右走
{
parent = cur;//记录父亲位置
cur = cur->_right;
}
else//找到了，要删除
{
//1.删除的是叶子节点, 删除节点后把父亲指向自己的指针置空
//2.删除的是有一个孩子的节点,就把它的孩子节点的链接给它的父亲，顶替自己的位置
//3.删除的是有两个孩子的节点，找比它自己的左孩子大，比它自己的右孩子小的节点替换它，
//也就是它的左子树的最大节点或右子树的最小节点替换它，它就只有一个孩子或没有孩子了
//第1可以当成第2去处理，当前节点的父亲节点指向空就可以了
if (cur->_left == nullptr)//cur左为空，就让父亲指向cur的右
{
//如果要删除根，直接让根的右孩子做根
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)//当cur是父亲的左时，就让父亲的左指向cur的右
{
parent->_left = cur->_right;
}
else//当cur是父亲的右时，就让父亲的右指向cur的右
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)//cur右为空，就让父亲指向cur的左
{
//如果要删除根，直接让根的右孩子做根
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)//当cur是父亲的左时，就让父亲的左指向cur的左
{
parent->_left = cur->_left;
}
else//当cur是父亲的右时，就让父亲的右指向cur的左
{
parent->_right = cur->_left;
}
}
delete cur;//删除
}
else//左右都不为空，替换法删除
{
//找右子树最左节点 当右子树的左孩子不为空时就继续遍历
Node* minRight = cur->_right;
Node* minParent = cur;//这里不要初始化成null，否则左为空时，minParent->_left就会崩掉
//当左不为空时，就一直向左走，直到找到右子树最左节点
while (minRight->_left)
{
minParent = minRight;
minRight = minRight->_left;
}
//保存替换节点的值
cur->_key = minRight->_key;
//删除替换节点
if (minParent->_left == minRight)//如果右子树最左节点是minParent的左，那就让minParent的左指向右子树最左节点的右
{
minParent->_left = minRight->_right;
}
else//如果右子树最左节点是minParent的右，那就让minParent的右指向右子树最左节点的右
{
minParent->_right = minRight->_right;
}
delete minRight;//删除
}
return true;
}
}
return false;//cur不存在，直接返回
}递归删除：
相对于非递归，只需要修改找到了要修改的代码：找到了后不需要管cur到底左为空、右为空、还是左右都不为空
① 找要删除节点的右子树的最小节点并把它的值保存起来
② 删除右子树的最小节点
③ 把要删除的节点值替换成右子树的最小节点值
else//左右都不为空，替换法删除
{
//找右子树最小节点
Node* minRight = cur->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
//用min保存右子树最小节点的值
K min = minRight->_key;
//递归调用自己去替换删除节点，一定会走到左为空的情况处理
this->Erase(min);
//删除完毕替换节点之后，把cur的值替换成min
cur->_key = min;
}
三、二叉搜索树操作（递归）
理解了非递归操作以后， 递归操作就很简单了：
#include<iostream>
using namespace std;
//树的节点可以支持多种类型
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:
//递归查找
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
//递归插入
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
//递归删除
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
Node* _root;
};由于_root是私有的，可以把递归子函数查找、插入、删除都定义成私有的
1.二叉搜索树的查找（递归）
递归查找：
private:
//查找
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)//没找到
{
return nullptr;
}
if (key < root->_key)//到左子树去找
{
FindR(root->_left, key);
}
else if (key > root->_key)//到右子树去找
{
FindR(root->_right, key);
}
else//找到了
{
return root;
}
}
2.二叉搜索树的插入（递归）
递归插入：当找到的位置为空时才插入
//插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)//找到位置了
{
root = new Node(key);
return true;
}
if (key < root->_key)//到左子树去找位置
{
_InsertR(root->_left, key);
}
else if (key > root->_key)//到右子树去找位置
{
_InsertR(root->_right, key);
}
else//已存在，无需插入
{
return false;
}
}
3.二叉搜索树的删除（递归）
递归删除：和二叉树的删除（非递归）一样，找到后的删除也有两种方式，递归和非递归
找到后的非递归删除：
//插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)//没找到
{
return false;
}
if (key < root->_key)//到左子树去找
{
_EraseR(root->_left, key);
}
else if (key > root->_key)//到右子树去找
{
_EraseR(root->_right, key);
}
else
{
//找到了，root就是要删除的节点
if (root->_left == nullptr)//root左为空
{
Node* del = root;
root = root->_right;
delete del;
}
else if (root->_right == nullptr)//root右为空
{
Node* del = root;
root = root->_left;
delete del;
}
else//root左右都不为空
{
//找到右子树最左节点替换
Node* minParent = root;
Node* minRight = root->_right;
while (minRight->_left)
{
minParent = minRight;
minRight = minRight->_left;
}
//保存替换节点的值
cur->_key = minRight->_key;
//链接
if (minParent->_left == minRight)
{
minParent->_left = minRight->_right;
}
else
{
minParent->_right = minRight->_right;
}
//删除
delete minRight;
}
return true;
}
}找到后的递归删除：
else//root左右都不为空
{
//找右子树最左节点
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
//保存右子树最左节点的值
K min = minRight->_key;
//使用递归方法删除右子树最左节点
_Erase(root->_right, min);
}
四、二叉搜索树的默认成员函数
现在还剩下二叉搜索树的构造、拷贝构造、赋值运算符重载、析构函数。
1.构造
前面已经写过构造函数了, 即只需要把根初始化为空就行了:
public:
//构造函数需要将根初始化为空就行了
BSTree()
:_root(nullptr)
{}
2.拷贝构造
拷贝构造利用递归调用子函数不断拷贝节点:
//拷贝构造
BSTree(const BSTree<K>& t)
{
_root = t.copy(t._root);
}在子函数处:
Node* _copy(Node* root)
{
if (root == nullptr)//如果根为空，直接返回
{
return;
}
Node* copyNode = new Node(root->_key);//创建根节点
copyNode->_left = _copy(root->_left);//递归拷贝左子树节点
copyNode->_right = _copy(root->_right);//递归拷贝右子树节点
return copyNode;//返回根
}
3.赋值运算符重载
借助拷贝构造用现代写法写:
//赋值运算符重载(现代写法)
BSTree& operator=(const BSTree<K>& t)
{
swap(_root,t._root);
return *this;
}
4.析构
递归调用子函数去析构
//析构
~BSTree()
{
_Destroy(_root);
_root = nullptr;
}在子函数处:
_Destroy(root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
五、K模型和KV模型搜索树
1.K模型搜索树
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。K模型不存在重复值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
（1）以单词集合中的每个单词作为key，构建一棵二叉搜索树
（2）在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
#pragma once
#include<iostream>
using namespace std;
namespace K
{
//树的节点可以支持多种类型
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;
private:
//查找
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)//没找到
{
return nullptr;
}
if (key < root->_key)//到左子树去找
{
FindR(root->_left, key);
}
else if (key > root->_key)//到右子树去找
{
FindR(root->_right, key);
}
else//找到了
{
return root;
}
}
//插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)//找到位置了
{
root = new Node(key);
return true;
}
if (key < root->_key)//到左子树去找位置
{
_InsertR(root->_left, key);
}
else if (key > root->_key)//到右子树去找位置
{
_InsertR(root->_right, key);
}
else//已存在，无需插入
{
return false;
}
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)//没找到
{
return false;
}
if (key < root->_key)//到左子树去找
{
_EraseR(root->_left, key);
}
else if (key > root->_key)//到右子树去找
{
_EraseR(root->_right, key);
}
else
{
//找到了，root就是要删除的节点
if (root->_left == nullptr)//root左为空
{
Node* del = root;
root = root->_right;
delete del;
}
else if (root->_right == nullptr)//root右为空
{
Node* del = root;
root = root->_left;
delete del;
}
else//root左右都不为空
{
//找右子树最左节点
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
//保存右子树最左节点的值
K min = minRight->_key;
//使用递归方法删除右子树最左节点
_Erase(root->_right, min);
}
return true;
}
}
Node* _copy(Node* root)
{
if (root == nullptr)//如果根为空，直接返回
{
return;
}
Node* copyNode = new Node(root->_key);//创建根节点
copyNode->_left = _copy(root->_left);//递归拷贝左子树节点
copyNode->_right = _copy(root->_right);//递归拷贝右子树节点
return copyNode;//返回根
}
_Destroy(root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
public:
//构造函数需要将根初始化为空就行了
BSTree()
:_root(nullptr)
{}
//拷贝构造
BSTree(const BSTree<K>& t)
{
_root = t.copy(t._root);
}
//赋值运算符重载(现代写法)
BSTree& operator=(const BSTree<K>& t)
{
swap(_root, t._root);
return *this;
}
//析构
~BSTree()
{
_Destroy(_root);
_root = nullptr;
}
//中序遍历
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);//递归调用自己
cout << root->_key << " ";
_Inorder(root->_right);//递归调用自己
}
//先调不传参数的InOrder
void InOrder()
{
//把_root传给子函数，让子函数去使用_root
_InOrder(_root);
cout << endl;
}
public:
//递归查找
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
//递归插入
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
//递归删除
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
Node* _root;
};
}
2.KV模型搜索树
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下：
（1）<单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较Key。
（2）查询英文单词时，只需给出英文单词，就可快速找到与其对应的key。
KV模型可以插入重复值，在K模型的基础上，节点增加了_value成员，用来_key去查找_value，_value的类型不确定，再增加一个模板参数即可：
namespace KV
{
//树的节点可以支持多种类型
template<class K, class V>
//树节点结构
struct BSTreeNode
{
BSTreeNode<K,V>* _left;//左指针
BSTreeNode<K,V>* _right;//右指针
K _key;
V _value;//增加了_value成员
//构造函数
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_value(value)//初始化_value成员
{}
};
template<class K, class V>//模板类型从K变成了KV
class BStree//树结构
{
typedef BSTreeNode<K,V> Node;//模板类型从K变成了KV
private:
//查找
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)//没找到
{
return nullptr;
}
if (key < root->_key)//到左子树去找
{
FindR(root->_left, key);
}
else if (key > root->_key)//到右子树去找
{
FindR(root->_right, key);
}
else//找到了
{
return root;
}
}
//插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲
bool _InsertR(Node*& root, const K& key, const V& value)//增加了_value成员
{
if (root == nullptr)//找到位置了
{
root = new Node(key, value);
return true;
}
if (key < root->_key)//到左子树去找位置
{
_InsertR(root->_left, key, value);
}
else if (key > root->_key)//到右子树去找位置
{
_InsertR(root->_right, key, value);
}
else//已存在，无需插入
{
return false;
}
}
bool _EraseR(Node*& root, const K& key,const V& value)//增加了_value成员
{
if (root == nullptr)//没找到
{
return false;
}
if (key < root->_key)//到左子树去找
{
_EraseR(root->_left, key, value);
}
else if (key > root->_key)//到右子树去找
{
_EraseR(root->_right, key, value);
}
else
{
//找到了，root就是要删除的节点
if (root->_left == nullptr)//root左为空
{
Node* del = root;
root = root->_right;
delete del;
}
else if (root->_right == nullptr)//root右为空
{
Node* del = root;
root = root->_left;
delete del;
}
else//root左右都不为空
{
//找右子树最左节点
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
//保存右子树最左节点的值
K kMin = minRight->_key;
V vMin = minRight->value;//增加了_value成员
//使用递归方法删除右子树最左节点
_Erase(root->_right, kMin);
root->_key = kMin;
root->_value = vMin;//增加了_value成员
}
return true;
}
}
Node* _copy(Node* root)
{
if (root == nullptr)//如果根为空，直接返回
{
return nullptr;
}
Node* copyNode = new Node(root->_key,root->_value);//创建根节点，增加了_value成员
copyNode->_left = _copy(root->_left);//递归拷贝左子树节点
copyNode->_right = _copy(root->_right);//递归拷贝右子树节点
return copyNode;//返回根
}
_Destroy(root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
public:
//构造函数需要将根初始化为空就行了
BSTree()
:_root(nullptr)
{}
//拷贝构造
BSTree(const BSTree<K>& t)
{
_root = t.copy(t._root);
}
//赋值运算符重载(现代写法)
BSTree& operator=(const BSTree<K>& t)
{
swap(_root, t._root);
return *this;
}
//析构
~BSTree()
{
_Destroy(_root);
_root = nullptr;
}
//中序遍历
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);//递归调用自己
cout << root->_key << ":" << root->_value<<endl;//增加了_value成员
_Inorder(root->_right);//递归调用自己
}
//先调不传参数的InOrder
void InOrder()
{
//把_root传给子函数，让子函数去使用_root
_InOrder(_root);
cout << endl;
}
public:
//递归查找
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
//递归插入
bool InsertR(const K& key,const V& value)//增加了_value成员
{
return _InsertR(_root, key, value);
}
//递归删除
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
Node* _root;
};
}
六、二叉搜索树性能分析
（1）查找效率代表了二叉搜索树中各个操作的性能，插入和删除操作都必须先查找。
（2）对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
（3）但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
例如按照序列{1,4,5,6,8,9,13,15,20,27}，构建二叉树：
元素相同，但是次序不同的序列{27,20,15,13,9,8,6,5,4,1}，构建二叉树:
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：
