平衡二叉树操作的演示.cpp

平衡二叉树实现一个动态查找表,有三种基本功能:查找,插入删除,还有选项功能:合并两棵平衡二叉树,和分裂两棵平衡二叉树.

#include<stdio.h>
#include<stdlib.h> 
#include <malloc.h>

#define EQ(a,b) ((a)==(b))
#define LT(a,b)  ((a)<(b))
#define LQ(a,b)  ((a)>(b))

#define LH +1   //左高 
#define EH  0   //等高 
#define RH -1   //右高 

#define true 1
#define false 0

/******************定义一个结构 **************/
typedef int KeyType;


typedef struct BSTNode
{
  KeyType data;   //data of boot
  struct BSTNode   *lchild, *rchild;  
  int bf;  //结点的平衡因子 
} BSTNode,*BSTree; 



/******************* 右旋 *******************/


void R_Rotate(BSTree &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)
{
  BSTree rc;
  rc=p->rchild;  //rc指向的*p的右子树根结点
  p->rchild=rc->lchild; //rc的左子树挂接为*p的右子树
  rc->lchild=p;   
  p=rc;   //p指向新的结点
}


/*************  左平衡旋转处理 **************/

void LeftBalance(BSTree &T)
{   
   BSTree lc,rd;
   lc=T->lchild;   //lc pointe to T left child
   switch(lc->bf){
         case LH: T->bf=EH;
                  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);
                  R_Rotate(T);//right high
              }
}


/************  右平衡旋转处理****************/


void RightBalance(BSTree &T)
{   
     BSTree rc,ld;
     rc=T->rchild;
     switch(rc->bf){
           case RH: T->bf=EH;
                    rc->bf=EH;
                    L_Rotate(T); break;
           case LH: ld=rc->lchild;
                    switch(ld->bf){
                         case LH: T->bf=RH; rc->bf=EH; break;
                         case EH: T->bf=rc->bf=EH; break;
                         case RH: T->bf = EH; rc->bf=LH; break; }
                    ld->bf=EH;
                    R_Rotate(T->rchild);
                    L_Rotate(T);
                 }
}


/***************  插入结点 ******************/

int InsertAVL(BSTree &T, KeyType e,int &taller)
{ 
        
     if(!T){  
              T=(BSTree )malloc(sizeof(BSTNode));
              T->data=e;
              T->lchild=NULL;
              T->rchild=NULL;
              T->bf=EH;
              taller=true;//if unexistence make one
                 
                 //return(T);
               }
     else{
           
           if(EQ(e,T->data)){taller=false;printf("已存在相同关键字的结点\n"); return 0;}
           if(LT(e,T->data)){//little tham boot
                          
                          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;

                                        }//switch
                                    }//if
         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;
}
/*************  左平衡旋转处理1 **************/
void LeftBalance1(BSTree &p,int &shorter)
{
  BSTree  p1,p2;
  if(p->bf==1)
   {  p->bf=0;
      shorter=1;
   }
   else if(p->bf==0)
   {  p->bf=-1;
      shorter=0;
   }
   else
   {  p1=p->rchild;
      if(p1->bf==0)
        {  p->rchild=p1->lchild;
           p1->lchild=p;
           p1->bf=1;
           p->bf=-1;
           p=p1;
           shorter=0;
        }
      else if(p1->bf==-1)
        {
           p->rchild=p1->lchild;
           p1->lchild=p;
           p1->bf=p->bf=0;
           p=p1;
           shorter=1;
        }
      else
        {
           p2=p1->lchild;
           p1->lchild=p2->rchild;
           p2->rchild=p1;
           p->rchild=p2->lchild;
           p2->lchild=p;
           if(p2->bf==0)
              {
                 p->bf=0;
                 p1->bf=0;
              }
           else if(p2->bf==-1)
              {
                 p->bf=1;
                 p1->bf=0;
              }
           else 
              {
                  p->bf=0;
                  p1->bf=-1;
              }
           p2->bf=0;
           p=p2;
           shorter=1;
              
        }
  }

}
/************  右平衡旋转处理1****************/

