C++数据结构——二叉搜索树（实现自定义迭代器）

太过爱你忘了你带给我的痛 2021-11-22 16:31 239阅读 0赞

**1.二叉搜索树抽象模型和相应的node对象表示  
![20130802173724406][]  
  
  
  
  
2.从二叉搜索树删除一个节点  
（1）如果是叶子节点就直接删除  
（2）被删除的节点有左节点，但没有右节点，则将左节点连接到父节点上，例如删除下图节点35  
![20130802173839265][]  
  
（3）被删除的节点有右节点，但没有左节点，则将右节点连接到父节点上，例如删除下图节点26  
![20130802174048687][]  
  
  
（4）被删除的节点有左右节点，选择该节点右子树最左边的节点来替换，此时分两组情况：  
pNodePtr:dNodePtr的父节点  
dNodeptr:将被删除的节点  
pOfRNodePtr:替代节点的父节点  
rNodePtr: 替代节点  
  
  
\*右节点的左子树为空，则不需要再往左下降，例如删除下图的节点25  
![20130802174156421][]  
  
  
\*右节点的左子树不为空，则沿着左子树下降，直到到达叶子节点，例如删除下图的节点30  
![20130802174339390][]  
  
  
实现代码：**

**node.h**

**myIterator.h  
(由于篇幅的关系，详见[C++数据结构——二叉搜索树迭代器的实现][C]）  
  
  
  
BSTree.h  
  
  
\#ifndef BS\_Tree\_H  
\#define BS\_Tree\_H  
\#include"node.h"  
\#include<iostream>  
\#include<queue>  
using namespace std;  
template<typename T>  
  
  
class bs\_Tree  
\{  
friend class myIterator;  
private:  
node<T> \*root; //二叉搜索树根节点   
  
  
//以后序遍历方式复制二叉搜索树，返回根节点  
node<T> \* copyBSTree(node<T> \*root)  
\{   
node<T> \*p=nullptr; //根节点  
node<T> \*l=nullptr; //左子树  
node<T> \*r=nullptr; //右子树  
  
  
if(!root) //递归结束条件  
\{   
return nullptr;  
\}  
else  
\{   
l=copyBSTree(root->left); //递归复制左子树  
r=copyBSTree(root->right); //递归复制右子树  
p=new node<T>(root->val,nullptr,l,r);  
  
  
if(l)  
\{   
l->parent=p;  
\}  
if(r)  
\{   
r->parent=p;  
\}  
\}  
  
  
return p;  
\}  
  
//以后序遍历方式删除二叉搜索树，  
void deleteBSTree(node<T>\* root)  
\{   
if(!root) //递归结束条件  
\{   
return;  
\}  
else  
\{   
deleteBSTree(root->left);  
deleteBSTree(root->right);  
delete root;  
\}  
\}  
  
public:  
\#include"myIterator.h"  
bs\_Tree():root(nullptr)\{\}  
bs\_Tree(bs\_Tree &rh)  
\{   
root=copyBSTree(rh.root);  
\}  
  
  
bs\_Tree& operator=(bs\_Tree &rh)  
\{   
if(this==&rh) //自身赋值  
\{   
return \*this;  
\}  
  
  
deleteBSTree(root); //释放原来的空间  
root=copyBSTree(rh.root);  
  
  
  
return \*this;  
\}  
  
  
  
~bs\_Tree()  
\{   
deleteBSTree(root);  
root=nullptr;  
\}  
  
  
  
  
  
  
  
  
//返回迭代器-布尔值键对  
//迭代器指向被插入的位置  
//插入成功布尔值为真，否则为假  
pair<myIterator,bool> insert(T v)   
\{   
  
if(!root) //二叉搜索树为空   
\{   
  
root=new node<T>(v);  
return make\_pair(myIterator(root,this),true);  
\}  
else  
\{   
node<T> \*tem=root;  
node<T> \*prt;  
while(tem!=nullptr) //查找合适的插入点   
\{   
prt=tem;  
if(v==tem->val)  
\{   
return make\_pair(myIterator(tem,this),false); //存在相同的值则不插入  
\}  
else if(v<tem->val)  
\{   
tem=tem->left;  
\}  
else  
\{   
tem=tem->right;  
\}  
\}  
  
  
node<T> \*newNode=new node<T>(v,prt);  
  
if(v<prt->val)  
\{   
  
prt->left=newNode; //把新节点作为父节点的左节点  
\}  
else  
\{   
prt->right=newNode; //把新节点作为父节点的右节点  
\}  
  
return make\_pair(myIterator(newNode,this),true);  
\}  
  
  
\}  
  
  
void erase(myIterator &pos)  
\{   
  
node<T> \*dNode=pos.curr; //被删除的节点  
node<T> \*pNode=dNode->parent; //被删除节点的父节点  
node<T> \*rNode=nullptr; //替代节点  
  
  
//被删除节点的左子树和右子树都为空  
if(!dNode->left&&!dNode->right)   
\{   
if(!pNode) //当只有一个根节点时  
\{   
delete dNode;  
root=nullptr; //把根节点赋为空，防止析构函数再次删除  
return;  
\}  
  
if(dNode->val<pNode->val)  
 pNode->left=nullptr;  
else if(dNode->val>pNode->val)  
 pNode->right=nullptr;  
  
delete dNode;  
return;  
\}  
  
  
//被删除节点的左子树或右子树为空  
else if(!dNode->left||!dNode->right)  
\{   
if(!dNode->left) //左子树为空  
rNode=dNode->right;  
 else if (!dNode->right) //右子树为空  
rNode=dNode->left;  
  
  
if(rNode) //被删除节点的左子树或右子树为只有一个为空时  
\{   
rNode->parent=pNode;  
\}  
\}  
else //被删除节点的左子树和右子树非空，选择该节点右子树最左边的节点来替换  
\{   
node<T> \*prNode=dNode; //替代节点的父节点  
  
rNode=dNode->right; //进入被删除节点的右节点  
  
while(rNode->left) //则沿着左子树下降，直到到达叶子节点  
\{   
prNode=rNode; //记录替代节点的父节点  
rNode=rNode->left;  
\}  
  
  
  
if(prNode==dNode)//说明while没有执行，即被删除节点的右节点的左子树为空  
\{   
rNode->parent=pNode; //替换节点的父节点指向被删除节点的父节点  
rNode->left=dNode->left;//替换节点的左节点指向被删除节点的左节点  
dNode->left->parent=rNode; //被删除节点的左子树的父节点指向替换节点  
\}  
else //被删除节点右节点的左子树不为空  
\{   
prNode->left=rNode->right; //替换节点的父节点左子树指向替换节点的右子树  
if(rNode->right) //替换节点不是叶子节点  
 rNode->right->parent=prNode;  
  
rNode->parent=pNode; //替换节点的父节点指向被删除节点的父节点  
rNode->left=dNode->left; //替换节点的左子树指向被删除节点的左子树  
rNode->right=dNode->right; //替换节点的右子树指向被删除节点的右子树  
dNode->left->parent=rNode; //被删除节点的左子树的父节点指向替换节点  
dNode->right->parent=rNode; //被删除节点的左子树的父节点指向替换节点  
\}  
\}  
  
  
if(!pNode) //被删除节点为根节点  
root=rNode; //使替换节点为根节点  
  
//被删除节点非根节点，使替换节点指向被删除节点的父节点的左子树或右子树  
else if(rNode->val<pNode->val)  
 pNode->left=rNode;  
else  
pNode->right=rNode;  
  
  
  
delete dNode; //删除节点  
\}  
  
  
myIterator begin() //返回中序遍历的第一个元素  
\{   
node<T> \*tem=root;  
while(tem->left)  
\{   
tem=tem->left;  
\}  
  
  
return myIterator(tem,this);  
\}  
  
  
myIterator end()  
\{   
return myIterator(nullptr,this);  
\}  
  
  
\};  
  
  
  
  
\#endif  
  
  
  
 测试代码：  
 \#include <iostream>  
\#include"BSTree.h"  
  
  
int main(int argc, char\*\* argv)  
\{  
bs\_Tree<int> bs;  
auto p=bs.insert(10); //测试插入函数及其返回值  
cout<<\*p.first<<ends<<p.second<<endl;  
  
  
bs.insert(33);  
bs.insert(12);  
bs.insert(21);  
  
  
p=bs.insert(10); //测试插入相同值时的返回值  
cout<<\*p.first<<ends<<p.second<<endl<<endl;  
  
cout<<"in bs ："<<endl;  
for(int x:bs)  
\{   
cout<<x<<ends;  
\}  
  
  
cout<<endl<<endl<<"after bs\_Tree<int> bs1(bs), in bs1: "<<endl;  
bs\_Tree<int> bs1(bs); //测试复制构造函数  
for(int x:bs1)  
\{   
cout<<x<<ends;  
\}  
  
  
bs\_Tree<int> bs2;  
bs2=bs1; //测试赋值操作符  
cout<<endl<<endl<<"after bs2=bs1,in bs2: "<<endl;  
for(int x:bs2)  
\{   
cout<<x<<ends;  
\}  
  
cout<<endl<<endl<<"test bs2.erase()"<<endl;  
  
for(auto p1=bs2.begin();p1!=bs2.end();) //测试erase()函数  
\{   
for(int x:bs2)  
 \{   
cout<<x<<ends;  
 \}  
cout<<endl;  
  
bs2.erase(p1++);  
\}  
  
  
  
  
return 0;  
\}**

**运行结果：**

**![Center][]**

[20130802173724406]: /images/20211122/554e973a466a42f6b20ce64ab9262ffb.png
[20130802173839265]: /images/20211122/7502ed5f59974032a4fa2b1112e91b06.png
[20130802174048687]: /images/20211122/4726c5fe99e1484bbbb08806f58caec2.png
[20130802174156421]: /images/20211122/d2331177cf6a4e0a908e14d0a3f27a52.png
[20130802174339390]: /images/20211122/b00124453ad74ef5ba42004cbc922012.png
[C]: http://blog.csdn.net/piniheaven/article/details/9719393
[Center]: /images/20211122/487c1f07581a4a85ab403dcce8082637.png