bst bbt.c

数 据 结 构 大型 作业3.1输入一个数列L

struct bnode *LeftBalance(struct bnode *T)                 /* 对以*T为根的二叉树作左平衡旋转处理 */
{ struct bnode *lc,*rd; 
  lc=(struct bnode *)malloc(LENG1);
  lc=T->lchild;
  switch(lc->bf)                                          /* 检查*T的左子树的平衡度，再作相应处理 */
  { case LH:(T->bf)=EH;(lc->bf)=EH;T=R_Rotate(T);break;  /* 新结点插入*T的左孩子的左子树上，做右旋处理 */
    case RH:                                               /* 新结点插入*T的左孩子的右子树上，做双旋处理 */
         rd=lc->rchild;
         switch(rd->bf)                                   /* 修改*T及其左小孩的平衡因子 */
         { case LH:(T->bf)=RH;(lc->bf)=EH; break;
           case EH:(T->bf)=EH;(lc->bf)=EH; break; 
           case RH:(T->bf)=EH;(lc->bf)=LH; break;
         }
        (rd->bf)=EH;
        T->lchild=L_Rotate(T->lchild);                     /* 对*T的左子树作左旋平衡处理 */
        T=R_Rotate(T);                                     /* 对*T作右旋处理 */
  }
 return T;
}

struct bnode *RightBalance(struct bnode *T)                /* 对以*T为根的二叉树作右平衡旋转处理 */
{ struct bnode *lc,*rd;
  lc=(struct bnode *)malloc(LENG1);
  rd=(struct bnode *)malloc(LENG1);
  rd=T->rchild;
  switch(rd->bf)                                          /* 检查*T的右子树的平衡度，再作相应处理 */
 {  case RH:(T->bf)=EH;(rd->bf)=EH;T=L_Rotate(T);break;  /* 新结点插入*T的右孩子的右子树上，做左旋处理 */
    case LH:                                               /* 新结点插入*T的右孩子的左子树上，做右旋处理 */
         lc=rd->lchild;
         switch(lc->bf)
         { case LH:(T->bf)=EH;(rd->bf)=RH; break;
           case EH:(T->bf)=EH;(rd->bf)=EH; break;         
           case RH:(T->bf)=LH;(rd->bf)=EH; break;
         }
         (lc->bf)=EH;
         T->rchild=R_Rotate(T->rchild);                    /* 对*T的右子树作右旋平衡处理 */
         T=L_Rotate(T);                                    /* 对*T作左旋处理 */
 }
 return T;
}

struct bnode *InsertAVL(struct bnode *T,int e,int *taller,int *G)   /* 生成平衡二叉排序树 */
{ if(!T)                                                            /* 插入新结点，树“长高”，taller置为1 */
    { T=(struct bnode *)malloc(LENG1);
      T->data=e;
      T->lchild=NULL;T->rchild=NULL;(T->bf)=EH;(*taller)=1;
    }
  else
   {  if(e==T->data)                                      /* 树中存在和e有相同关键字的结点 */
      { (*taller)=0;(*G)=0;return T;                      /* 则不插入 */
      }
     if(e<T->data)                                        /* 在左子树搜索 */
       { T->lchild=InsertAVL(T->lchild,e,taller,G);
        if(!(*G)) return T;                               /* 未插入 */
        if(*taller)
         { 
           switch(T->bf)                                 /* 检查*T的平衡度 */
           { case LH:T=LeftBalance(T);(*taller)=0;break;  /* 原来左子树比右子树高，作左平衡处理 */
             case EH:(T->bf)=LH;(*taller)=1;break;       /* 原来左，右子树等高，树增高 */
             case RH:(T->bf)=EH;(*taller)=0;break;       /* 原来右子树比左子树高，现左，右子树等高 */
           }
         }
      }
    else                                                  /* 在右子树搜索 */
     {T->rchild=InsertAVL(T->rchild,e,taller,G);
      if(!(*G)) return T;                                 /* 未插入 */
       if((*taller))
       switch(T->bf)                                     /* 检查*T的平衡度 */
       {  case LH:(T->bf)=EH;(*taller)=0;break;          /* 原来左子树比右子树高，现左，右子树等高 */
          case EH:(T->bf)=RH;(*taller)=1;break;          /* 原来左，右子树等高，树增高 */
          case RH:T=RightBalance(T);(*taller)=0;break;    /* 原来右子树比左子树高，作右平衡处理 */
       }
     }
  }
  (*G)=1;
  return T;
}
/* *******************  第5问  **************************** */


