Erase( ) 删除函数 🦕
删除函数在搜索二叉树中是一个比较复杂的函数;
复杂的问题在于:
- 该如何删除节点;
- 删除节点后如何对剩余节点进行链接;
同时从一张图的分析中可以分析出搜索二叉树删除节点的几种情况:
- 删除的节点不存在子树;
当所删除的节点不存在左右子树时直接将节点进行删除即可;
- 删除的节点左子树为空或者右子树为空;
当所删除的节点的左子树或者右子树为空时,可采用托孤的方式对节点进行链接;
即所删除节点的父节点与所删除的子节点进行链接;
- 删除的节点左右子树都不为空;
当所删除的节点其左右子树都不为空时,由于每个节点只能管理两个子树(左右子树),而所删除的节点存在左右两棵子树,故不能采用托孤的方式对所删除的节点的子树进行管理;
在这种情况下即可采用伪删除法的方式对节点进行伪删除;
伪删除即为选择一个符合接管该节点的左右子树规则的节点,将其值赋值给当前节点,并将选择的节点进行删除 (符合该种条件的节点一般为该节点左子树的最大值或该节点右子树的最小值);
以该图为例若是删除节点8,则可以使用节点7进行代替接管其左右子树,并将原节点7进行删除从而达到伪删除的目的;
实现:
bool Erase(const K& key){ if(nullptr == _proot) return false; //找到这个key值 Node* pcur = _proot; Node* parent = _proot; while(pcur){ //进行遍历找到对应的key值 if(key>pcur->_key){ parent = pcur; pcur = pcur->_pright; } else if(key<pcur->_key){ parent = pcur; pcur = pcur->_pleft; } else{ //已经找到了对应的key值,需要进行删除 //左为空的情况 if(pcur->_pleft == nullptr){ //判断极端情况(左为空或者右为空的情况下所删节点为根) if(pcur == _proot){ _proot = pcur->_pright; delete pcur; return true; } if(parent->_pleft == pcur){ parent->_pleft = pcur->_pright; } else{ parent->_pright = pcur->_pright; } delete pcur; return true; } //右为空的情况 else if(pcur->_pright == nullptr){ //判断极端情况(左为空或者右为空的情况下所删节点为根) if(pcur == _proot){ _proot = pcur->_pleft; delete pcur; return true; } if(parent->_pleft == pcur){ parent->_pleft = pcur->_pleft; } else { parent->_pright = pcur->_pleft; } delete pcur; return true; } //左右都不为空 else{ /* * 找到左子树的最右子树或右子树的最左子树 */ Node*tmp = pcur->_pright; //右子树的最左子树(最小值) Node*tmp_parent = pcur; while(tmp->_pleft){ tmp_parent = tmp; tmp = tmp->_pleft; } /* * 找到符合条件的值,进行伪删除法; */ pcur->_key = tmp->_key; //说明该子树存在孩子,需要对该子树进行托孤 //由于所找的数据为该节点右子树的最小值,说明找到的这个最小值不存在左子树,只需要对右子树进行托孤; if(tmp_parent->_pleft == tmp){ tmp_parent->_pleft = tmp->_pright; delete tmp; } else{ tmp_parent->_pright = tmp->_pright; delete tmp; } return true; } } } //未找到key值,pcur指针已经为空,返回false; return false; }
👾 Erase( ) 函数(递归)
对于Erase()函数的递归方式与其非递归的方式都有异曲同工之处;
唯一不同的是为了节点链接的方便在用于递归的子函数当中使用指针引用的方式完成节点的链接;
bool EraseR(const K&key){//主函数 return _EraseR(key,_proot); } //---------------------------------- bool _EraseR(const K& key, Node*& root){//子函数 if(root == nullptr) return false; if(key>root->_key) return _EraseR(key,root->_pright); else if(key<root->_key) return _EraseR(key,root->_pleft); else{ Node *cur = root; //左为空 if(root->_pleft == nullptr){ root = root->_pright; delete cur; return true; } //右为空 else if(root->_pright == nullptr){ root = root->_pleft; delete cur; return true; } //左右都不为空 else{ cur = root->_pleft; while(cur->_pright) cur = cur->_pright; root->_key = cur->_key; _EraseR(cur->_key,root->_pleft); return true; } } }
默认成员函数 🦕
👾 构造函数
搜索二叉树的构造函数即对节点进行初始化即可,在不存在其他的构造函数的情况下可以使用默认生成的构造函数,因为由于在定义成员变量时给定了成员变量了缺省参数_proot = nullptr;
若是存在其他构造函数 (拷贝构造函数也为构造函数的一种) 时则需要手写这个构造函数;
或是使用default关键字:
BinarySearchTree() = default;
👾 拷贝构造函数
拷贝构造函数则可以使用递归的方式逐个对节点进行拷贝从而达到深拷贝的效果;
BinarySearchTree(const BinarySearchTree<K> &node){//主函数 _proot = _CopyNode(node._proot); } //---------------------------------- Node* _CopyNode(const Node* node){//子函数 if(node == nullptr) { return nullptr; } Node*newnode = new Node(node->_key); newnode->_pleft = _CopyNode(node->_pleft); newnode->_pright = _CopyNode(node->_pright); return newnode; }
👾 赋值运算符重载
赋值运算符重载一般采用现代的写法:
即为利用自定义类型在进行传值传参时会进行拷贝构造的特性完成对该自定义类型的拷贝,再进行交换与返回;
BinarySearchTree<K>& operator=( BinarySearchTree<K> node){//在传值传参过程中调用拷贝构造生成了临时拷贝(深拷贝) swap(_proot,node._proot); return *this; }
👾 析构函数
析构函数采用父子函数的方式,利用子函数作递归,主函数调用该子函数即可;
void _Destroy(Node*& root){ if(root == nullptr) return; _Destroy(root->_pleft); _Destroy(root->_pright); delete root; root = nullptr; } //---------------------------------- ~BinarySearchTree(){ _Destroy(_proot); }
总代码 🦕
#pragma once #include<iostream> using namespace std; template<class K> struct BSTNode{ BSTNode(const K& key = K()) :_pleft(nullptr), _pright(nullptr), _key(key) {} BSTNode<K> *_pleft; BSTNode<K> *_pright; K _key; }; template<class K> class BinarySearchTree{ typedef BSTNode<K> Node; public: /* * 默认成员函数 */ //-------------------------------- //构造函数 BinarySearchTree()=default; /*强制生成默认构造函数*/ //-------------------------------- //拷贝构造 BinarySearchTree(const BinarySearchTree<K> &node){ _proot = _CopyNode(node._proot); } //-------------------------------- //赋值重载操作符 BinarySearchTree<K>& operator=( BinarySearchTree<K> node){ swap(_proot,node._proot); return *this; } //-------------------------------- //析构函数 - 使用递归方法 后序遍历进行Destory ~BinarySearchTree(){ _Destroy(_proot); } //-------------------------------- bool Insert(const K& key){ if(_proot == nullptr){//如果root节点为空说明为空树，空树进行第一次插入 _proot = new Node(key); return true;//插入成功进行返回 } Node* cur = _proot; Node* tmp; while(cur!=nullptr){ tmp = cur; if(key>cur->_key){ tmp = cur; cur = cur->_pright; } else if(key<cur->_key){ tmp = cur; cur = cur->_pleft; } else{ //相同 返回false return false; } } if(key>tmp->_key){//链接在右边 cur = new Node(key); tmp->_pright = cur; } else{//链接在左边 cur = new Node(key); tmp->_pleft = cur; } return true; } //----------------------- void InOrder(){ /* * 自定义类型成员函数若是需要进行递归时 * 尽量设置一个子函数来方便递归并使用原成员函数进行调用 * * 在该自定义类型当中，由于传的参数为private私有成员变量 * 私有成员变量不方便直接进行传参，所以为了方便传参_proot * 在private访问限定符的域当中设置一个子函数用来递归 * 通过原函数去调用这个私有成员函数 */ _InOrder(_proot); cout<<endl; } //----------------------- bool Find(const K& key){ Node*pcur = _proot; while(pcur){ if(key>pcur->_key) pcur = pcur->_pright; else if(key<pcur->_key) pcur = pcur->_pleft; else return true; } return false; } //----------------------- bool Erase(const K& key){ if(nullptr == _proot) return false; //找到这个key值 Node* pcur = _proot; Node* parent = _proot; while(pcur){ //进行遍历找到对应的key值 if(key>pcur->_key){ parent = pcur; pcur = pcur->_pright; } else if(key<pcur->_key){ parent = pcur; pcur = pcur->_pleft; } else{ //已经找到了对应的key值,需要进行删除 //左为空的情况 if(pcur->_pleft == nullptr){ if(pcur == _proot){ _proot = pcur->_pright; delete pcur; return true; } if(parent->_pleft == pcur){ parent->_pleft = pcur->_pright; } else{ parent->_pright = pcur->_pright; } delete pcur; return true; } //右为空的情况 else if(pcur->_pright == nullptr){ //判断极端情况(左为空或者右为空的情况下所删节点为根) if(pcur == _proot){ _proot = pcur->_pleft; delete pcur; return true; } if(parent->_pleft == pcur){ parent->_pleft = pcur->_pleft; } else { parent->_pright = pcur->_pleft; } delete pcur; return true; } //左右都不为空 else{ /* * 找到左子树的最右子树或右子树的最左子树 */ Node*tmp = pcur->_pright; //右子树的最左子树(最小值) Node*tmp_parent = pcur; while(tmp->_pleft){ tmp_parent = tmp; tmp = tmp->_pleft; } /* * 找到符合条件的值,进行伪删除法; */ pcur->_key = tmp->_key; //说明该子树存在孩子,需要对该子树进行托孤 //由于所找的数据为该节点右子树的最小值,说明找到的这个最小值不存在左子树,只需要对右子树进行托孤; if(tmp_parent->_pleft == tmp){ tmp_parent->_pleft = tmp->_pright; delete tmp; } else{ tmp_parent->_pright = tmp->_pright; delete tmp; } return true; } } } //未找到key值,pcur指针已经为空,返回false; return false; } //----------------------- bool FindR(const K& key){ return _FindR(key,_proot); } //----------------------- bool InsertR(const K&key){ return _InsertR(key,_proot); } //----------------------- bool EraseR(const K&key){ return _EraseR(key,_proot); } //----------------------- private: /* * 私有成员包括成员函数以及成员变量 */ Node *_proot = nullptr; //----------------------- protected: void _InOrder(Node *root){ if(root == nullptr){ return; } _InOrder(root->_pleft); cout<<root->_key<<" "; _InOrder(root->_pright); } //----------------------- bool _FindR(const K&key,Node*root){ if(root == nullptr) return false; if(root->_key == key) return true; if(root->_key>key) return _FindR(key,root->_pleft); else return _FindR(key,root->_pright); } //----------------------- bool _InsertR(const K&key,Node*& root){ //纯高效法 /* * 该方法重点在于使用了一个引用来引用指针, * 指针既可以为判断条件(为nullptr), * 也不缺乏其为上一个节点的左\右子树; * */ if(root == nullptr) { root = new Node(key); return true; } if(root->_key < key){ return _InsertR(key,root->_pright); } else if(root->_key>key){ return _InsertR(key,root->_pleft); } else return false; } //----------------------- bool _EraseR(const K& key, Node*& root){ if(root == nullptr) return false; if(key>root->_key) return _EraseR(key,root->_pright); else if(key<root->_key) return _EraseR(key,root->_pleft); else{ /* * 在该递归删除中同样利用到了指针引用的方式 // 具体能够指针引用是因为递归每次都会开辟出新的栈帧 * 解决了大部分的判断问题(具体表现在左为空或右为空) * 在判断两个子树都不为空的条件下,具体的思路是利用了循环找到可以进行伪删除法的数,再重新调用该子函数完成删除 * 其想法可以理解为将问题划分为子问题 * (将左右均不为空的方式在进行一系列操作后将其最终以左为空或者右为空的问题进行解决); * */ Node *cur = root; //左为空 if(root->_pleft == nullptr){ root = root->_pright; delete cur; return true; } //右为空 else if(root->_pright == nullptr){ root = root->_pleft; delete cur; return true; } //左右都不为空 else{ cur = root->_pleft; while(cur->_pright) cur = cur->_pright; root->_key = cur->_key; _EraseR(cur->_key,root->_pleft); return true; } } } //----------------------- Node* _CopyNode(const Node* node){ if(node == nullptr) { return nullptr; } Node*newnode = new Node(node->_key); newnode->_pleft = _CopyNode(node->_pleft); newnode->_pright = _CopyNode(node->_pright); return newnode; } //------------------------ void _Destroy(Node*& root){ if(root == nullptr) return; _Destroy(root->_pleft); _Destroy(root->_pright); delete root; root = nullptr; } };
