哈希表和平衡二叉树数据结构C语言

#include<iostream> #include<string> using namespace std; //二叉树的节点结构 struct AvlTreeNode { int Data;//数据 int Bf;//节点平衡因子 AvlTreeNode *LChild,*RChild;//左右孩子 }; class AvlTree { public: int InitTree();//初始化数据 int CreateTree();//由用户键入创建二叉树 int DestroyTree();//销毁二叉树，空间的释放 int ShowTree();//以字符形式显示平衡二叉树 int InsertNode(int data);//插入节点，它的数据域是data，并做平衡处理，失败返回0，成功返回1 int DeleteNode(int data);//删除节点，它的数据域是data，并做平衡处理，失败返回0，成功返回1 AvlTreeNode* SearchNode(int data);//查找节点，它的数据域是data，查找成功返回指向该节点的指针，否则返回空指针 private: int TreeDelete(AvlTreeNode* &t);//递归删除全部节点，从叶子节点开始 int TreeShow(AvlTreeNode* t,int layer);//递归先序输出全部节点，layer初始为0 AvlTreeNode* TreeSearch(AvlTreeNode* t,int data);//递归寻找树t中数据域为data的节点，成功返回指向该节点的指针，否则返回空指针 int NodeInsert(AvlTreeNode* &t,int data,bool &taller);//递归定位后data插入相应位置，并做平衡处理 int NodeDelete(AvlTreeNode* &t,int data,bool &lower);//递归定位后在相应位置删除data，并做平衡处理 int BalanceDelete(AvlTreeNode* &t,bool &lower);//删除节点t，并做平衡处理 void MaxDelete(AvlTreeNode* &t,int &max,bool &lower);//删除t树中最大数节点，并返回最大数，平衡处理t树 int RightBalance(AvlTreeNode* &t);//右增高失衡平衡处理函数,平衡处理后树层数增长返回1，下降返回-1，不变返回0 int LeftBalance(AvlTreeNode* &t);//左增高失衡平衡处理函数,平衡处理后树层数增长返回1，下降返回-1，不变返回0 int R_Rotate(AvlTreeNode* &t);//右旋函数 int L_Rotate(AvlTreeNode* &t);//左旋函数 private: AvlTreeNode* T;//二叉树的头指针 }; //二叉树头指针致空 int AvlTree::InitTree() { T=NULL; return 0; } //释放空间 int AvlTree::DestroyTree() { //递归删除全部的节点 TreeDelete(T); return 0; } int AvlTree::TreeDelete(AvlTreeNode* &t) { if(!t) return 0; if(t->LChild) TreeDelete(t->LChild); if(t->RChild) TreeDelete(t->RChild); //t若是叶子节点直接删除 if(!t->LChild&&!t->RChild) { delete t; t=NULL; return 0; } } int AvlTree::ShowTree() { if(!T) return 0; //递归显示各个节点的 TreeShow(T,0); return 1; } int AvlTree::TreeShow(AvlTreeNode* t,int layer) { //输出空格以标记层次 for(int i=0;i<layer;i++) cout<<" "; //输出当前的节点 if(t) cout<<"数据:"<<t->Data<<" 平衡因子:"<<t->Bf<<endl; //输出左孩子 if(t->LChild) TreeShow(t->LChild,1+layer); if(t->RChild) TreeShow(t->RChild,1+layer); return 0; } AvlTreeNode* AvlTree::SearchNode(int data) { //递归寻找数据域是data的节点 return TreeSearch(T,data); } AvlTreeNode* AvlTree::TreeSearch(AvlTreeNode* t,int data) { //若树t为空或该节点的数据等于data返回当前节点 if((!t)||t->Data==data) return t; //若当前节点数据小于data，在右孩子中再搜索 if(t->Data<data) return TreeSearch(t->RChild,data); //若当前节点数据大于data，在左孩子中再搜索 if(t->Data>data) return TreeSearch(t->LChild,data); } //有用户的键盘输入创建二叉树 int AvlTree::CreateTree() { //输入数据的个数 int n; cout<<"请先输入您要输入的数据的个数:"; cin>>n; int data;//输入数据临时变量 //依次插入数据，并做平衡处理 cout<<"请依次输入您的数据(用空格隔开):"<<endl; for(int i=0;i<n;i++) { cin>>data; InsertNode(data); } return n; } //插入数据data，并做平衡处理 int AvlTree::InsertNode(int data) { bool taller=false; //递归定位后插入相应的位置 if(NodeInsert(T,data,taller)) return 1; return 0; } //递归定位后data插入树t相应的位置，并做平衡处理，taller表示树层数是否增长，初始为false int AvlTree::NodeInsert(AvlTreeNode* &t,int data,bool &taller) { //当期位置是空，插入新节点，数据域是data if(!t) { t=new AvlTreeNode; t->Data=data; t->Bf=0;//左右孩子都为空 t->LChild=t->RChild=NULL; taller=true;//对于当前树t层数增长 return 1; } //当前节点数据域等于data，插入失败 if(t->Data==data) return 0; //若data大于当前节点数据，在右孩子中再定位插入，并在失衡后做平衡处理 if(data>t->Data) { //若插入成功，判断是否失衡，失衡后做平衡处理 if(NodeInsert(t->RChild,data,taller)) { //若层数增长，更新当前节点平衡因子bf以及taller，判断是否失衡 if(taller) { switch(t->Bf) { case 1: t->Bf=0; taller=false; break; case 0: t->Bf=-1; taller=true; break; case -1://失衡，做平衡处理 RightBalance(t);//平衡处理后树层数增长返回1，下降返回-1，不变返回0 taller=false; break; } } return 1; } } //若data小于当前节点数据，在左孩子中再定位插入，并在失衡后做平衡处理 if(data<t->Data) { //若插入成功，判断是否失衡，失衡后做平衡处理 if(NodeInsert(t->LChild,data,taller)) { //若层数增长，更新当前节点平衡因子bf以及taller，判断是否失衡 if(taller) { switch(t->Bf) { case -1: t->Bf=0; taller=false; break; case 0: t->Bf=1; taller=true; break; case 1://失衡，做平衡处理 LeftBalance(t);//平衡处理后树层数增长返回1，下降返回-1，不变返回0 taller=false; break; } } return 1; } } } //右孩子增高失衡平衡处理 int AvlTree::RightBalance(AvlTreeNode* &t) { AvlTreeNode* p;//判断失衡情况的辅助变量 p=t->RChild; //对失衡不同情况做出不同处理 switch(p->Bf) { case -1: t->Bf=p->Bf=0; L_Rotate(t);//一次左旋 return -1; case 0: t->Bf=-1; p->Bf=1; L_Rotate(t); return 0; case 1: AvlTreeNode* q=p->LChild;//判断失衡情况的辅助变量 switch(q->Bf) { case 0: t->Bf=p->Bf=0; break; case 1: t->Bf=0; p->Bf=-1; break; case -1: t->Bf=1; p->Bf=0; break; } q->Bf=0; R_Rotate(t->RChild); L_Rotate(t); return -1; } } //左孩子增高失衡平衡处理 int AvlTree::LeftBalance(AvlTreeNode* &t) { AvlTreeNode* p;//判断失衡情况的辅助变量 p=t->LChild; //对失衡不同情况做出不同处理 switch(p->Bf) { case 1: t->Bf=p->Bf=0; R_Rotate(t);//一次左旋 return -1; case 0: t->Bf=-1; p->Bf=1; L_Rotate(t); return 0; case -1: AvlTreeNode* q=p->RChild;//判断失衡情况的辅助变量 switch(q->Bf) { case 0: t->Bf=p->Bf=0; break; case -1: t->Bf=0; p->Bf=-1; break; case 1: t->Bf=1; p->Bf=0; break; } q->Bf=0; L_Rotate(t->RChild); R_Rotate(t); return -1; } } //右旋函数 int AvlTree::R_Rotate(AvlTreeNode* &t) { AvlTreeNode* p=t->LChild;//辅助变量，避免一些节点丢失 t->LChild=p->RChild; p->RChild=t; t=p; return 0; } //左旋函数 int AvlTree::L_Rotate(AvlTreeNode* &t) { AvlTreeNode *p=t->RChild;//辅助变量，避免一些节点丢失 t->RChild=p->LChild; p->LChild=t; t=p; return 0; } //删除数据域是data的节点，并做平衡处理 int AvlTree::DeleteNode(int data) { bool lower=false; //递归定位删除相应的节点，若没有该数据的节点删除失败 if(NodeDelete(T,data,lower)) return 1; return 0; } //递归定位后在树t相应位置删除数据data，并做平衡处理，lower表示树层数是否下降，初始为false int AvlTree::NodeDelete(AvlTreeNode* &t,int data,bool &lower) { //若没有数据域等于data的节点，返回0 if(!t) { lower=false;//删除失败，层数无变化 return 0; } //若当前节点数据等于data，删除当前节点并做平衡处理 if(t->Data==data) return BalanceDelete(t,lower); //若data小于当前节点数据域，再在左孩子中删除 if(data<t->Data) { if(NodeDelete(t->LChild,data,lower)) { if(lower) { switch(t->Bf) { case 1: t->Bf=0; lower=true; break; case 0: t->Bf=-1; lower=false; break; case -1: if(RightBalance(t)==0) lower=false; else lower=true; break; } } return 1; } return 0; } //若data大于当前节点数据域，再在右孩子中删除 if(data>t->Data) { if(NodeDelete(t->RChild,