void main()
{ struct bnode *root,*t,*root_AVL;
  int flag=0,d,k,S[N],i=-1,j,*nu,w,y,*num,u,*taller,B=0,C=0,D=0,E,*G;
  t=(struct bnode *)malloc(LENG1);
  G=&E;
  (*G)=0;
  nu=&B;                                             
  taller=&B;
  root=NULL;
  t=NULL;
  root_AVL=NULL;
 printf("input an array of int end of ENTER:");        /* 输入一列数 */
do
 { scanf("%d",&d);                                     /* 逐一读入数 */
  flag=0;
  if(i>0)                                        
  {for(j=0;j<=i;j++)                                   /* 判断结点是否相同，相同则不输入 */
    { if(d==S[j])
      {flag=1;break;} 
    }
  } 
    if(!flag)
    {i++;                                              /* i标记节点数 */
    S[i]=d;                                            /* 将结点存入数组 */  
    root=creat_tree(root,d);                           /* 生成一棵二叉排序树 */
   }
 }
while(getchar()!='\n');                                /* 结束标志 */
    printf("Inorder of the Binary Sort Tree:");
    inorder(root);                                     /* 中序遍历二叉树 */                          
    printf("\n");
    ASL(root,S,i);                                      /* 求二叉排序树的平均查找长度*/
    printf("Press any key to continue\n");
    getch(); 

/* *************      第4问         ***************** */
 printf("Make sure whether the BSTree is a BBTree:");
 for(j=0;j<=i;j++)                                     /* 判断二叉排序树T是否为平衡二叉树 */                
 { t=root;
   { while(S[j]!=t->data)                              /* 找到各结点 */
      {  if(S[j]<t->data)                             
         t=t->lchild;
        else t=t->rchild;
      }
     B=0;
     preorder1(t->lchild,nu);                          /* 求出以t->lchild为根二叉树结点个数 */
     C=depth(t->lchild,nu);                            /* 求出以t->lchild为根二叉树深度 */                        
     B=0;
     preorder1(t->rchild,nu);                          /* 求出以t->rchild为根二叉树结点个数 */
     D=depth(t->rchild,nu);                            /* 求出以t->rchild为根二叉树深度 */ 
     if((C-D)>1||(C-D)<-1)                             /* 左，右子树深度相差大于1，则为非平衡二叉树，输出NO!*/
      { printf("NO!\n");
        break;
      }
   }
  if(j==i) printf("OK!\n");                            /* 否则为平衡二叉树，输出OK!*/                             
 }
 printf("Press any key to continue\n");
 getch();  

/* **************     第4问        ****************** */


/* *********************第5,6问****************************** */
  B=0;
  for(j=0;j<=i;j++)                                    /* 生成平衡的二叉排序树 */   
  {root_AVL=InsertAVL(root_AVL,S[j],taller,G);      
  }
  printf("Preorder The Balanced Binary Tree:");
  preorder2(root_AVL);                                 /* 先序遍历二叉树 */ 
  printf("\nInorder The Balanced  Binary Tree:");        
  inorder(root_AVL);                                   /* 中序遍历二叉树 */ 
  printf("\n");
  ASL(root_AVL,S,i);                                   /* 求二叉排序树root_AVL的平均查找长度 */                                
  printf("Press any key to return\n");
  getch();
}

/* *********************第5,6问****************************** */