avl.rar_avl_平衡树

#include<iostream> #include<fstream> #include<string> using namespace std; const int max=10; struct Tele { string name; //姓名 string phoneNumber; //固定电话号码 string mobileNumber; //移动电话号码 string email; //电子邮箱 } Tel[max]; int taller=0; //taller反映T长高与否 int shorter=0; //shorter反映T变矮与否 //********************************************************************** //在屏幕打印菜单函数 int PrintMenu() { int userChose; cout << "**************************************" << endl; cout << " 1. 查找电话号码" << endl; cout << " 2. 插入电话号码" << endl; cout << " 3. 删除电话号码" << endl; cout << " 4. 修改信息" << endl; cout << " 5. 退出程序" << endl; cout << "***************************************" << endl; cout << "请选择你的操作:"; cin >> userChose; return userChose; } //******************************************************* class AVLTree { public: struct AVLNode { Tele data;AVLNode *left,*right;int balance; AVLNode():left(NULL),right(NULL),balance(0){} AVLNode(Tele d,AVLNode *l=NULL,AVLNode *r=NULL): data(d),left(l),right(r),balance(0){} }; Tele RefValue; //protected: int Insert(AVLNode * &tree,Tele x,int &taller); Tele Delete(AVLNode* &T,Tele e); void Delete_Rightbalance(AVLNode* &T,int &shorter); void Delete_Leftbalance(AVLNode* &T,int &shorter); void DeleteAVL(AVLNode* &T,Tele e); void RotateLeft(AVLNode * Tree,AVLNode * &NewTree); void RotateRight(AVLNode * Tree,AVLNode * &NewTree); void LeftBalance(AVLNode * &Tree,int &taller); void RightBalance(AVLNode * &Tree,int &taller); //int Height(AVLNode * t)const; public: AVLNode * root; void find(const string &x,AVLNode *ptr)const { if(ptr==NULL) cout<<"对不起，系统内无此人!!!"<<endl; else if(x<ptr->data.name) find(x,ptr->left); else if(x>ptr->data.name) find(x,ptr->right); else { cout<<"你查找的姓名是: "<<ptr->data.name<<endl; cout<<ptr->data.name<<"的固定电话是： "<<ptr->data.phoneNumber <<endl; cout<<ptr->data.name<<"的移动电话是： "<<ptr->data.mobileNumber<<endl; cout<<ptr->data.name<<"的电子邮件是： "<<ptr->data.email<<endl; } } AVLNode * Find(string n,AVLNode * ptr) {//查找 if(ptr==NULL)return NULL; else if(n<ptr->data.name) return Find(n,ptr->left); else if(n>ptr->data.name) return Find(n,ptr->right); else return ptr; } AVLTree():root(NULL){} AVLTree(Tele Ref):RefValue(Ref),root(NULL){} int Insert(Tele x) { int taller;return Insert(root,x,taller); } //friend istream &operator >>(istream& in,AVLTree &Tree); //friend ostream &operator<<(ostream& out,const AVLTree &Tree); int Height()const; //void Traverse(AVLNode *ptr,ostream &out)const; void change(string n);//修改 }; //*********************************************************** void AVLTree ::RotateLeft ( AVLNode *Tree,AVLNode * &NewTree ) { NewTree = Tree->right; Tree->right = NewTree->left; NewTree->left = Tree; } //************************************************************** void AVLTree::RotateRight ( AVLNode *Tree, AVLNode * &NewTree) { NewTree = Tree->left; Tree->left = NewTree->right; NewTree->right = Tree; } //*************************************************************** void AVLTree::LeftBalance(AVLNode * &Tree,int &taller) { AVLNode *leftsub=Tree->left,* rightsub; switch(leftsub->balance) { case -1: Tree->balance=leftsub->balance=0; RotateRight(Tree,Tree);taller=0;break; case 0: break; case 1: if(leftsub->right!=NULL) { rightsub=leftsub->right; switch(rightsub->balance) { case -1: Tree->balance=1;leftsub->balance=0;break; case 0: Tree->balance=leftsub->balance=0;break; case 1: Tree->balance=0;leftsub->balance=-1;break; } } else break; rightsub->balance=0; RotateLeft(leftsub,Tree->left); RotateRight(Tree,Tree);taller=0; } } //******************************************************************* void AVLTree::RightBalance(AVLNode * &Tree,int &taller) { AVLNode *rightsub=Tree->right,* leftsub; switch(rightsub->balance) { case -1: Tree->balance=rightsub->balance=0; RotateRight(Tree,Tree);taller=0;break; case 0: break; case 1: if(rightsub->left!=NULL) { leftsub=rightsub->left; switch(leftsub->balance) { case -1: Tree->balance=1;rightsub->balance=0;break; case 0: Tree->balance=rightsub->balance=0;break; case 1: Tree->balance=0;rightsub->balance=-1;break; } } else break; leftsub->balance=0; RotateRight(rightsub,Tree->right); RotateLeft(Tree,Tree);taller=0; } } //************************************************************ int AVLTree::Insert(AVLNode* &tree,Tele x,int &taller) { int success; if(tree==NULL) { tree=new AVLNode(x); success=tree!=NULL? 1:0; if(success) taller=1; } else if(x.name<tree->data.name) { success=Insert(tree->left,x,taller); if(taller) switch(tree->balance) { case -1:LeftBalance(tree,taller);break; case 0:tree->balance=-1;break; case 1:tree->balance=0;taller=0;break; } } else if(x.name>tree->data.name) { success=Insert(tree->right,x,taller); if(taller) switch(tree->balance) { case -1: tree->balance=0;taller=0;break; case 0: tree->balance=1;break; case 1: RightBalance(tree,taller);break; } } return success; } //********************************************************** /*istream &operator>>(istream &in,AVLTree &Tree) { Tele item; cout<<"Construct AVL tree:\n"; cout<<"input data:"; in>>item.name>>item.phoneNumber>>item.mobileNumber>>item.email; while(item.name!=Tree.RefValue) { Tree.Insert(item); cout<<"input data:"; in>>item.name>>item.phoneNumber>>item.mobileNumber>>item.email; } return in; } //************************************************************ ostream &operator<<(ostream &out,const AVLTree &Tree) { out<<"inorder traversal of avl tree.\n"; Tree.Traverse(Tree.root,out); out<<endl; return out; }*/ //************************************************************* /*void AVLTree::Traverse(AVLNode *ptr,ostream &out)const { if(ptr!=NULL) { Traverse(ptr->left,out); out<<"你查找的姓名是: "<<ptr->data.name<<endl; out<<ptr->data.name<<"的固定电话是： "<<ptr->data.phoneNumber <<endl; out<<ptr->data.name<<"的移动电话是： "<<ptr->data.mobileNumber<<endl; out<<ptr->data.name<<"的电子邮件是： "<<ptr->data.email<<endl; //out<<ptr->data.name<<' '<<ptr->data.phoneNumber<<' '<<ptr->data.mobileNumber<<' '<<ptr->data.email; Traverse(ptr->right,out); } }*/ //************************************************************** void AVLTree::change(string n) {//修改 int w; string num; AVLNode *temp; if(!Find(n,root)) { cout<<"对不起，系统内无此人!!!"<<endl; } else { temp=Find(n,root); cout<<"*************************************"<<endl; cout<<" 要修改名字请输入1；"<<endl; cout<<" 要修改固定电话请输入2；"<<endl; cout<<" 要修改移动电话请输入3；"<<endl; cout<<" 要修改邮件请输入4："<<endl; cout<<"*************************************"<<endl; cin>>w; if(w==1) { cout<<"请输入改后的名字: "<<endl; cin>>num; temp->data.name=num; } else if(w==2) { cout<<"请输入改后的固定电话号码: "<<endl; cin>>num; temp=Find(n,root); temp->data.phoneNumber=num; } else if(w==3) { cout<<"请输入改后的移动电话号码: "<<endl; cin>>num; temp=Find(n,root); temp->dat