C++数据结构二叉搜索树的实现应用与分析
目录
- 概念
- 二叉搜索树的实现
- 基本框架
- 二叉搜索树的插入
- 二叉搜索树的查找
- 二叉搜索树的删除（重点）
- 二叉搜索树的应用
- 二叉树性能分析
- 总结
⭐️博客代码已上传至gitee：https://gitee.com/byte-binxin/cpp-class-code
概念
二叉搜索树又称为二叉排序书，因为这棵树的中序遍历是有序的。二叉搜索树总结起来有以下几个性质：
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于于根节点的值
- 它的左右子树都是二叉搜索树
- 这棵树中没有重复的元素
二叉搜索树的实现
基本框架
由一个节点的成员构成，先构建节点的类型，和我们之前数据结构中的二叉树的节点定义是一样的。二叉搜索树的根节点先默认给空。
template <class K, class V>
struct BSTNode
{
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
K _key;
V _value;
BSTNode(const K& key, const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_value(value)
{}
};
template <class K, class V>
class BSTree //Binary Search Tree
{
typedef BSTNode<K, V> Node;
private:
Node* _root = nullptr;
};
二叉搜索树的插入
插入分为下面几个步骤：
- 先判断树是否为空，为空就让要插入的这个节点作为根节点，然后结束
- 部署就确定要插入节点的位置
- 用一个cur记录当前节点，parent记录父节点
- 要插入节点的值如果比当前节点的值小，cur就往左走，如果比当前节点的值大，就往右子树走，如果等于就返回false，表面这棵树中有这个数据，不需要插入。
下面是一个简单的动图演示
注意： 这里不用担心新插入节点会在树中间插入，它一定是在最下面插入的，它会走到最下面，然后在树的底部插入。
代码实现如下：
bool Insert(const K& key, const V& value)
{
// 没有节点时第一个节点就是根节点
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
// 用一个父亲节点记录cur的上一个节点
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
// 小于往左边走
if (key < cur->_key)
cur = cur->_left;
else if (key > cur->_key)
cur = cur->_right;
else
return false;// 已有的节点不插入，此次插入失败
}
cur = new Node(key, value);
// 判断应该插在父节点的左边还是右边
if (cur->_key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
为了更好地观察这棵树插入后是否有效，我们可以实现一个中序遍历，将其打印出来。 中序遍历代码如下：
void InOrder()
{
// 利用子函数遍历
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
测试代码如下：
void TestBSTree()
{
BSTree<int> bt;
int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
//int arr[] = { 1,2,3,4 };
//int arr[] = { 4,3,2,1};
for (auto e : arr)
{
bt.Insert(e);
}
bt.InOrder();
}
代码运行结果如下：
二叉搜索树的查找
查找的步骤如下：（和插入的步骤有些类似）
- 如果查找值key比当前节点的值小，就往左子树走
- 如果查找值key比当前节点的值大，就往右子树走
- 如果查找值key和当前节点的值相等，就返回当前节点的指针
代码实现如下：
Node* Find(const K& key)
{
if (_root == nullptr)
return nullptr;
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;
}
二叉搜索树的删除（重点）
二叉搜索树的删除相对来说会复杂一些，下面我要给大家分析一下。 有四种情况 先看下面这棵树，分别对以下四个节点进行删除会发生什么（如何处理）？
- 删除节点1时，它的左右都为空，可以直接删除
- 删除节点2时，它的左不为空右为空，删除方法如下：
还要分析一种特殊的情况，就是此时2没有父亲节点，也就是自己为根时，看下面如何操作
- 删除节点7时，它的左为为右不为空，删除方法如下：
和情况2一样，该节点如果为根节点，就让自己的右孩子变成根节点。
- 左右都不为空（替代法）
这种情况我们采用替代法来解决，替代法就是找一个节点和现在这个节点交换，然后转移为上面的情况，具体如下： 我们可以选择用左子树的最右节点（左子树最大的节点）或右子树的最左节点（右子树的最小节点）和当前节点互换，然后删除互换后的节点，这里我们统一采用用右子树的最右节点来进行替换。
然后这里可以转化为情况3来对节点进行删除，因为所有的最左孩子一定是左为空，右是不确定的。
总结： 一共有四种情况，但是情况1可以归为情况3，因为它也是左为空，所以整体处理下来是三种情况。
代码实现如下：
bool Erase(const K& key)
{
// 如果树为空，删除失败
if (_root == nullptr)
return false;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 小于往左边走
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
// 找到了，开始删除
// 1.左右子树都为空 直接删除 可以归类为左为空
// 2.左右子树只有一边为空 左为空，父亲指向我的右，右为空，父亲指向我的左
// 3.左右子树都不为空 取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
if (cur->_left == nullptr)
{
// 要删除节点为根节点时，直接把右子树的根节点赋值给——root
// 根节点的话会导致parent为nullptr
if (_root == cur)
{
_root = _root->_right;
}
else
{
// 左为空，父亲指向我的右
// 判断cur在父亲的左还是右
if (parent->_left == cur) // cur->_key < parent->_key
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
cur = nullptr;
}
else if (cur->_right == nullptr)
{
if (_root == cur)
{
_root = _root->_left;
}
else
{
// 右为空，父亲指向我的左
// 判断cur在父亲的左还是右
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
cur = nullptr;
}
else
{
// 找右子树中最小的节点
Node* rightMinParent = cur;
Node* rightMin = cur->_right;// 去右子树找
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
//swap(cur->_key, rightMin->_key);
// 替代删除
cur->_key = rightMin->_key;
// 转换成了第一种情况 左为空
if (rightMinParent->_left == rightMin)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
rightMin = nullptr;
}
return true;
}
}
return false;
}
测试代码如下：（要测试每种情况，还有测试删空的情况）
void TestBSTree()
{
BSTree<int> bt;
int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
for (auto e : arr)
{
cout << "插入 " << e << " 后：";
bt.Insert(e);
bt.InOrder();
}
cout << "------------------------------" << endl;
for (auto e : arr)
{
cout << "删除 " << e << " 后：";
bt.Erase(e);
bt.InOrder();
}
}
代码运行结果如下：
二叉搜索树的应用
二叉搜索树有两种模型：
- K模型： K模型只有key值，节点只存储key值。这里主要应用就是查找判断某个元素在不在。
- KV模型： KV模型每个key值都对应着一个value，主要应用就是通过key找value。（我们平时查找单词就是通过中文找英文，或者通过英文找中文）
下面我把上面的K模型的代码简单改造一下，实现KV模型：（这里没有使用传键值对的方法，之后的博客我会给大家介绍，这里使用传两个值的方式）
template <class K, class V>
struct BSTNode
{
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
K _key;
V _value;
BSTNode(const K& key, const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_value(value)
{}
};
template <class K, class V>
class BSTree //Binary Search Tree
{
typedef BSTNode<K, V> Node;
public:
~BSTree()
{
Node* cur = _root;
while (cur)
{
Erase(cur->_key);
cur = _root;
}
}
Node* Find(const K& key)
{
if (_root == nullptr)
return nullptr;
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;
}
// 用一个父亲节点记录cur的上一个节点
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
// 小于往左边走
if (key < cur->_key)
cur = cur->_left;
else if (key > cur->_key)
cur = cur->_right;
else
return false;// 已有的节点不插入，此次插入失败
}
cur = new Node(key, value);
// 判断应该插在父节点的左边还是右边
if (cur->_key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
bool Erase(const K& key)
{
// 如果树为空，删除失败
if (_root == nullptr)
return false;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 小于往左边走
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
// 找到了，开始删除
// 1.左右子树都为空 直接删除 可以归类为左为空
// 2.左右子树只有一边为空 左为空，父亲指向我的右，右为空，父亲指向我的左
// 3.左右子树都不为空 取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
if (cur->_left == nullptr)
{
// 要删除节点为根节点时，直接把右子树的根节点赋值给——root
// 根节点的话会导致parent为nullptr
if (_root == cur)
{
_root = _root->_right;
}
else
{
// 左为空，父亲指向我的右
// 判断cur在父亲的左还是右
if (parent->_left == cur) // cur->_key < parent->_key
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
cur = nullptr;
}
else if (cur->_right == nullptr)
{
if (_root == cur)
{
_root = _root->_left;
}
else
{
// 右为空，父亲指向我的左
// 判断cur在父亲的左还是右
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
cur = nullptr;
}
else
{
// 找右子树中最小的节点
Node* rightMinParent = cur;
Node* rightMin = cur->_right;// 去右子树找
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
//swap(cur->_key, rightMin->_key);
// 替代删除
cur->_key = rightMin->_key;
// 转换成了第一种情况 左为空
if (rightMinParent->_left == rightMin)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
rightMin = nullptr;
}
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->_value << endl;
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
void TestBSTree_KV1()
{
// 创建一个简易的字典
BSTree<string, string> dict;
dict.Insert("苹果", "apple");
dict.Insert("排序", "sort");
dict.Insert("培养", "cultivate");
dict.Insert("通过", "pass");
dict.Insert("apple", "苹果");
dict.Insert("sort", "排序");
dict.Insert("cultivate", "培养");
dict.Insert("pass", "通过");
string str;
while (cin >> str)
{
BSTNode<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "本字典无此词" << endl;
}
}
下面测试几个应用： 实例1 英汉字典
void TestBSTree_KV1()
{
// 创建一个简易的字典
BSTree<string, string> dict;
dict.Insert("苹果", "apple");
dict.Insert("排序", "sort");
dict.Insert("培养", "cultivate");
dict.Insert("通过", "pass");
dict.Insert("apple", "苹果");
dict.Insert("sort", "排序");
dict.Insert("cultivate", "培养");
dict.Insert("pass", "通过");
string str;
while (cin >> str)
{
BSTNode<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "本字典无此词" << endl;
}
}
}
代码运行结果演示：
实例2： 统计树
void TestBSTree_KV2()
{
// 统计水果个数
BSTree<string, int> countTree;
string strArr[] = { "香蕉","水蜜桃","西瓜","苹果","香蕉" ,"西瓜","香蕉" ,"苹果","西瓜","苹果","苹果","香蕉" ,"水蜜桃" };
for (auto e : strArr)
{
BSTNode<string, int>* ret = countTree.Find(e);
if (ret == nullptr)
{
// 第一次插入
countTree.Insert(e, 1);
}
else
{
ret->_value++;
}
}
countTree.InOrder();
}
代码运行结果如下：
二叉树性能分析
一般情况下，二叉搜索树的插入和删除的效率都是O(logN)，极端情况会导致效率变成O(N)。
理想状态： 完全二叉树：O(logN)
极端情况： 一条链：O(1)
后面我要和大家分析的AVL树会利用旋转，就可解决掉这种极端情况。
总结
上面这些是二叉搜索树的大致内容，其中删除大家可以好好理解一下，它后面还有两棵树我还没有介绍，就是AVL树和红黑树，在后面两篇博客我都会介绍。今天就先到这了，喜欢的话，欢迎点赞支持~
热门内容推荐
快捷栏目导航
