BSTree二叉树讲解-CSDN博客
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
二叉搜索树的概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
- 若它的左子树不为空则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
二叉树的运用改代码就是KV模型的二叉搜索树
1. K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到
的值。
比如给一个单词word判断该单词是否拼写正确具体方式如下
以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
2. KV模型每一个关键码key都有与之对应的值Value即<Key, Value>的键值对。该种方
式在现实生活中非常常见
比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英
文单词与其对应的中文<word, chinese>就构成一种键值对
再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出
现次数就是<word, count>就构成一种键值对。
二叉树的查找
a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。
b、最多查找高度次走到到空还没找到这个值不存在。
Node* _Find(Node* root,const K& key)
{
if (root == nullptr)//遇到空节点就返回
{
return nullptr;
}
if (root->_kv.first == key)
{
return root;
}
else if (root->_kv.first > key)
{
_Find(root->_left, key);
}
else
{
_Find(root->_right, key);
}
}二叉搜索树的插入
插入的具体过程如下
a. 树为空则直接新增节点赋值给root指针
b. 树不空按二叉搜索树性质查找插入位置插入新节点
bool _Insert(const pair<K, V>& kv)//这里使用pair——key,value模型 如字典
{
if (_root == nullptr)//如果该二叉树的树为空 就给个节点然后返回
{
_root = new Node(kv);
return true;
}
//不为空就进行寻找 找到太该呆的位置
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
//判断该节点在父节点的左边还是右边
if (parent->_kv.first > kv.first)
{
parent->_left = new Node(kv);
}
else
{
parent->_right = new Node(kv);
}
}
Node* _root = nullptr;
};二叉搜索树的删除
首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情
况
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程
如下
情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点
中再来处理该结点的删除问题--替换法删除
bool _Erase(Node* root, const K& key)
{
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
if (cur->_kv.first == key)//如果key与要搜索的值相等 就进行删除
{
if (cur->_left == nullptr)//左子树为空 右子树不为空
{//再考虑要删除的节点是他父节点的左子树还是右子树 将该节点接到其父节点上
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;//将该节点进行释放
}
else if (cur->_right == nullptr)//右子树不存在 左子树存在 同上
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
}
else//左右子树都存在 需要寻找一个可以代替该节点值的值
{//在左子树中找最小的值 就是左子树最左边的那个节点右节点就找右子树中最大的节点 就是右子树最右边的那个节点
Node* parent1 = nullptr;
Node* tmp = cur;
while (tmp->_left)//寻找左节点
{
parent1 = tmp;
tmp = tmp->_left;
}
swap(&cur->_kv, &tmp->_kv);//找到进行值的交换
parent1->_left = tmp->_right;//如果最小的左节点的左子树为空右子树不为空 将右子树接到该节点的父亲上 但是如果右子树为空 也可以将空节点接到其父节点上 不产生影响
delete tmp;//释放节点
}
}
else
{
if (root->_kv.first > key)
{
parent = cur;
cur = cur->_left;
}
else
{
parent = cur;
cur = cur->_right;
}
}
}
}
二叉树的遍历中序遍历将二叉树中key的值按顺序打印
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " " << root->_kv.second << endl;
_InOrder(root->_right);
}以下就是二叉搜索树的完整代码 以及对应的测试用例可以自行去调用测试。
#include<iostream>
#include<string>
using namespace std;
template<class K,class V>
struct BSTreeNode
{
typedef BSTreeNode<K, V> Node;
BSTreeNode(const pair<K, V>& x)
:_kv(x)
, _left(nullptr)
, _right(nullptr)
{
}
pair<K, V> _kv;
Node* _left;
Node* _right;
};
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
bool Insert(const K& key, const V& value)
{
pair<K, V> kv(key, value);
return _Insert(kv);
}
Node* Find(const K& key)
{
return _Find(_root,key);
}
bool Erase(const K& key)
{
return _Erase(_root, key);
}
void InOrder()
{
_InOrder(_root);
}
private:
bool _Erase(Node* root, const K& key)
{
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
if (cur->_kv.first == key)
{
if (cur->_left == nullptr)
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
}
else
{
Node* parent1 = nullptr;
Node* tmp = cur;
while (tmp->_left)
{
parent1 = tmp;
tmp = tmp->_left;
}
swap(&cur->_kv, &tmp->_kv);
parent1->_left = tmp->_right;
delete tmp;
}
}
else
{
if (root->_kv.first > key)
{
parent = cur;
cur = cur->_left;
}
else
{
parent = cur;
cur = cur->_right;
}
}
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " " << root->_kv.second << endl;
_InOrder(root->_right);
}
Node* _Find(Node* root,const K& key)
{
if (root == nullptr)
{
return nullptr;
}
if (root->_kv.first == key)
{
return root;
}
else if (root->_kv.first > key)
{
_Find(root->_left, key);
}
else
{
_Find(root->_right, key);
}
}
bool _Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
if (parent->_kv.first > kv.first)
{
parent->_left = new Node(kv);
}
else
{
parent->_right = new Node(kv);
}
}
Node* _root = nullptr;
};
void TestBSTree()
{
BSTree<string, string> dict;
dict.Insert("insert", "插入");
dict.Insert("erase", "删除");
dict.Insert("left", "左边");
dict.Insert("string", "字符串");
string str;
while (cin >> str)
{
auto ret = dict.Find(str);
if (ret)
{
cout << str << ":" << ret->_kv.second << endl;
}
else
{
cout << "单词拼写错误" << endl;
}
}
string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
// 统计水果出现的次
BSTree<string, int> countTree;
for (auto str : strs)
{
auto ret = countTree.Find(str);
if (ret == NULL)
{
countTree.Insert(str, 1);
}
else
{
ret->_kv.second++;
}
}
countTree.InOrder();
}