长春网站制作专业,长沙医院网站建设,四川长昕建设工程有限公司网站,陕西营销型网站建设#x1f466;个人主页#xff1a;Weraphael ✍#x1f3fb;作者简介#xff1a;目前学习C和算法 ✈️专栏#xff1a;C航路 #x1f40b; 希望大家多多支持#xff0c;咱一起进步#xff01;#x1f601; 如果文章对你有帮助的话 欢迎 评论#x1f4ac; 点赞#x1… 个人主页Weraphael ✍作者简介目前学习C和算法 ✈️专栏C航路 希望大家多多支持咱一起进步 如果文章对你有帮助的话 欢迎 评论 点赞 收藏 加关注✨ 目录 一、什么是二叉搜索树二、二叉搜索树的实现(迭代版)2.1 定义二叉树的结点2.2 插入操作2.3 查找操作3.4 删除操作3.5 二叉搜索树的遍历3.5.1 中序遍历重点3.5.2 前序遍历3.5.3 后序遍历 四、二叉搜索树的实现 (递归版)4.1 查找操作4.2 插入操作4.3 删除操作 五、代码补充5.1 释放结点5.2 拷贝构造5.3 赋值运算符重载 六、性能分析七、完整代码7.1 非递归 7.2 递归 一、什么是二叉搜索树
二叉搜索树Binary Search Tree是基于二叉树的一种改进版本。因为普通二叉树没有实际价值无法进行插入、删除等操作但二叉搜索树就不一样了。
二叉搜索树又称二叉排序树它或者是一棵空树。如果不为空则满足一下性质:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也要分别为二叉搜索树
总之左节点比根小右节点比根大。因此二叉搜索树的查找效率极高具有一定的实际价值。
下图展示了二叉搜索树 搜索二叉树还有一个非常重要的特性中序遍历左子树 根 右子树的结果为升序。
二、二叉搜索树的实现(迭代版)
2.1 定义二叉树的结点
一般来说二叉树使用链表来定义不同的是由于二叉树每个结点都存在两条出边因此指针域变为两个分别指向左子树和右子树的根结点地址因此又把这种链表叫做二叉链表。
templateclass K
struct BSTreeNode // 结点
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;// 默认构造BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};2.2 插入操作
当插入一个值时必须先找到满足二叉搜索性质的位置如果当前位置不为空或者插入的值和已有的值重复则插入失败。如果找到满足条件的位置并且为空则结束循环进行插入。步骤创建新节点、判断需要插在左边还是右边、链接新节点
templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:BSTree():_root(nullptr){}// 插入操作bool Insert(const K key){// 一开始树为空直接插入if (_root nullptr){_root new Node(key);return true;}// cur用来查找合适的位置Node* cur _root;// parent用来找cur的父亲结点Node* parent nullptr;while (cur){// 插入的结点大于当前结点// 往右走if (cur-_key key){parent cur;cur cur-_right;}// 插入的结点小于当前结点// 往左走else if (cur-_key key){parent cur;cur cur-_left;}// 最后一种情况就是出现冗余// 直接返回else{return false;}}// 当循环来到此处说明已经找到合适的位置了// 直接开始插入操作// 1. 创建新的结点cur new Node(key);// 2. 判断是插在父亲的左边还是右边if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}
private:Node* _root;
};【插入成功】 【插入失败】 2.3 查找操作
从根结点开始比较比根大的则往右查找比根小的往左查找。走到空还没找到说明值不存在。否则就是存在
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;}【查找成功】 【查找失败】 3.4 删除操作
二叉搜索树的删除是个麻烦事需要考虑很多情况因此大多数面试都会考察搜索二叉树的删除操作
删除逻辑
首先查找元素是否在二叉搜索树中如果不存在则直接返回否在要删除的结点就要分以下四种情况
1、 要删除的结点只有左孩子
只需要将被删除结点的左子树与父节点进行链接即可。前提是要判断删除的结点是父结点的左还是右。 2、 要删除的结点只有右孩子
同理左子树为空时将其右子树与父节点进行判断链接链接完成后删除目标节点
3、要删除的结点有两个孩子
当左右都不为空时就有点麻烦了需要找到一个合适的值即左子树所有节点的值又右子树所有节点的值确保符合二叉搜索树的基本特点
符合条件的值有左子树的最右节点左子树中最大的或者右子树的最左节点右子树中最小的将这两个值中的任意一个覆盖待删除节点的值都能确保符合要求
以左子树的最右节点左子树中最大的为例 4、要删除的结点没有孩子
这种情况可以包含在1或者2中
下面是代码实现详细的代码解释
bool Erase(const K key)
{// parent - 用来记录删除结点的父亲Node* parent nullptr;// cur - 记录被删除的结点Node* cur _root;// 查找key(被删除的结点)while (cur){// 如果key比当前元素要大// 就往右找if (cur-_key key){parent cur;cur cur-_right;}// key比当前元素要小// 就往左找else if (cur-_key key){parent cur;cur cur-_left;}// 最后一种情况就是找到了// 对于找到要分情况讨论 else {// 1. 如果删除的结点的左孩子为空// 右孩子可能为空包含删除叶子结点的情况// 也可能不为空if (cur-_left nullptr){// 可能删除的结点是根结点// 也就是以下这种情况// 1 -- root cur// 2// 3// 没有考虑这个问题会引发parent野指针问题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;}}} // 左右都不为空 // 左右子树都不为空的场景中// parent 要初始化为cur避免后面的野指针问题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;
}3.5 二叉搜索树的遍历
二叉搜索树的遍历操作和二叉树一模一样的因此可以有前序遍历、中序遍历以及后序遍历。
3.5.1 中序遍历重点
搜索二叉树的 中序遍历左子树 根 右子树的结果为升序。
void InOrder(Node* root)
{if (root NULL){return;}InOrder(root-_left);cout root-_key ;InOrder(root-_right);
}但因为这里是一个被封装的类所以面临着一个尴尬的问题二叉搜索树的根root是私有外部无法直接获取
解决办法
公有化破坏类的封装性不推荐使用静态成员函数可以直接被类外使用。也是ok但是不推荐将这种需要用到根的函数再封装。推荐
public:
void InOrder()
{_InOrder(root);
}
private:
void _InOrder(Node* root)
{if (root NULL){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);
}实际调用时只能调到InOrder因为真正的函数_InOrder为是私有除了类之外其他地方不可访问。
3.5.2 前序遍历
public:
void PreOrder()
{_PreOrder(_root);
}private:void _PreOrder(Node* root){if (root nullptr){return;}cout root-_key ;_PreOrder(root-_left);_PreOrder(root-_right);}3.5.3 后序遍历
public:
void PostOrder()
{_PostOrder(_root);
}
private:void _PostOrder(Node* root)
{if (root nullptr){return;}_PostOrder(root-_left);_PostOrder(root-_right);cout root-_key ;
}四、二叉搜索树的实现 (递归版)
4.1 查找操作
递归查找逻辑
如果当前根的值查找值递归至右树查找如果当前根的值查找值递归至左树查找
二叉树的递归常常是通过将问题分解为更小规模的子问题来解决的。通过传递根节点作为参数我们可以在每次递归中处理当前节点并将问题分解为处理左子树和右子树的子问题。因此还需要对函数进行封装。
public:
bool Find(const K key)
{return _Find(_root, key);
}
private:
bool _Find(Node* root, const k key)
{// 如果根为空说明查找失败递归出口if (root nullptr)return false;// 查找的值比当前结点大往右找if (root-_key key){return _Find(root-_right);}// 查找的值比当前结点小往左找else if (root-_key key){return _Find(root-_left);}// 最后一种情况就是找到了elsereturn true;
}4.2 插入操作
这里和其它不同的是在传参的时候使用了引用。传引用是为了在递归查找过程中能够修改目标节点的指针值。搜索二叉树的递归查找算法通常会通过比较当前节点的值与目标值来决定向左子树还是右子树继续查找。如果不传引用每次递归调用时都会创建一个新的节点指针副本这样就无法修改原始节点的指针值从而导致无法正确返回目标节点的指针。
这么说有点抽象可以先看代码理解过会画完递归展开图大家就能够理解了。
public:
bool Insert(const K key)
{return _Insert(_root, key);
}private:
bool _Insert(Node* root, const K key)
{// 当走到空说明找到了合适的位置if (root nullptr){// 还得找到父亲为什么加个引用就搞定了root new Node(key);return true;}// 插入的值比当前结点大往右找if (root-_key key){return _Insert(root-_right);}// 插入的值比当前结点小往左找else if (root-_key key){return _Insert(root-_left);}// 当插入的值和树发生冗余直接返回falseelse{return false;}
}【递归展开图】 4.3 删除操作
递归删除时也使用了引用其想法和插入一样不需要找删除结点的父亲直接修改目标节点的指针值
public:
bool Earse(const K key)
{return _Erase(root, key);
}private:
bool _Erase(Node* root, const K key)
{// 如果是空结点说明删除失败if (root nullptr)return false;if (root-_key key){return _Erase(root-_right, key);}else if (root-_key key){return _Erase(root-_left, key);}// 找到keyelse{Node* del root;// 还是分三种情况// 1. 删除结点的左孩子为空if (root-_left nullptr){root root-_right;}// 2. 删除结点的右孩子为空else if (root-_right nullptr){root root-_left;}// 3. 删除结点孩子都不为空else{//递归为小问题去处理Node* maxLeft root-_left;while (maxLeft-_right){maxLeft maxLeft-_right;}//注意需要交换std::swap(root-_key, maxLeft-_key);//注意当前找的是左子树的最右节点所以递归从左子树开始return _Erase(root-_left, key);}delete del; //释放节点return true;}
} 五、代码补充
5.1 释放结点
创建节点时使用了new申请堆空间根据动态内存管理原则就需要使用delete释放申请的堆空间但二叉搜索树是一棵树不能直接释放需要递归式的遍历每一个节点
释放思路后序遍历思想
public:
~BSTree()
{_destory(_root);
}private:
void _destory(Node* root)
{if (root nullptr)return;//后序遍历销毁destory(root-_left);destory(root-_right);delete root;root nullptr;
}5.2 拷贝构造
销毁问题考虑完以后就要想是否会有浅拷贝问题因为浅拷贝问题会导致一个结点析构两次程序就崩了。而我们在类和对象中说过如果类中有动态分配内存的指针变量则需要手动编写深拷贝的拷贝构造函数。
public:
BSTree(BSTreeK tree):_root(nullptr)
{_root _Copy(tree._root);
}private:
Node* _Copy(Node* root)
{//递归拷贝if (root nullptr)return nullptr;Node* new_root new Node(root-_key); new_root-_left _Copy(root-_left);new_root-_right _Copy(root-_right);return new_root;
}5.3 赋值运算符重载
如果没有显式实现时编译器会生成一个默认赋值运算符重载以值的方式逐字节拷贝浅拷贝。其默认成员函数和拷贝构造的默认函数类似内置类型成员变量是直接赋值的而自定义类型成员会去调用它的默认函数。因此赋值运算符也需要自己实现深拷贝
直接写现代写法
BSTreeK operator(BSTreeK tree)
{std::swap(_root, tree._root);return *this;
}六、性能分析
从名字上来看二叉树的特性就是查找快。
搜索二叉树的时间复杂度取决于树的高度。因此当是一颗平衡二叉搜索树时时间复杂度是O(log n)。因为每次搜索都可以通过比较目标值与当前节点的值来确定向左子树还是右子树进行搜索这样每次都可以将搜索范围减半。 是不是有点类似于二分查找但二分查找不是一个很实用的算法。因为对比二叉搜索树来说二分查找底层是一个数组的删除和插入的效率低0(n)(特别是中间插入和删除) 二叉搜索树看起来这么完美但下限没有保障。在最坏的情况下当搜索二叉树是一个不平衡的树时时间复杂度为O(n)其中n是树中节点的数量。这是因为在最坏情况下每次搜索都要遍历树的所有节点。 因此为了解决这个问题引入了AVL树和红黑树后续会讲解
七、完整代码
7.1 非递归
#pragma once// 迭代版本
templateclass K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:BSTree():_root(nullptr){}bool Insert(const K key){// 如果一开始树为空直接插入if (_root nullptr){// 对自定义类型的new会自动调用其默认构造函数_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 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 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;}void InOrder(){_InOrder(_root);}void PreOrder(){_PreOrder(_root);}void PostOrder(){_PostOrder(_root);}private:void _PostOrder(Node* root){if (root nullptr){return;}_PostOrder(root-_left);_PostOrder(root-_right);cout root-_key ;}void _PreOrder(Node* root){if (root nullptr){return;}cout root-_key ;_PreOrder(root-_left);_PreOrder(root-_right);}void _InOrder(Node* root){if (root NULL){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root;
};7.2 递归
#pragma once
templateclass K
struct BSTNode
{BSTNodeK _left;BSTNodeK _right;K _key;BSTNode(const K key):_left(nullptr), _right(nullptr), key(key){}
};templateclass K
class BSTree
{typedef BSTNodeK Node;
public:BSTree():_root(nullptr){}~BSTree(){_destory(_root);}bool Find(const K key){return _Find(_root, key);}bool Insert(const K key){return _Insert(_root, key);}bool Earse(const K key){return _Erase(root, key);}BSTree(BSTreeK tree):_root(nullptr){_root _Copy(tree._root);}BSTreeK operator(BSTreeK tree){std::swap(_root, tree._root);return *this;}
private:Node* _Copy(Node* root){//递归拷贝if (root nullptr)return nullptr;Node* new_root new Node(root-_key); new_root-_left _Copy(root-_left);new_root-_right _Copy(root-_right);return new_root;}void _destory(Node* root){if (root nullptr)return;//后序遍历销毁destory(root-_left);destory(root-_right);delete root;root nullptr;}bool _Find(Node* root, const k key){if (root nullptr)return false;// 查找的值比当前结点大往右找if (root-_key key){return _Find(root-_right);}// 查找的值比当前结点小往左找else if (root-_key key){return _Find(root-_left);}// 最后一种情况就是找到了elsereturn true;}bool _Insert(Node* root, const K key){// 当走到空说明找到了合适的位置if (root nullptr){// 还得找到父亲为什么加个引用就搞定了root new Node(key);return true;}// 插入的值比当前结点大往右找if (root-_key key){return _Insert(root-_right);}// 插入的值比当前结点小往左找else if (root-_key key){return _Insert(root-_left);}// 当插入的值和树发生冗余直接返回falseelse{return false;}}bool _Erase(Node* root, const K key){if (root nullptr)return false;if (root-_key key){return _Erase(root-_right, key);}else if (root-_key key){return _Erase(root-_left, key);}else{Node* del root;// 还是分三种情况// 1. 删除结点的左孩子为空if (root-_left nullptr){root root-_right;}// 2. 删除结点的右孩子为空else if (root-_right nullptr){root root-_left;}// 3. 删除结点孩子都不为空else{//递归为小问题去处理Node* maxLeft root-_left;while (maxLeft-_right){maxLeft maxLeft-_right;}//注意需要交换std::swap(root-_key, maxLeft-_key);//注意当前找的是左子树的最右节点所以递归从左子树开始return _Erase(root-_left, key);}delete del; //释放节点return true;}}private:Node* _root;
};
