phecs.cpp

平衡二叉树操作的演示 一、 需求分析 （1） 利用平衡二叉树实现动态查找表。实现查找

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

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

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

enum Boolean {FALSE,TRUE};

typedef int Status;

typedef struct BSTNode{
 int data;
 int bf;//结点的平衡因子
 struct BSTNode *lchild,*rchild;//左、右孩子指针
}BSTNode,*BSTree;

void R_Rotate(BSTree &p){
//右旋处理，处理之后P指向新的树根结点，放置处理之前的左子树的根结点
 BSTree lc;
 lc=p->lchild;   
 p->lchild=lc->rchild;  
 lc->rchild=p;  
 p=lc;
}//R_Rotate

void L_Rotate(BSTree &p){
//左旋处理
 BSTree rc;
 rc=p->rchild;   
 p->rchild=rc->lchild;  
 rc->lchild=p;  
 p=rc;
}//L_Rotate

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

Status InsertAVL(BSTree &T,int e,enum Boolean &taller){
//若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为有的新结点，并返回1，否则返回0。若因插入而使二叉
//排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否
 if(!T){//插入新结点，树“长高”，置taller为TRUE
  T=(BSTree)malloc(sizeof(BSTNode)); T->data=e;
  T->lchild=T->rchild=NULL; T->bf=EH; taller=TRUE;
 }
 else{
  if(EQ(e,T->data))  //树中已存在和e有相同关键字的点则不再插入
   { taller=FALSE; return 0; }
  if(LT(e,T->data)){   //继续在*T的左子树中进行搜索
   if(!InsertAVL(T->lchild,e,taller)) return 0;  //未插入
   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=EH; taller=FALSE; break;
    }//switch(T->bf)
  }//if
  else{      //继续在*T的右子树中进行搜索
   if(!InsertAVL(T->rchild,e,taller)) 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

Status DeleteAVL(BSTree &T,int e,enum Boolean &taller){
//删除平衡二叉树的元素，并做平衡处理
 if(!T)  return 0;
 else {
  if(EQ(e,T->data))  //找到和e相等的结点
  {
   if(!T->lchild&&!T->rchild) {taller=FALSE; free(T); T=NULL;return 1;}//该结点为叶子结点
   else if(T->lchild) {//该结点有左子树
    if(!T->lchild->rchild) {//在左子树中寻找最大值来替代T
     T->data=T->lchild->data;
     T->lchild->data=e;
     DeleteAVL(T->lchild,e,taller);
    }
    else {
     T->data=T->lchild->rchild->data;
     T->lchild->rchild->data=e;
     DeleteAVL(T->lchild->rchild,e,taller);
    }
    if(!taller)  //已从左子树删除且左子树变矮
     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 if
   else if(T->rchild) {//该结点有右子树
    if(!T->rchild->lchild) {//在右子树中寻找最小值来替代T
     T->data=T->rchild->data;
     T->rchild->data=e;
     DeleteAVL(T->rchild,e,taller);
    }
    else {
     T->rchild->data=T->rchild->lchild->data;
     T->rchild->lchild->data=e;
     DeleteAVL(T->rchild->lchild,e,taller);
     }
    if(!taller)    //已从右子树删除且右子树变矮
     switch(T->bf){  //检查*T的平衡度
      case LH:  //原本左子树比右子树高，需要作左平衡处理
       LeftBalance(T); taller=FALSE; break;
      case EH:  //原本左、右子树等高，现因右子树变矮而使树增高
       T->bf=LH; taller=TRUE; break;
      case RH:  //原本右子树比左子树高，现左、右子树等高
       T->bf=EH; taller=FALSE; break;
     }//switch(T->bf)
   }//else if
  }
  if(LT(e,T->data)){   //继续在*T的左子树中进行搜索
   if(!DeleteAVL(T->lchild,e,taller)) return 0;  //未删除
  }//if
  else{      //继续在*T的右子树中进行搜索
   if(!DeleteAVL(T->rchild,e,taller)) return 0;//未删除
  }//else
 }//else
 return 1;
}//DeleteAVL

void Print_BSTree(BSTree T,int i)//按树状打印输出二叉树的元素,i表示结点所在层次,初次调用时i=0
{
  int j;
  if(T->rchild) Print_BSTree(T->rchild,i+1);
  for(j=1;j<=i;j++) printf("     "); //打印i个空格以表示出层次
  printf("%5d\n",T->data); //打印T元素,换行
  if(T->lchild) Print_BSTree(T->lchild,i+1);
}//Print_BiTree

void Destroy_BSTree(BSTree &T)
{//销毁平衡二叉树
 BSTree p;
 p=T;
 while(p->lchild&&p->rchild)
 {
  Destroy_BSTree(p->lchild);
  Destroy_BSTree(p->rchild);
 }
 if(!p->lchild&&p->rchild) Destroy_BSTree(p->rchild);
 if(!p->rchild&&p->lchild) Destroy_BSTree(p->lchild);
 if(!p->lchild&&!p->rchild) free(p);
 T=NULL;
}//Destroy_BSTree

void main()
{
 char num;
 int e,i;
 enum Boolean taller;
 BSTree T,T2;
 T=T2=NULL;
 i=0;
 for( ; ; )
 {
   printf("bstree\n");
   printf(" MENU:\n");
   printf(" 1.Insert;\n");
   printf(" 2.Delete;\n");
   printf(" 3.Quit.\n");
   printf(" 请选择:");
   num=getchar();
   if(num=='1')
   {
    printf("请输入一个整数:");
    scanf("%d",&e);
    taller=FALSE;
    InsertAVL(T,e,taller);
    Print_BSTree(T,i);
   }
   else if(num=='2')
   {
    if(T==NULL) printf("空树!\n");
    else{
     printf("请输入一个整数:");
     scanf("%d",&e);
     taller=TRUE;
     DeleteAVL(T,e,taller);
     if(T==NULL) printf("空树!\n");
     else Print_BSTree(T,i);
    } //else
   }
   else if(num=='3') break;
   else printf("Error!\n");
   getchar();
 } //for
 printf("Tree 1:\n");//合并两个平衡二叉树
 if(T==NULL) printf("空数!\n");
 else{
  Print_BSTree(T,0);
 }
 printf("创建树2:\n");
 for( ; ; )
 {
  printf("请输入一个整数(当输入为0时,将停止输入,第二棵二叉树创建结束):");
  scanf("%d",&e);
  if(e==0) break;
  taller=FALSE;
  InsertAVL(T2,e,taller);
  InsertAVL(T,e,taller);//将树2并到树1中
  Print_BSTree(T2,0);
 }
 printf("合并后的树:\n");//打印出合并后的树
 Print_BSTree(T,i);
 Destroy_BSTree(T);
 Destroy_BSTree(T2);
}