关于数据结构的问题，平衡二叉树的删除算法？

Question

class CNode : public CObject     //结点类；
{
 
protected:
int data;
public:
int bf;                //平衡因子
         CNode* lchild;         //左子树
        CNode* rchild;         //右子树
 
 
public:
CNode();
CNode(int);
int GetData();
void SetData(int);
  void SetLchild(CNode*);
    void SetRchild(CNode*);
 
CNode* GetLchild();
CNode* GetRchild();
 
CNode* operator=(CNode* p);
 
 
};BOOL InsertAVL(CNode* &T,int e,BOOL &taller)   //插入算法，T为头结点，若不
{                                              //存在和e相同的结点，
if (!T)                               //若失去平衡，作旋转处理
{
T=new CNode(e);
T->bf=EH;taller=TRUE;
}
else
{
if (e==T->GetData())
{
taller=FALSE;
return 0;
}
if (e<T->GetData())
{
if (!InsertAVL(T->lchild,e,taller)) return 0;
if (taller)
switch(T->bf)
{
case LH:
LeftBalance(T);     taller=FALSE; break;
case EH:
T->bf=LH; taller=TRUE; break;
case RH:
T->bf=EH; taller=FALSE; break;
}
}
else
{
if (!InsertAVL(T->rchild,e,taller)) return 0;
if (taller)
switch(T->bf)
{
case LH:
T->bf=EH;taller=FALSE; break;
case EH:
T->bf=RH;taller=TRUE;break;
case RH:
RightBalance(T);taller=FALSE;break;
}
}
}
return 1;}void CPaintDoc::LeftBalance(CNode *&T )             //左旋平衡处理
{
CNode* lc;
CNode* rd; lc=T->GetLchild();
switch (lc->bf){
case LH:
T->bf=lc->bf=EH;
R_Rotate(T);break;
case RH:
rd=lc->rchild;
switch (rd->bf){
case LH:T->bf=RH;lc->bf=EH; break;
case EH:T->bf=lc->bf=EH;    break;
case RH:T->bf=EH;lc->bf=LH; break;
}
rd->bf=EH;
L_Rotate(T->lchild);             //Error
R_Rotate(T);
}
}void RightBalance(CNode* &T)                 //右旋平衡处理
{
CNode* rc;
CNode* ld;
rc=T->GetRchild();
switch (rc->bf){
case RH:
T->bf=rc->bf=EH;
L_Rotate(T);break;
case LH:
ld=rc->GetLchild();
switch (ld->bf){
case RH:T->bf=LH;rc->bf=EH; break;
case EH:T->bf=rc->bf=EH;    break;
case LH:T->bf=EH;rc->bf=RH; break;
}
ld->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T);
}}void L_Rotate(CNode *&p )        //左旋处理
{
CNode* rc;
rc=p->GetRchild();
p->SetRchild(rc->GetLchild());
rc->SetLchild(p);
p=rc;
}void  R_Rotate(CNode *&p )           //左旋处理
{
CNode* lc;
lc=p->GetLchild();
p->SetLchild(lc->GetRchild());
lc->SetRchild(p);
p=lc;
}BOOL DeleteAVL(CNode* &T,int key)   //删除算法，找到待删除结点e，调用Delete
{                                   //函数
 
if (!T) return FALSE;
else 
{

if (key==T->GetData()) {Delete(T);}
else if (key<T->GetData()) return DeleteBST(T->lchild,key);
else return DeleteBST(T->rchild,key);
return TRUE;
}
}void Delete(CNode* &p)         //问题所在，如何删除结点后处理平衡因子
{                              //和作平衡处理？
CNode* q;
    CNode* s;
 
q=s=p;
    
if (p->bf<=0)
{

if (!p->lchild&&!p->rchild)
{
delete (p);
p=NULL;
}
else
{
p=p->rchild;
    if (p->lchild)
{
while(p->lchild)
{
q=p;
p=p->lchild;
}
if (p->rchild) 
{
q->lchild=p->rchild;
}
p->rchild=s->rchild;p->lchild=s->lchild;q->lchild=NULL;
}
else 
{
p->lchild=s->lchild;
}
delete s;
s=NULL;
}
}
else if(p->bf>0)
{
p=p->lchild;

if (p->rchild)
{
while(p->rchild)
{
q=p;
p=p->rchild;
}
if (p->lchild) 
{
q->rchild=p->lchild;
}
p->rchild=s->rchild;p->lchild=s->lchild;q->rchild=NULL;
}
else 
{
p->rchild=s->rchild;
}
 
delete s;
s=NULL;
}
}

Answer 1

