?? avlnode.h
字號:
//this is avl tree node
#include "Item.h"
class avlNode//平衡二叉樹結(jié)點類
{
public:
avlNode(Index val);//構(gòu)造函數(shù)
void release();//析構(gòu)用函數(shù)
int add(avlNode* &p,Index val);//插入一個值；返回新的avl樹的根結(jié)點的指針
void preorderview(avlNode *current,int i=-1);//前序周游
avlNode* remove(Index val,avlNode* &waste,int &flag);//刪除以當(dāng)前結(jié)點的為根的avl樹中的val結(jié)點
avlNode* findNodeValue(Index val);//查找val結(jié)點
Index value;//碼值
int bf;// balance factor
avlNode * leftptr;//左右指針
avlNode * rightptr;
avlNode * removeLeftmostElement(avlNode* &childptr,int &flag);//找到最左的結(jié)點
avlNode * LL_singleRotation();//在插入時候左子樹LL失衡的時候調(diào)整，返回新的樹根的指針
avlNode * RR_singleRotation();//在插入時候右子樹RR失衡的時候調(diào)整，返回新的樹根的指針
avlNode * LR_doubleRotation();//在插入時候左子樹LR失衡的時候調(diào)整，返回新的樹根的指針
avlNode * RL_doubleRotation();//在插入時候右子樹RL失衡的時候調(diào)整，返回新的樹根的指針
};
avlNode::avlNode(Index val)
{
value=val;
leftptr=NULL;
rightptr=NULL;
bf=0;
}
void avlNode::release()
{
if (leftptr)
{//刪除左子樹中的結(jié)點
leftptr->release();//遞歸調(diào)用
delete leftptr;
leftptr=0;
}
if (rightptr)
{//刪除右子樹中的結(jié)點
rightptr->release();//遞歸調(diào)用
delete rightptr;
rightptr=0;
}
}
int avlNode::add(avlNode* &rp,Index val)
{//返回值表明以當(dāng)前結(jié)點為根的樹是否再插入之后增高，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)
{//原來已經(jīng)傾斜，左邊失衡，需要做平衡處理
if (rp->leftptr->bf<0) //插入在左側(cè)，單旋轉(zhuǎn)
rp = LL_singleRotation();
else rp = LR_doubleRotation(); //插入在右側(cè)，雙旋轉(zhuǎn)
return 0;
}
return --bf; // bf=(0, +1)的情況，不需要調(diào)整樹，只要修改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)
{//原來已經(jīng)傾斜，需要做平衡處理
if (rp->rightptr->bf>0) //插入在右側(cè)，單旋轉(zhuǎn)
rp = RR_singleRotation();
else rp = RL_doubleRotation(); //插入點在右側(cè).雙旋轉(zhuǎn)
return 0;
}
return ++bf; // bf=(0, -1)的情況，不需要調(diào)整樹，只要修改bf
}
}
avlNode* avlNode::remove(Index val,avlNode* &waste,int &flag)
{
if (val.account==value.account)
{
waste=this;
//當(dāng)沒有右子樹的時候返回左子樹
if(rightptr==NULL)
{
flag=1;
return leftptr;
}
//刪除右子樹中的最小結(jié)點
int oldbf=rightptr->bf;
avlNode* newroot;
rightptr=rightptr->removeLeftmostElement(newroot,flag);//找到后返回已經(jīng)平衡的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)
{//雙旋轉(zhuǎn)
return newroot->LR_doubleRotation();
}
else
{//單旋轉(zhuǎn)
return newroot->LL_singleRotation();
}
}
return newroot;
}
else if(val.account<value.account)
{//從左子樹中刪除
if(leftptr==NULL)
return this;
//執(zhí)行刪除
int oldbf=leftptr->bf;
leftptr=leftptr->remove(val,waste,flag);//遞歸調(diào)用
//調(diào)整左子樹
avlNode* leftchild=leftptr;
//計算刪除后的子樹對當(dāng)前的根結(jié)點的平衡因子的影響
if (leftchild==NULL)
bf++;
else if((leftchild->bf!=oldbf)&&(leftchild->bf==0))
bf++;
if (bf>1)//失衡
{//調(diào)整
int newoldbf=rightptr->bf;
if (newoldbf<0)//雙旋轉(zhuǎn)
{
return RL_doubleRotation();
}
else
{//單旋轉(zhuǎn)
avlNode* temp= RR_singleRotation();
if(flag==1)
bf++;
return temp;
}
}
return this;
}
else
{//從右子樹中刪除
if(rightptr==NULL)
return this;
//執(zhí)行刪除
int oldbf=rightptr->bf;
rightptr=rightptr->remove(val,waste,flag);//遞歸調(diào)用
//調(diào)整右子樹
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)
{//雙旋轉(zhuǎn)
return LR_doubleRotation();
}
else
{//單旋轉(zhuǎn)
avlNode* temp= LL_singleRotation();
if(flag==1)
bf--;
return temp;
}
}
return this;
}
}
avlNode* avlNode::removeLeftmostElement(avlNode* &childptr,int &flag)
{//flag 表示子樹高度是否變化
avlNode* leftchild=leftptr;
//找到最小的值，返回，否則遞歸調(diào)用
if (leftchild==NULL)
{
childptr=this;
flag=1;
return rightptr;
}
int oldbf=leftchild->bf;
leftptr=leftchild->removeLeftmostElement(childptr,flag);//遞歸調(diào)用
//調(diào)整左子樹平衡
avlNode* newleftchild=leftptr;
//計算刪除后的子樹的高度變化
if((newleftchild==NULL)&&(rightptr==NULL))
flag=1;
//計算刪除后的子樹對當(dāng)前的根結(jié)點的平衡因子的影響
if (newleftchild==NULL)
bf++;
else if((newleftchild->bf!=oldbf)&&(newleftchild->bf==0))
bf++;
if (bf>1)//失衡
{//調(diào)整
int newoldbf=rightptr->bf;
if (newoldbf<0)//雙旋轉(zhuǎn)
{
return RL_doubleRotation();
}
else
{//單旋轉(zhuǎn)
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);//遞歸調(diào)用
else
return NULL;
}
else
{//小于的話在左子樹中查找
if (leftptr!=NULL)
return leftptr->findNodeValue(val);//遞歸調(diào)用
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");
}
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -