avl.cpp

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->data.mobileNumber=num;
   }
	else if(w==4)
   {
	   	cout<<"请输入改后的邮件:  "<<endl;
	cin>>num;
	temp=Find(n,root);
	temp->data.email=num;
   }
	}

}
//****************************************************************
Tele AVLTree::Delete(AVLNode* &T,Tele e)
{
	//删除结点
	AVLNode* p,*q;
	e=RefValue;
	p=T;
	if(T->right==NULL) {//右子数为空需要重接它的左子数
	    T=T->left;
		free(p);
		shorter=true;
		}
	else if(T->left==NULL) {//重接它的右子数
		T=T->right;
		free(p);
		shorter=true;
		}
		else{ //左右子数均不空
			q=T->left;
			while(q->right!=NULL){//转左，然后向右到尽头
							q=q->right;
						}
			e=q->data;
			}
		return e;
}
//********************************************************************

void AVLTree::Delete_Rightbalance(AVLNode* &T,int& shorter)
{
	if (T->right!=NULL)
	{
	///////////删除在左子树上的，相当于插入在右子树
	AVLNode* rc=T->right,*ld;
	switch(rc->balance){
	case 1://///////双旋 ，先右旋后左旋
		ld=rc->left;
		rc->left=ld->right;
		ld->right=rc;
		T->right=rc->left;
		rc->left=T;
		switch(ld->balance)	{
				case 1:T->balance=0;
						rc->balance=-1;	
						break;
				case 0:T->balance=rc->balance=0;
						break;
				case -1:T->balance=1;
						rc->balance=0;
						break;
				}
		ld->balance=0;
		T=rc;
		shorter=true;break;
	case 0:///////删除在左子树，相当于插入在右子树，左单旋
		T->right=rc->left;
		rc->left=T;
		rc->balance=1;
		T->balance=-1;
		T=rc;
		shorter=0;break;
	case -1:///////删除在左子树，相当于插入在右子树，左单旋
		T->right=rc->left;
		rc->left=T;
		rc->balance=T->balance=0;
		T=rc;
		shorter=true;break;
	}
	}
	//else Delete(T,T->data);

}



void AVLTree::Delete_Leftbalance(AVLNode* &T,int &shorter)/////删除右子树上的，相当于插入在左子树上
{
		AVLNode* p1,*p2;
			if (T->left!=NULL)
	{
		p1=T->left;
		switch(p1->balance) 	{
				case 1:T->left=p1->right;//////右旋
					p1->right=T;
					p1->balance=T->balance=0;
					T=p1;	
					shorter=true;
					break;
				case 0:T->left=p1->right;///////右旋
						p1->right=T;
						p1->balance=-1;
						T->balance=1;
						T=p1;
						shorter=false;
						break;
				case -1:p2=p1->right;//////////右双旋
						p1->right=p2->left;
						p2->left=p1;
						T->left=p2->right;
						p2->right=T;
						switch(p2->balance){
											case 1:T->balance=-1;p1->balance=0;break;
											case 0:T->balance=0;p1->balance=0;break;
											case -1:T->balance=0;p1->balance=1;break;
										}
				p2->balance=0;
				T=p2;
			shorter=true;break;
			} 
			}
			//else Delete(T,T->data);

}
//****************************************************************************************
void AVLTree::DeleteAVL(AVLNode* &T,Tele e)
{
	//删除后要保证该二叉树还是平衡的
	Tele n,m;/////标记
	m=RefValue;
	AVLNode* q;
	if(!T) T=NULL;
	else	{
		if(e.name==T->data.name)	{////直接删除
			n=Delete(T,e);
			m=n;
			if(m.name!=RefValue.name) {
				q=T;
				DeleteAVL(T,m);
				q->data=m;}	
		}
		else {
					if(e.name<T->data.name){////在左子树上寻找
							DeleteAVL(T->left,e);
							if(shorter){
									switch(T->balance){
														case 1:T->balance=0;shorter=true;break;
														case 0:T->balance=-1;shorter=false;break;
														case -1:shorter=true;Delete_Rightbalance(T,shorter);break;
												}////switch(T->bf)
											}/////if(shorter)
									}/////if(e<T->data)
					else{ /////////在右子树上寻找
					DeleteAVL(T->right,e);
					if(shorter)
						switch(T->balance){
												case 1:shorter=true;Delete_Leftbalance(T,shorter);break;
												case 0:T->balance=1;shorter=false;break;
												case -1:T->balance=0;shorter=true;break;
										}////////switch(T->bf)
						}////////在右子数上寻找完
				}////////在左右子上完
		}///////////删除完
//return T;
}
//*********************************************************************************************

 int main()
 {
	 string t,ss,c;
	 // AVLTree<Tele> jiang;
	 AVLTree jiang;
	  //ofstream out;
	  //out.open ("jj.txt");
	  ifstream in;
		  Tele tl,z;
	
	 in.open("shan.txt");
	 //int k=0;
	 while(!in.eof())
	{
		//k++;
		in>>tl.name;
		in>>tl.phoneNumber;
		in>>tl.mobileNumber;
		in>>tl.email;
		jiang.Insert(tl);
	}


	 
    int userChoseMenu;
    while (userChoseMenu = PrintMenu()) 
    {
        //根据用户不同选择作出不同处理
        switch (userChoseMenu)
        {
            case 1 : 
                cout << "你选择了1，请输入你要查找的姓名：" << endl;
                //root = BuildTree(root);
				cin>>ss;
              jiang.find(ss,jiang.root);
                break;
            case 2 :
                cout << "你选择了2，请输入要插入信息;" << endl;
				cout <<"请输入姓名： "<<endl;
                 cin>>z.name;
				cout<<"请输入固定电话号码： "<<endl;
				cin>>z.phoneNumber;
				cout<<"请输入移动电话号码：　"<<endl;
				cin>>z.mobileNumber;
				cout<<"请输入电子邮件： "<<endl;
				cin>>z.email;
		  //in.read(z.name,2);//>>z.phoneNumber>>z.mobileNumber>>z.email;
					//root = InsertAVL(root,e);
		            jiang.Insert(z);
                break;
            case 3 :
                cout << "你选择了3，请输入要删除的姓名：" << endl;
				//cout<<"delete!"<<endl;
				cin>>z.name;
				jiang.DeleteAVL(jiang.root,z);
			//	root = DeleteAVL(root,e);
                break;
            case 4 :
                cout << "你选择了4，请输入要修改人的姓名：" << endl;
				cin>>c;
			    jiang.change(c);
				//jiang.Insert
                break;
            case 5 :
                cout << "你选择了5，程序将退出。" << endl;
				exit(0);
                break;
            default :
                cout << "无效选择，程序将退出。" << endl;
				exit(0);
                break;
        }
    }

	 return 0;
 }