class CNode : public CObject     //结点类；
{
 
protected:
int data;
public:
int bf;                //平衡因子
         CNode* lchild;         //左子树
        CNode* rchild;         //右子树
 
 
public:
CNode();
CNode(int);
int GetData();
void SetData(int);
  void SetLchild(CNode*);
    void SetRchild(CNode*);
 
CNode* GetLchild();
CNode* GetRchild();
 
CNode* operator=(CNode* p);
 
 
};BOOL InsertAVL(CNode* &T,int e,BOOL &taller)   //插入算法，T为头点不
{                                              //存在和e相同的结点，
if (!T)                               //若失去平衡，作旋转处理
{
T=new CNode(e);
T->bf=EH;taller=TRUE;
}
else
{
if (e==T->GetData())
{
taller=FALSE;
return 0;
}
if (e<T->GetData())
{
if (!InsertAVL(T->lchild,e,taller)) return 0;
if (taller)
switch(T->bf)
{
case LH:

                                     LeftBalance(T);     
                                     taller=FALSE; break;
case EH:

                                    T->bf=LH; taller=TRUE; break;
case RH:

                                    T->bf=EH; taller=FALSE; break;
}
}
else
{
if (!InsertAVL(T->rchild,e,taller))    return 0;
if (taller)
switch(T->bf)
{
case LH:

                                     T->bf=EH;taller=FALSE; break;
case EH:

                                     T->bf=RH;taller=TRUE;break;
case RH:

                                 RightBalance(T);taller=FALSE;break;
}
}
}
return 1;}void CPaintDoc::LeftBalance(CNode *&T )             //左旋平衡处理
{
CNode* lc;
CNode* rd; lc=T->GetLchild();
switch (lc->bf){
case LH:
T->bf=lc->bf=EH;
R_Rotate(T);break;
case RH:
rd=lc->rchild;
switch (rd->bf){
case LH:T->bf=RH;lc->bf=EH; break;
case EH:T->bf=lc->bf=EH;    break;
case RH:T->bf=EH;lc->bf=LH; break;
}
rd->bf=EH;
L_Rotate(T->lchild);             //Error
R_Rotate(T);
}
}void RightBalance(CNode* &T)                 //右旋平衡处理
{
CNode* rc;
CNode* ld;
rc=T->GetRchild();
switch (rc->bf){
case RH:
T->bf=rc->bf=EH;
L_Rotate(T);break;
case LH:
ld=rc->GetLchild();
switch (ld->bf){
case RH:T->bf=LH;rc->bf=EH; break;
case EH:T->bf=rc->bf=EH;    break;
case LH:T->bf=EH;rc->bf=RH; break;
}
ld->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T);
}}void L_Rotate(CNode *&p )        //左旋处理
{
CNode* rc;
rc=p->GetRchild();
p->SetRchild(rc->GetLchild());
rc->SetLchild(p);
p=rc;
}void  R_Rotate(CNode *&p )           //左旋处理
{
CNode* lc;
lc=p->GetLchild();
p->SetLchild(lc->GetRchild());
lc->SetRchild(p);
p=lc;
}BOOL DeleteAVL(CNode* &T,int key)   //删除算法，找到待删除结点e，调用Delete
{                                   //函数
 
if (!T) return FALSE;
else 
{

if (key==T->GetData()) {Delete(T);}
else if (key<T->GetData()) 
                  return DeleteBST(T->lchild,key);
else return DeleteBST(T->rchild,key);
return TRUE;
}
}void Delete(CNode* &p)         //问题所在，如何删除结点后处理平衡因子
{                              //和作平衡处理？
CNode* q;
         CNode* s;
 
q=s=p;
    
if (p->bf<=0)
{

if (!p->lchild&&!p->rchild)
{
delete (p);
p=NULL;
}
else
{
p=p->rchild;
    if (p->lchild)
{
while(p->lchild)
{
q=p;
p=p->lchild;
}
if (p->rchild) 
{
q->lchild=p->rchild;
}
p->rchild=s->rchild;
                           p->lchild=s->lchild;
                           q->lchild=NULL;
}
else 
{
p->lchild=s->lchild;
}
delete s;
s=NULL;
}
}
else if(p->bf>0)
{
p=p->lchild;

if (p->rchild)
{
while(p->rchild)
{
q=p;
p=p->rchild;
}
if (p->lchild) 
{
q->rchild=p->lchild;
}
p->rchild=s->rchild;
                           p->lchild=s- >lchild;
                           q->rchild=NULL;
}
else 
{
p->rchild=s->rchild;
}
 
delete s;
s=NULL;
}
}

Answer 2

对了，忘了#define LH 1
#define EH 0
#define RH -1