目录
一、概念
二、代码实现
1.框架
2.查找
3.插入
4.删除
5.递归的写法
三、应用
一、概念
二、代码实现
1.框架
#pragma once
namespace utoKey
{
//结点
template<class K>
struct BinarySearchTreeNode
{
//结点的typedef
typedef BinarySearchTreeNode Node;
//
Node* _left;
Node* _right;
K _key;
//结点的构造函数，new操作时要调用
BinarySearchTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
//BST
template<class K>
class BinarySearchTree
{
typedef BinarySearchTreeNode Node;
public:
bool Find(const K& key);//查找
bool Insert(const K& key);//插入
bool Erase(const K& key);//删除
void InOrder();//中序遍历，结果是升序
private:
Node* _root;
};
}
2.查找
遍历整个BST，基于BST的特性，如果要查找的值key大于当前cur的值，则在右子树查找，反之，则在左子树查找。
bool Find(const K& key)//查找
{
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}3.插入
插入一定是插入到了空结点，即通过BST的特点确定的当前cur为空的地方。插入的第一个结点，直接插入即可。
a.树为空，则直接新增节点，赋值给root
指针
b.树不空，按二叉搜索树性质查找插入位置，插入新节点
bool Insert(const K& key)//插入
{
if (_root == nullptr)
{
_root = new Node(key);
return;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
//说明要插入的值已经存在了，提升插入失败
return false;
}
}
cur = new Node(key);
if (cur->_key > parent->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}4.删除
删除分为以下几种情况：
1.要删除的结点是叶子结点
2.要删除的结点只有一个子树
3.要删除的结点有左右两个子树。
- 如果是1，比如删除上图的4，则直接删除叶子结点即可
- 如果是2，比如删除上图的14，则把子树换到删除掉的位置，让10的右子树指向14的左子树
- 如果是3，比如删除3，则要采用替换算法，具体操作是：
a.找到左子树的最右结点（左子树最大）或者右子树的最左结点（右子树最小）
b.将找到的值替换到要删除的位置，转换为要删除右子树最左结点（或者左子树最右结点）
情况1、2可以看作同一种，比如删除叶子结点后，叶子结点的父指向为空。
如果当作情况2，其实等于父指向要删除结点的非空子树，而此时该非空子树为空。
情况3采用替换算法
实现思路
1.如果树为空，删除失败，返回空。
2.查找到要删除的结点
3.找到后分情况删除：
- 如果当前结点左子树为空：
判断当前结点是父的左还是右，如果是左，则父->左 = 结点->右；如果是右，则父->右 = 结点->左
存在一种特殊情况，就是删除左子树为空的根结点，此时父和要删除的结点为同一个。
则让非空子树成为新树即可。
- 如果当前结点右子树为空：
同上
- 如果左右子树都不为空：
a.先找到右子树的最左结点Rightmin，同时记住该结点的父亲
b.替换值
c.判断Rightmin是左子还是右子，Rightmin一定没有左孩子，让父指向Rightmin的右子
bool Erase(const K& key)//删除
{
if (_root == nullptr)
{
return false;
}
Node* cur = _root;
Node* parent = _root;
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_left;
}
delete cur;
return true;
}
else if(cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
return true;
}
else
{
Node* rightmin_parent = cur;
Node* rightmin = cur->_right;
while (rightmin->_left)
{
rightmin_parent = rightmin;
rightmin = rightmin->_left;
}
cur->_key = rightmin->_key;
if (rightmin_parent->_left == rightmin)
{
rightmin_parent->_left = rightmin->_right;
}
else
{
rightmin_parent->_right = rightmin->_right;
}
delete rightmin;
return true;
}
}
}
return false;
}5.递归的写法
//查找 bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
return false;
if (root->_key > key)
{
return _FindR(root->_left, key);
}
else if (root->_key < key)
{
return _FindR(root->_right, key);
}
else
{
return true;
}
}
//插入
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else
{
return false;
}
}
//删除
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else if (root->_key < key)
{
return _EraseR(root->_right, key);
}
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)
{
rightmin = rightmin->_left;
}
swap(rightmin->_key, root->_key);
return _EraseR(root->_right, key);
}
delete del;
return true;
}
}三、应用
1. K 模型： K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到 的值 。输出结果为bool类型，表示是否找到。比如：给一个单词 word ，判断该单词是否拼写正确 ，具体方式如下：以词库中所有单词集合中的每个单词作为key ，构建一棵二叉搜索树 ，在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。比如：小区的汽车进出，是否是该小区人员，判断是否允许进出。2. KV 模型：每一个关键码 key ，都有与之对应的值 Value ，即 <Key, Value> 的键值对 。该种方 式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系 ，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文 <word, chinese> 就构成一种键值对； 再比如统计单词次数 ，统计成功后，给定单词就可快速找到其出现的次数， 单词与其出 现次数就是 <word, count> 就构成一种键值对 。比如商场停车场，从停车场出去时，通过查找key即车牌找到记录<key，value>，value可能表示进入停车场的时间。
namespace utoKeyValue
{
//结点
template<class K,class V>
struct BinarySearchTreeNode
{
//结点的typedef
typedef BinarySearchTreeNode<K,V> Node;
//
Node* _left;
Node* _right;
K _key;
V _value;
//结点的构造函数，new操作时要调用
BinarySearchTreeNode(const K& key,const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_value(value)
{}
};
//BST
template<class K,class V>
class BinarySearchTree
{
typedef BinarySearchTreeNode<K,V> Node;
public:
BinarySearchTree() = default;
~BinarySearchTree()
{
Destory(_root);
}
Node* Find(const K& key)//查找
{
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
bool Insert(const K& key,const V& value)//插入
{
if (_root == nullptr)
{
_root = new Node(key,value);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
//说明要插入的值已经存在了，提升插入失败
return false;
}
}
cur = new Node(key,value);
if (cur->_key > parent->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
private:
Node* _root = nullptr;
void Destory(Node* root)
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
};
}
