平衡二叉树的操作演示6.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) {  //  算法 9.9
  // 对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，
  // 即旋转处理之前的左子树的根结点
  BSTree lc;
  lc = p->lchild;            // lc指向*p的左子树根结点
  p->lchild = lc->rchild;    // lc的右子树挂接为*p的左子树
  lc->rchild = p;  p = lc;   // p指向新的根结点
} // R_Rotate


/******************* 左旋 *******************/


void L_Rotate(BSTree &p) {  // 算法 9.10
  // 对以p↑为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，
  // 即旋转处理之前的右子树的根结点
  BSTree rc;
  rc = p->rchild;            // rc指向*p的右子树根结点
  p->rchild = rc->lchild;    // rc的左子树挂接为*p的右子树
  rc->lchild = p;  p = rc;   // p指向新的根结点
} // L_Rotate
       


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

void LeftBalance(BSTree &T) {  // 算法 9.12
  // 对以指针T所指结点为根的二叉树作左平衡旋转处理。
  // 本算法结束时，指针T指向新的根结点
  BSTree lc,rd;
  lc = T->lchild;    // lc指向*T的左子树根结点
  switch (lc->bf) {  // 检查*T的左子树的平衡度，并作相应平衡处理
    case LH:   // 新结点插入在*T的左孩子的左子树上，要作单右旋处理
        T->bf = lc->bf = EH; 
        R_Rotate(T);   
        break;  
    case RH:      // 新结点插入在*T的左孩子的右子树上，要作双旋处理
        rd = lc->rchild;   // rd指向*T的左孩子的右子树根
        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;
        } // switch (rd->bf)
        rd->bf = EH;              
        L_Rotate(T->lchild);  // 对*T的左子树作左旋平衡处理
        R_Rotate(T);          // 对*T作右旋平衡处理
  } // switch (lc->bf) 
} // LeftBalance

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


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)
{  { // 算法9.11
  // 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，
  // 则插入一个数据元素为e的新结点，并返回1，否则返回0。
  // 若因插入而使二叉排序树失去平衡，则作平衡旋转处理，
  // 布尔变量taller反映T长高与否
  if (!T) {  // 插入新结点，树"长高"，置taller为TRUE
    T = (BSTree) malloc (sizeof(BSTNode));  T->data = e;
     T->lchild=NULL;
              T->rchild=NULL;
              T->bf=EH;
              taller=true;
  }
  else {
   if(EQ(e,T->data))    // 树中已存在和e有相同关键字的结点

    {taller=false;printf("已存在相同关键字的结点\n"); return 0;}
          if(LT(e,T->data)){//little tham boot   // 未插入
      if (taller)  // 已插入到*T的左子树中且左子树"长高"
        switch (T->bf) {   // 检查*T的平衡度
          case LH:   // 原本左子树比右子树高，需要作左平衡处理
{ LeftBalance(T);taller=false; break;}
          case EH:   // 原本左、右子树等高，现因左子树增高而使树增高
             T->bf=LH;taller=true;break;
          case RH:   // 原本右子树比左子树高，现左、右子树等高
             T->bf=LH;taller=true;break;  
        } // switch (T->bf)
    } // if
    else {    // 应继续在T↑的右子树中进行搜索
      if (InsertAVL(T->rchild, e, taller)==0) return 0;
      if (taller)         // 已插入到*T的右子树且右子树长高
        switch (T->bf) {  // 检查*T的平衡度
          case LH:   // 原本左子树比右子树高，现左、右子树等高
              T->bf=EH;taller=false;
                                      
                                      break;  
          case EH:   // 原本左、右子树等高，现因右子树增高而使树增高
 T->bf=RH;taller=true;
                                      
                                          break;
          case RH:   // 原本右子树比左子树高，需要作右平衡处理
            RightBalance(T);taller=false;  break;
                                }
        } // switch (T->bf)
    } // else
  } // else 
  return 1;
} //InsertAVL
/*************  左平衡旋转处理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()) );
}