avlnode.h

这是一个银行账户的管理程序

//this is avl tree node 
#include "Item.h"

class avlNode//平衡二叉树结点类
{
	public:
		avlNode(Index val);//构造函数
		void release();//析构用函数								
		int add(avlNode* &p,Index val);//插入一个值；返回新的avl树的根结点的指针
		void preorderview(avlNode *current,int i=-1);//前序周游
		avlNode* remove(Index val,avlNode* &waste,int &flag);//删除以当前结点的为根的avl树中的val结点
		avlNode* findNodeValue(Index val);//查找val结点
		Index value;//码值

		int bf;// balance factor
		avlNode * leftptr;//左右指针
		avlNode * rightptr;
		avlNode * removeLeftmostElement(avlNode* &childptr,int &flag);//找到最左的结点
		avlNode * LL_singleRotation();//在插入时候左子树LL失衡的时候调整，返回新的树根的指针
		avlNode * RR_singleRotation();//在插入时候右子树RR失衡的时候调整，返回新的树根的指针
		avlNode * LR_doubleRotation();//在插入时候左子树LR失衡的时候调整，返回新的树根的指针
		avlNode * RL_doubleRotation();//在插入时候右子树RL失衡的时候调整，返回新的树根的指针
	
};


avlNode::avlNode(Index val)
{
	value=val;
	leftptr=NULL;
	rightptr=NULL;
	bf=0;
}


void avlNode::release()
{
	if (leftptr)
	{//删除左子树中的结点
		leftptr->release();//递归调用
		delete leftptr;
		leftptr=0;
	}
	if (rightptr)
	{//删除右子树中的结点
		rightptr->release();//递归调用
		delete rightptr;
		rightptr=0;
	}
}


int avlNode::add(avlNode* &rp,Index val)
{//返回值表明以当前结点为根的树是否再插入之后增高，0:非增高，非0:增高
	if (val.account <value.account)
	{//左子树插入
		if (rp->leftptr==NULL)
			rp->leftptr=new avlNode(val);
		else if(rp->leftptr->add(rp->leftptr,val)==0)//插入后子树没有增高
			return 0;
		if (rp->bf==-1)
		{//原来已经倾斜，左边失衡，需要做平衡处理
	       if (rp->leftptr->bf<0)  //插入在左侧，单旋转
	             rp = LL_singleRotation();
	       else rp = LR_doubleRotation();	//插入在右侧，双旋转
		   return 0;
		}
		return --bf;   // bf=(0, +1)的情况，不需要调整树，只要修改bf
	}
	else
	{
		if (rp->rightptr==NULL)
			rp->rightptr=new avlNode(val);
		else if (rp->rightptr->add(rp->rightptr,val)==0)//插入后子树没有增高 
			return 0;
		if(rp->bf==1)
		{//原来已经倾斜，需要做平衡处理
	       if (rp->rightptr->bf>0)    //插入在右侧，单旋转
	           rp = RR_singleRotation();
	       else rp = RL_doubleRotation();  //插入点在右侧.双旋转
		   return 0;
		}
		return ++bf; // bf=(0, -1)的情况，不需要调整树，只要修改bf
	}
}


avlNode* avlNode::remove(Index val,avlNode* &waste,int &flag)
{
	if (val.account==value.account)
	{
		waste=this;
		//当没有右子树的时候返回左子树
		if(rightptr==NULL)
		{
			flag=1;
			return leftptr;
		}
		//删除右子树中的最小结点
		int oldbf=rightptr->bf;
		avlNode* newroot;
		rightptr=rightptr->removeLeftmostElement(newroot,flag);//找到后返回已经平衡的avl树的根指针
		newroot->leftptr=leftptr;
		newroot->rightptr=rightptr;
		if((flag==1)&&(bf==1))
			flag=1;
		else flag=0;
		if(flag==1)
		{
			newroot->bf=bf--;
		}
		else newroot->bf=bf;
        //左树的平衡
		avlNode* rightchild=newroot->rightptr;
	    if (rightchild==NULL) 
		    bf--;
	    else if((rightchild->bf!=oldbf)&&(rightchild->bf==0))
		    bf--;
    	if (bf<-1)
		{
		    int newoldbf=newroot->leftptr->bf;
	        if (newoldbf>0)
			{//双旋转
    	       return newroot->LR_doubleRotation();
			}
	        else
			{//单旋转
		       return newroot->LL_singleRotation();
           	}
		}
	    return newroot;
		
	}
	else if(val.account<value.account)
	{//从左子树中删除
		if(leftptr==NULL)
			return this;
		//执行删除
		int oldbf=leftptr->bf;
		leftptr=leftptr->remove(val,waste,flag);//递归调用
        //调整左子树
        avlNode* leftchild=leftptr;
	    //计算删除后的子树对当前的根结点的平衡因子的影响
	    if (leftchild==NULL)
		   bf++;
	    else if((leftchild->bf!=oldbf)&&(leftchild->bf==0))
		   bf++;
	    if (bf>1)//失衡
		{//调整
		   int newoldbf=rightptr->bf;
	       if (newoldbf<0)//双旋转
		   {
	           return RL_doubleRotation();
		   }
	       else
		   {//单旋转
		       avlNode* temp= RR_singleRotation();
			   if(flag==1)
				   bf++;
			   return temp;
		   }
		}
    	return this;
	}
	else
	{//从右子树中删除
		if(rightptr==NULL)
			return this;
		//执行删除
		int oldbf=rightptr->bf;
		rightptr=rightptr->remove(val,waste,flag);//递归调用
		//调整右子树
		avlNode* rightchild=rightptr;
    	if (rightchild==NULL) 
		  bf--;
	    else if((rightchild->bf!=oldbf)&&(rightchild->bf==0))
		  bf--;
	    if (bf<-1)
		{
		  int newoldbf=leftptr->bf;
	      if (newoldbf>0)
		  {//双旋转
    	      return LR_doubleRotation();
		  }
	      else
		  {//单旋转
			  avlNode* temp= LL_singleRotation();
			  if(flag==1)
			    bf--;
			   return temp;
		   }
		} 
	    return this;
	}
}