void  RightBalance1(BSTree &p,int &shorter)
{
  BSTree  p1,p2;
  if(p->bf==-1)
   {  p->bf=0;
      shorter=1;
   }
   else if(p->bf==0)
   {  p->bf=1;
      shorter=0;
   }
   else
   {  p1=p->lchild;
      if(p1->bf==0)
        {  p->lchild=p1->rchild;
           p1->rchild=p;
           p1->bf=-1;
           p->bf=1;
           p=p1;
           shorter=0;
        }
      else if(p1->bf==1)
        {
           p->lchild=p1->rchild;
           p1->rchild=p;
           p1->bf=p->bf=0;
           p=p1;
           shorter=1;
        }
      else
        {
           p2=p1->rchild;
           p1->rchild=p2->lchild;
           p2->lchild=p1;
           p->lchild=p2->rchild;
           p2->rchild=p;
           if(p2->bf==0)
              {
                 p->bf=0;
                 p1->bf=0;
              }
           else if(p2->bf==1)
              {
                 p->bf=-1;
                 p1->bf=0;
              }
           else 
              {
                  p->bf=0;
                  p1->bf=1;
              }
           p2->bf=0;
           p=p2;
           shorter=1;
          
        }
  }

}
/************  删除结点****************/
void Delete(BSTree q,BSTree  &r,int &shorter)
{
   if(r->rchild==NULL)
   {
      q->data=r->data;
      q=r;
      r=r->lchild;
      free(q);
      shorter=1;
   }
   else 
   {
     Delete(q,r->rchild,shorter);
     if(shorter==1)
        RightBalance1(r,shorter);
   }
}


int DeleteAVL(BSTree &p,KeyType x,int &shorter)
{
   int k;
   BSTree q;
   if(p==NULL)  {printf("不存在要删除的关键字!!\n"); return 0;}
   else if(x<p->data)
   {
      k=DeleteAVL(p->lchild,x,shorter);
      if(shorter==1)
         LeftBalance1(p,shorter);
         return k;
   }
   else if(x>p->data)
    {
      k=DeleteAVL(p->rchild,x,shorter);
      if(shorter==1)
         RightBalance1(p,shorter);
         return k;
   }
   else
   {
    q=p;
       if(p->rchild==NULL)
       {p=p->lchild;
        free(q);
        shorter=1;
       }
       else if(p->lchild==NULL)
       {p=p->rchild;
        free(q);
        shorter=1;
       }
       else
       {
        Delete(q,q->lchild,shorter);
        if(shorter==1)
            LeftBalance1(p,shorter);
        p=q; 
       
       }
       return 1;
   }
}
/****************打印最后结果平衡树**************/
void Print_BSTree(BSTree &T,int m)//按树状打印输出二叉树的元素,i 表示结点所在层次,初次调用时 m=0 
{   int j;
    if(T->rchild) Print_BSTree(T->rchild,m+1);   
    for(j=1;j<=m;j++) printf("     "); //打印 i 个空格以表示出层次   
      printf("%d \n",T->data); //打印 T 元素,换行 
      if(T->lchild) Print_BSTree(T->lchild,m+1); }//Print_BiTree 
/*****************  查找   **********************/

BSTree BSTree_search(BSTree T,int key)
{
     if((!T)) printf("查找失败!\n");
     else if(EQ(key,T->data))  printf("查找成功!\n");    
     else if (LT(key,T->data))  return(BSTree_search(T->lchild,key));
     else return(BSTree_search(T->rchild,key)); 

}

/******************创建平衡二叉树*****************/
void creat_BSTree(BSTree &bt)
{
  KeyType key;
  bt=NULL;
  int i=0;
  int m;
  printf("\n请输入关键字(以-1结束建立平衡二叉树):");
  scanf("%d",&key);
  
  while(key!=-1){
      InsertAVL(bt,key ,i) ;
   
     printf("\n请输入关键字(以-1结束建立平衡二叉树):");
     scanf("%d",&key);
     
   }
  printf("\n创建平衡二叉树完成.\n");
  m=0;
  printf("**********************************************************\n");
    if(bt)  Print_BSTree(bt,m);
    else    printf("这是一棵空树!!\n\n\n");
  printf("**********************************************************\n");
        
        }
