前言
大家好吖,欢迎来到 YY 滴数据结构系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁
主要内容含:
欢迎订阅 YY滴C++专栏!更多干货持续更新!以下是传送门!
- YY的《C++》专栏
- YY的《C++11》专栏
- YY的《Linux》专栏
- YY的《数据结构》专栏
- YY的《C语言基础》专栏
- YY的《初学者易错点》专栏
- YY的《小小知识点》专栏
一.二叉搜索树的基本概念
二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
- 若它的左子树不为空,则 左子树 上所有节点的值都 小于 根节点的值
- 若它的右子树不为空,则 右子树 上所有节点的值都 大于 根节点的值
- 它的 左右子树 也分别为二叉搜索树 ;
二.增删查改基本操作
文章来源:https://www.toymoban.com/news/detail-755349.html
//结点模板
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
//在二叉搜索树模板中
typedef BSTreeNode<K> Node;
1.二叉搜索树的查找(分析&代码演示)
分析
- 从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找
- 最多查找高度次 ,走到到空,还没找到,这个值不存在。
代码演示
//查找操作
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)//从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;//最多查找高度次 ,走到到空,还没找到,这个值不存在。
}
2.二叉搜索树的插入(分析&代码演示)
分析
- 树为空,则直接新增节点,赋值给root指针
- 树不空, 按二叉搜索树性质的查找方式(前后指针) 找到插入位置,插入新节点
代码演示
//插入操作
bool Insert(const K& key)
{
//树为空,则直接新增节点,赋值给root指针
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//树不空, 按二叉搜索树性质的查找方式(前后指针) 找到插入位置,插入新节点
Node* parent = nullptr;//后指针
Node* cur = _root;//前指针
while (cur)
{
if (cur->_key < key)//比keycur的_key大,往右走
{
parent = cur;
cur = cur->_right;
}
else if(cur->_key > key)//比keycur的_key小,往左走
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//cur走到空了,开始给插入的key值创建结点,根据其比后一个结点(parent)大还是小,决定其是插在左还是右
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
3.二叉搜索树的删除【※核心重点】(分析&代码演示)
分析
- 首先查找元素是否在二叉搜索树中,如果不存在,则返回
- 否则要删除的结点可能分下面四种情况:
- 要删除的结点无孩子结点
- 要删除的结点只有左孩子结点
- 要删除的结点只有右孩子结点
- 要删除的结点有左、右孩子结点
- 对上面四种情况整理后(1与2,3分别结合),剩下下面2种情况(直接删除,替换法),分出3种具体情况(直接删除占两种):
- 直接删除情况: 只有左/右/无孩子结点(无孩子,只有一个孩子)
(双亲结点指向被删除节点的左还是右————取决于被删除节点是其双亲节点的左还是右节点)- 情况1:被删除节点是其双亲节点的左节点,删除该结点且使被删除节点的双亲结点指向被删除节点的 左孩子 结点
- 情况2:被删除节点是其双亲节点的右节点,删除该结点且使被删除节点的双亲结点指向被删除结点的 右孩子 结点
- 还要考虑结点为根结点情况:
- 替换法情况:【※核心难点】 (有两个孩子)
- 情况3 :在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题
- 分析:要 找到左子树的最大(右)结点,或者 右子树的最小(左)结点(下图演示中是找到左子树的最大结点)
- 具体过程分析:
- 设置前后指针,留一个cur指针指向要删除结点,parent指针跟着LeftMax指针向下逐个移动
- 找到leftMax以后,交换其和cur的数值,(收完尾后,最后一步再将指针也一同转移)
- 要分为两种情况(如下图所示) (1) leftMax指针的左指针为空,(2) leftMax指针的左指针不为空
(为什么不用讨论右指针呢?因为leftMax的右指针必定为空,否则leftMax会继续向下移动)- 因为采用的是前后指针法,所以这时留下的后指针(parent)就对应指向leftMax的左/右结点
- 最后将cur指针指向leftMax,leftMax动不动无所谓
代码演示
//删除操作
bool Erase(const K& key)
{
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 // 找到了
{
// 左为空
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_right == cur)//被删除节点是其双亲节点的右节点
{
parent->_right = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 右孩子 结点
}
else//被删除节点是其双亲节点的左节点
{
parent->_left = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 左孩子 结点
}
}
}
// 右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
}
// 替换法情况:左右都不为空
else
{
// 找替代节点
Node* parent = cur;
Node* leftMax = cur->_left;
while (leftMax->_right)
{
parent = leftMax;
leftMax = leftMax->_right;
}
swap(cur->_key, leftMax->_key);
if (parent->_left == leftMax)
{
parent->_left = leftMax->_left;
}
else
{
parent->_right = leftMax->_left;
}
cur = leftMax;
}
delete cur;
return true;
}
}
return false;
}
4.二叉搜索树的中序遍历(分析&代码演示)
分析
- 中序遍历要从通过模板实例化的树中调用中序遍历函数
- 需要传根结点指针,但是 根结点指针是在private域中,域外不能直接传一个根结点指针 ,所以要引入_InOrder函数,在二叉搜索树模板中 再次封装一层
代码演示
void TestBSTree1()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> t;
for (auto e : a)
{
t.Insert(e);
}
t.InOrder(); //需要传根结点指针,但是根结点指针是在private域中,域外不能直接传一个根结点指针,
//所以要引入_InOrder函数,在二叉搜索树模板中再次封装一层
}
//中序遍历——————————————————————————————————————————为了解决中序要传入根节点的问题,引入_InOrder函数
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
三.二叉搜索树的性能问题:需要AVL树…红黑树…
- 插入和删除操作都必须先 查找,查找效率代表了二叉搜索树中各个操作的性能
- 当二叉搜索树 退化为单支时,其效率为O(N),二叉搜索树的性能就失去了
- 对二叉搜索树进行改进后,得到的AVL树红黑树效率为 Log(N)
四.二叉搜索树的完整实现代码演示
//结点模板
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 Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
//插入操作
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
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;
}
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
//删除操作
bool Erase(const K& key)
{
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 // 找到了
{
// 左为空
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_right == cur)//被删除节点是其双亲节点的右节点
{
parent->_right = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 右孩子 结点
}
else//被删除节点是其双亲节点的左节点
{
parent->_left = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 左孩子 结点
}
}
}
// 右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
}
// 替换法情况:左右都不为空
else
{
// 找替代节点
Node* parent = cur;
Node* leftMax = cur->_left;
while (leftMax->_right)
{
parent = leftMax;
leftMax = leftMax->_right;
}
swap(cur->_key, leftMax->_key);
if (parent->_left == leftMax)
{
parent->_left = leftMax->_left;
}
else
{
parent->_right = leftMax->_left;
}
cur = leftMax;
}
delete cur;
return true;
}
}
return false;
}
//中序遍历——————————————————————————————————————————为了解决中序要传入根节点的问题,引入_InOrder函数
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root;
};
void TestBSTree1()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> t;
for (auto e : a)
{
t.Insert(e);
}
t.InOrder();
t.Erase(4);
t.InOrder();
t.Erase(6);
t.InOrder();
t.Erase(7);
t.InOrder();
t.Erase(3);
t.InOrder();
for (auto e : a)
{
t.Erase(e);
}
t.InOrder();
}
五.进阶二叉树习题传送门
进阶二叉树习题传送门文章来源地址https://www.toymoban.com/news/detail-755349.html
到了这里,关于【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!