avlNode* avlNode::removeLeftmostElement(avlNode* &childptr,int &flag)
{//flag 表示子树高度是否变化
	avlNode* leftchild=leftptr;
	//找到最小的值，返回，否则递归调用
	if (leftchild==NULL)
	{
		childptr=this;
		flag=1;
		return rightptr;
	}
	int oldbf=leftchild->bf;
	leftptr=leftchild->removeLeftmostElement(childptr,flag);//递归调用
	//调整左子树平衡
	avlNode* newleftchild=leftptr;
	//计算删除后的子树的高度变化
	if((newleftchild==NULL)&&(rightptr==NULL))
		flag=1;
	//计算删除后的子树对当前的根结点的平衡因子的影响
	if (newleftchild==NULL)
		bf++;
	else if((newleftchild->bf!=oldbf)&&(newleftchild->bf==0))
		bf++;
	if (bf>1)//失衡
	{//调整
		int newoldbf=rightptr->bf;
	    if (newoldbf<0)//双旋转
		{
	       return RL_doubleRotation();
		}
	    else
		{//单旋转
		   return RR_singleRotation();
		}
	}
	return this;
}


avlNode* avlNode::findNodeValue(Index val)
{
	if (val.account==value.account)
	{
		return this;
	}
	else if (val.account>value.account)
	{//大于的话在右子树中查找
		if (rightptr!=NULL)
			return rightptr->findNodeValue(val);//递归调用
		else 
			return NULL;
	}
	else
	{//小于的话在左子树中查找
		if (leftptr!=NULL)			
			return leftptr->findNodeValue(val);//递归调用
		else
			return NULL;
	}
}

avlNode* avlNode::LL_singleRotation()
{
	avlNode *p;
	p=leftptr;
	leftptr=p->rightptr;
	bf=0;
	p->rightptr=this;
    if(p->bf==0)
	  p->bf=1;
	else p->bf=0;
	return p;
}

avlNode* avlNode::LR_doubleRotation()
{
	avlNode *p,*q;
	q=leftptr;
	p=q->rightptr;
	q->rightptr=p->leftptr;
	leftptr=p->rightptr;
	p->leftptr=q;
	bf=q->bf=0;
	if(p->bf==-1) bf=1;
	if(p->bf==1) q->bf=-1;
	p->rightptr=this;
	p->bf=0;
	return p;
}

avlNode* avlNode::RR_singleRotation()
{
	avlNode *p;
	p=rightptr;
	rightptr=p->leftptr;
	bf=0;
	p->leftptr=this;
    if(p->bf==0) 
	  p->bf=-1;
	else p->bf=0;
	return p;
}

avlNode* avlNode::RL_doubleRotation()
{
	avlNode *p,*q;
	q=rightptr;
	p=q->leftptr;
	q->leftptr=p->rightptr;
	rightptr=p->leftptr;
	p->rightptr=q;
	bf=q->bf=0;
	if(p->bf==-1) q->bf=1;
	if(p->bf==1) bf=-1;
	p->leftptr=this;
	p->bf=0;
	return p;
}

void InsertAccount(int acc)
{
	Item newuser;
	int pass1,pass2;
	printf("您的帐号是:%d\n",acc);
	printf("请输入您的密码:");
	scanf("%d",&pass1);
	bool flag=false;
	while(flag==false)
	{
		printf("请确认，再次输入您的密码:");
		scanf("%d",&pass2);
		if(pass1==pass2)
		{
			newuser.password=pass1;
			flag=true;
		}
		else
			printf("密码不匹配，请重新输入\n");
	}
}