phecs.cpp

1.本程序演示平衡二叉树的插入,删除,查找,。 2.首先要先初始二叉树为空树； 3.接着要实现平衡二叉树的插入

/*---------------------------------------------------------------------------------*/
 #include<string.h>
 #include<ctype.h>
 #include<malloc.h> 
 #include<limits.h> 
 #include<stdio.h> 
 #include<stdlib.h> 
 #include<io.h>
 #include<math.h> 
 #include<process.h>
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define INFEASIBLE -1
 typedef int Status;
 typedef int Boolean;
#define LH +1  
#define EH  0  
#define RH -1 
typedef char KeyType; 
typedef struct
 {
   KeyType key;
   int order;
 }ElemType; 
 #define EQ(a,b) ((a)==(b))
 #define LT(a,b) ((a)<(b))
 #define LQ(a,b) ((a)<=(b))
typedef struct BSTNode
 {
   ElemType data;
   int bf; 
   struct BSTNode *lchild,*rchild; 
 }BSTNode,*BSTree;


/*-----------------------------------------------------------------------------------*/


Status InitDSTable(BSTree *DT)  
 { /* 操作结果: 构造一个空的动态查找表DT */
   *DT=NULL;
   return OK;
 }

/*-----------------------------------------------------------------------------------*/

void R_Rotate(BSTree &p)/*对以*p为根的二叉排序树作右旋处理*/
{                       /*处理之后p指向新的树根结点，即旋转处理这前的左子树的根结点*/
 BSTree lc;
 lc=p->lchild;          /*lc指向的*p的左子树根结点*/
 p->lchild=lc->rchild;  /*lc的右子树挂接为*p的左子树*/
 lc->rchild=p;          
 p=lc;                  /*p指向新的根结点*/
}
void L_Rotate(BSTree &p)/*对以*p为根的二叉排序树作左旋处理*/
{                       /*处理之后p指向新的树根结点，即旋转处理这前的右子树的根结点*/
 BSTree rc;
 rc=p->rchild;          /*rc指向的*p的右子树根结点*/
 p->rchild=rc->lchild;  /*rc的左子树挂接为*p的右子树*/
 rc->lchild=p;          /*p指向新的根结点*/
 p=rc;
}
void LeftBalance(BSTree &T)/*对以指针T所指结点为根的二叉排序树作左平衡旋转处理*/
{                         /*处理之后T指向新的树根结点*/
 BSTree lc,rd; 
 lc=T->lchild;
 switch(lc->bf)             /*检查*T的左子树的平衡度，并作相应平衡处理*/
 {
 case LH:                  /*新结点插入在*T的左孩子的左子树上，要作右旋处理*/
	      T->bf=lc->bf=EH;
          R_Rotate(T);
          break;
 case RH:                 /*新结点插入在*T的左孩子的右子树上，要作双旋处理*/
	      rd=lc->rchild;
          switch(rd->bf)/*修改*T及其左孩子的平衡因子*/
          {
           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);     /*对*T的左子树作左旋平衡处理*/
          R_Rotate(T);             /*对*T作右旋平衡处理*/
 }
}
void RightBalance(BSTree &T)/*对以指针T所指结点为根的二叉排序树作右平衡旋转处理*/
{                           /*处理之后T指向新的树根结点*/
 BSTree rc,ld;
 rc=T->rchild;              /*检查*T的右子树的平衡度，并作相应平衡处理*/
 switch(rc->bf)             
 {
  case RH:                  /*新结点插入在*T的右孩子的右子树上，要作右旋处理*/
	       T->bf=rc->bf=EH;
           L_Rotate(T);
           break;
  case LH:                  /*新结点插入在*T的右孩子的左子树上，要作双旋处理*/
	       ld=rc->lchild;
           switch(ld->bf)   /*修改*T及其右孩子的平衡因子*/
           {
            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;
           }
           ld->bf=EH;
           R_Rotate(T->rchild);/*对*T的右子树作左旋平衡处理*/
           L_Rotate(T);        /*对*T作右旋平衡处理*/
 }
}


/*-----------------------------------------------------------------------------------*/