/*****************分裂时中序遍历二叉树***********************/
void inorder(BSTree &bt,int x,BSTree &T1,BSTree &T2)
{  int i=0;
   
   if (bt!=NULL){
      inorder(bt->lchild,x,T1,T2);
      if(LQ(bt->data,x)) InsertAVL(T1,bt->data,i) ;
      else   InsertAVL(T2,bt->data,i) ;
      inorder(bt->rchild,x,T1,T2);
              }
      }


/*********************分裂平衡二叉树**********************/
void   devide_BSTree(BSTree T,int  x)// 
{       int m=0;
       BSTree T1=NULL,T2=NULL;
        inorder(T,x,T1,T2);
     printf("******************分裂出的第一棵树************************\n");
      if(T1)  Print_BSTree(T1,m);
      else    printf("这是一棵空树!!\n\n\n");
      printf("*****************分裂出的第二棵树*************************\n");
      if(T2)  Print_BSTree(T2,m);
      else    printf("这是一棵空树!!\n\n\n");
      printf("**********************************************************\n");
      }
      
/****************合并时中序遍历二叉树****************/      
void inorder1(BSTree &T1,BSTree  &T2)
{ 
    int i=0;
    if (T2!=NULL){
      inorder1(T1,T2->lchild);
      InsertAVL(T1,T2->data,i);
      inorder1(T1,T2->rchild);
              }
}
/****************合并平衡二叉树*****************/
void   unite_BSTree( )
{ 
  int m=0;
  BSTree  T1=NULL,  T2=NULL;
  creat_BSTree(T1);
  creat_BSTree(T2);
  inorder1(T1,T2);
       printf("*****************两棵树合并后形成的树********************\n");
      if(T1)  Print_BSTree(T1,m);
      else    printf("这是一棵空树!!\n\n\n");
       printf("*********************************************************\n");
}


/***************函数主体部分**************/
void body(BSTree &bt)

{  int choi;
   KeyType key;
   
   int i,m;
   KeyType x,y;
   KeyType search_key;
   printf("\n\t**************************************************************\n");
   printf("\t\t1.创建\t2.查找\t3.插入\t4.删除\t5.分裂\t6.合并");
   printf("\n\t**************************************************************\n");
   printf("\n\n\n请输入您所需的操作功能:\t");
   scanf("%d",&choi);
   
   if(choi==1)
      {
	  creat_BSTree(bt);
	  //break;
      }
      
   else if(choi==2)
      {
      printf("请输入要查找的关键字:"); 
      scanf("%d",&search_key);
      BSTree_search(bt,search_key);
      //break;
      }
      
    else if(choi==3)
      {
      i=0;m=0;
      printf("请输入要插入的关键字:"); 
      scanf("%d",&y);
      InsertAVL(bt,y ,i) ;
      printf("**********************************************************\n");
      if(bt)  Print_BSTree(bt,m);
      else    printf("这是一棵空树\n\n\n");
      printf("**********************************************************\n");
      //break;
      }   
         
    else if(choi==4)
      {
      i=0;m=0;
      printf("请输入要删除的关键字:"); 
      scanf("%d",&y);
      DeleteAVL(bt,y,i);
      printf("**********************************************************\n");
      if(bt)  Print_BSTree(bt,m);
      else    printf("这是一棵空树\n\n\n");
      printf("**********************************************************\n");
      //break;
      }  
      

    else if(choi==5)
      {
      printf("请输入要分裂点x的值:");
      scanf("%d",&x);
      devide_BSTree(bt,x);
	  //break;
      }
      
    else if(choi==6)
      
	  unite_BSTree( );
}


void main()
{
    BSTree bt=NULL;
    char c;
    do{
       body(bt);
       c=getchar();
       printf("\n\n是否继续/?(Y/N)");
       scanf("%c",&c);
      }while((c=='Y'||c=='y')&& (c=getchar()) );
}