BSTree SearchBST(BSTree T,KeyType key)
 { /* 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素， */
   /* 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。算法9.5(a) */
   if((!T)||EQ(key,T->data.key))
     return T; /* 查找结束 */
   else if LT(key,T->data.key) /* 在左子树中继续查找 */
     return SearchBST(T->lchild,key);
   else
     return SearchBST(T->rchild,key); /* 在右子树中继续查找 */
 }


/*-----------------------------------------------------------------------------------*/

Status InsertAVL(BSTree& T,ElemType e,Boolean& taller)
{/*若在T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点*/
 /*并返回1,否则返回0，如因插入而失去平衡，则作平衡旋转处理，taller反映T长高与否*/
 if(!T)
 {/*插入新结点，树长高*/
  T=(BSTree)malloc(sizeof(BSTNode));
  T->data.key=e.key;
  T->lchild=T->rchild=NULL;
  T->bf=EH;
  taller=true;
 }
 else
 {
 if(e.key==T->data.key){         /*存在相同关键字结点，不插入*/
  taller=false;
  return false;
  }
 else if(e.key<T->data.key)/*在*T的左子树中进行搜索*/
  {
   if(!InsertAVL(T->lchild,e,taller))
     return false;
   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;
       }
    }
    else                          /*在*T的右子树进行搜索*/
      {
      if(!InsertAVL(T->rchild,e,taller))
         return false;
	       if(taller)
          switch(T->bf)
          {
           case RH: RightBalance(T);/*右平衡处理*/
                    taller=false;
                    break;
           case EH: T->bf=RH;
                    taller=true;
                    break;
           case LH: T->bf=EH;
                    taller=false;
           }
        }
      }
      return true;
 } 


/*-----------------------------------------------------------------------------------*/

Status Delete(BSTree& p,ElemType &e,Boolean &flag)/*从二叉树中删除结点e;*/
{ 
  BSTree q,s;
  if(!p->rchild)      /*如果右子树空,则重接它的左子树*/
  {
      q=p;               /*q指向删除结点；*/
	  if(p->lchild)      /*被删除结点的左子树的不空；*/
	  {
		  p->lchild->bf=p->bf;     /*把被删结点平衡因子赋给左子树结点；*/
		  e.key=p->lchild->data.key;
	  }
	  p=p->lchild;      
	  free(q);
	  flag=1;
  }
   else if(!p->lchild)   /*如果左子树空,则重接它的右子树*/
   {
	   q=p;
	   p->rchild->bf=p->bf;
	   e.key=p->rchild->data.key;
	   p=p->rchild; 
	   free(q);
	   flag=1;
   }
   else
   {
      q=p; s=p->lchild;
      while(s->rchild){q=s; s=s->rchild;}
      p->data.key=s->data.key;
      if(q!=p)q->rchild=s->lchild;
      else {
		  q->lchild=s->lchild;
		  p->bf=RH;
	  }
	  e.key=q->data.key;
      free(s);
      }
   return true;
}
Status DeleteBST(BSTree& T,ElemType &e,Boolean &flag)
{/*在二叉树T中删除存在关键字等于e.key的数据元素时，则删除该数据元素的结点*/

   if(!T)return false;/*不存在此结点*/
   else{
      if(e.key==T->data.key)return Delete(T,e,flag);/*找到结点*/
	  else if(e.key<T->data.key) {
		      if(!DeleteBST(T->lchild,e,flag))return false;
			  return true;
			  }
	  else {
	          if(!DeleteBST(T->rchild,e,flag))return false;
			  return true;
			 }
	  }
}
void Balance(BSTree& T,ElemType e, Boolean &lower,Boolean &flag)
{/*删除结点的平衡处理*/
 if(!T) 
 {
	lower=true;
	return;
 }
 if(e.key==T->data.key)
 {
	if(flag==1)
		switch(T->bf)
	{
		case RH:
		case LH: T->bf=EH;
			     lower=true;
			     break;
	}
   else switch(T->bf)
        {
         case RH: lower=false;
                  break;
         case EH: T->bf=LH;
                  lower=false;
                  break;
         case LH: LeftBalance(T);/*作左平衡处理*/
                  lower=true;
				  break;
         }
   return ;
   } 
 if(e.key<T->data.key)
 {
    Balance(T->lchild,e,lower,flag);
    if(lower)
       switch(T->bf)
       {
        case LH: T->bf=EH;
                 lower=true;
                 break;
        case EH: T->bf=RH;
                 lower=false;
                 break;
        case RH: RightBalance(T);/*作右平衡处理*/
                 lower=true;
				 break;
        }
      }
 if(e.key>T->data.key)
 {
     Balance(T->rchild,e,lower,flag);
     if(lower)
        switch(T->bf)
        {
         case RH: T->bf=EH;
                  lower=true;
                  break;
         case EH: T->bf=LH;
                  lower=false;
                  break;
         case LH: LeftBalance(T);/*作左平衡处理*/
                  lower=true;
				  break;
	 } 
      }
 return ;
}
Status DeleteAVL(BSTree& T,ElemType &e,Boolean& lower)
{
	int flag=0;
	if(!DeleteBST(T,e,flag))return false;
	else Balance(T,e,lower,flag);/*作平衡处理*/
	return true;
}


/*-----------------------------------------------------------------------------------*/

void BlankOutput(int i)
{
 while(i >=0){
    printf(" ");
    i--;
  }
}
void BSTreeOutput(BSTree T,int i)/*输出二叉树*/
{
 if(T != NULL)
  {
   BlankOutput(i);
   printf("%d(%d)\n",T->data.key,T->bf);
 }
 else
  { 
   BlankOutput(i);printf("NULL\n");return; 
 }
  BSTreeOutput(T->lchild,i+5);
  BSTreeOutput(T->rchild,i+5);
}




/*-----------------------------------------------------------------------------------*/


void Display(void)/*界面输出*/
{
  
  printf("              *************************************************\n");
  printf("              *    操作提示：(共分为4种操作)                  *\n");
  printf("              *             输入0：退出                       *\n");
  printf("              *             输入1：在T树中插入                *\n");
  printf("              *             输入2：在T树中查找                *\n");
  printf("              *             输入3：在T树中删除                *\n");
  printf("              *************************************************\n");
  printf("                    ***************************************\n");
}


/*-----------------------------------------------------------------------------------*/

 void main()
 {int st,taller,fg,lower,out;
   BSTree dt,p;
   ElemType e;
   KeyType j;
   fg=1;out=0;
   Display();
   InitDSTable(&dt); /* 初始化空树 */
  
 while(fg!=0)
	{
	 printf("\n请输入你要进行的操作(退出：0；插入：1；查找：2；删除:3):");
	 scanf("%d",&st);	
	 switch(st)
   { 
	   case 0: fg=0; exit(2);break;
	   
		case 1: printf("请输入要插入元素的关键字(整数):");
			    scanf(" %d",&e.key);
				InsertAVL(dt,e,taller);
				out=1;
				break;
		case 2: printf("\n请输入待查找的关键字: ");
               scanf("%d",&j);
               p=SearchBST(dt,j); /* 查找给定关键字的记录 */
               if(p)
               printf("** ** ** ** ** ** ** ** \n!查找成功!其结果为:(%d,%d) ** ** ** ** **\n",p->data.key,p->bf);
               else
               printf("** ** ** ** ** ** ** ** \n!查找失败!平衡二叉树中不存在此元素 ** ** ** ** **\n");
               if(dt==NULL)printf("** ** ** ** ** ** ** ** 且平衡二叉树此时为空树!\n");
        	    out=1;
			    break;
       case 3: printf("请输入要删除元素的关键字(整数):");
			    scanf(" %d",&e.key);
				if(DeleteAVL(dt,e,lower)) printf("! 删除成功!!\n");
				                     else printf("! 无此元素,删除失败 !\n");
				out=1; 
				break;
	   default :printf("          ! !输入出错! !\n");
		        printf("请输入  0	   或 	1   或	 2	 或	 3\n");
		        out=0;
				break;
      }
         if(out==1)
		 {   printf("\n二叉平衡树为(其中括号里的数表示为平衡因子):\n"); 
			 printf("根结点后上层为左子树,下层为右子树!\n"); 
	         BSTreeOutput(dt,30);
		 }
	}
}


/*-----------------------------------------------------------------------------------*/