1.c

平衡二叉排序树的建立.增加和删除操作 平衡二叉排序树的建立.增加和删除操作

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
# define LH 1
# define EH 0
# define RH -1
# define TRUE 1
# define FALSE 0
# define MAX 20

int taller=0;  /*taller反映T长高与否*/
int shorter=0; /*shorter反映T变矮与否*/

typedef struct BSTNode
{   /*二叉排序树的类型定义*/
  int data;
  int bf;   /*结点的平衡因子*/
  struct BSTNode * lchild, * rchild;
}BSTNode, *BSTree;

BSTree R_Rotate(BSTree p)
{  /*对以p为根的二叉排序树作右旋处理，处理之p指向新的树根结点*/
  /*即旋转处理之前的左子树根结点*/
  BSTNode *lc;
  lc=p->lchild;
  p->lchild=lc->rchild;
  lc->rchild=p;p=lc;
  return p;
} /*R_Rotate*/

BSTree L_Rotate(BSTree p)
{   /*对以p为根的二叉排序树作左旋处理，处理之p指向新的树根结点*/
  /*即旋转处理之前的右子树根结点*/
  BSTNode *rc;
  rc=p->rchild;
  p->rchild=rc->lchild;
  rc->lchild=p;p=rc;
  return p;
}/*L_Rotate*/

BSTree LeftBalance(BSTree T)
{   /*对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时*/
   /*指针T指向新的根结点*/
  BSTNode *lc,*rd;
  lc=T->lchild;
  switch(lc->bf)
  {
     case LH: T->bf=lc->bf=EH;
       T=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;
       T->lchild=L_Rotate(T->lchild);
       T=R_Rotate(T);
  }
  return T;
}

BSTree RightBalance(BSTree T)
{   /*对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时*/
   /*指针T指向新的根结点*/
   BSTree rc,ld;
   rc=T->rchild;
   switch(rc->bf)
   {
      case RH:T->bf=rc->bf=EH;
       T=L_Rotate(T);
       break;
      case LH:ld=rc->lchild;
       switch(ld->bf)
       {
   case LH:T->bf=LH;
    rc->bf=EH;
    break;
   case EH:T->bf=rc->bf=EH;
    break;
   case RH:T->bf=EH;
    rc->bf=RH;
    break;
       }
       ld->bf=EH;
       T->rchild=R_Rotate(T->rchild);
       T=L_Rotate(T);
   }
   return T;
}

BSTree InsertAVL (BSTree T, int e)
{   /*若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入一个
    /*数据元素为e的新结点,并返回插入后所建成的平衡二叉排序树,否则返回
    /*NULL.若因插入而使二叉数失去平衡,则作平衡旋转处理,布尔变量taller
    /*反映T长高与否*/
   BSTree p;
   if(!T)
   {
      T=(BSTree)malloc(sizeof(BSTNode));
      T->data=e;
      T->lchild=T->rchild=NULL;
      T->bf=EH;
      taller=TRUE;
   }
   else
   {
      if(e==T->data)
      {
  taller=FALSE;
  return NULL;
      }
      if(e < T->data)
      {
  p=InsertAVL(T->lchild,e);
  if(p)
  {
     T->lchild=p;
     if(taller)
        switch(T->bf)
        {
    case LH:
     T=LeftBalance(T);
     taller=FALSE;
     break;
    case EH:
     T->bf=LH;
     taller=TRUE;
     break;
    case RH:
     T->bf=EH;
     taller=FALSE;
     break;
        }
  }
      }
      else
      {
  p=InsertAVL(T->rchild,e);
  if (p)
  {
     T->rchild=p;
     if(taller)
     {
        switch(T->bf)
        {
    case LH: T->bf=EH;
      taller=FALSE;
      break;
    case EH: T->bf=RH;
      taller=TRUE;
      break;
    case RH: T=RightBalance(T);
      taller=FALSE;
      break;
        }
     }
  }
      }
   }
   return T;
}

BSTree midorder(BSTree T)
{   /*树的中序遍历的递归算法*/
   if(T!=NULL)
   {
      midorder(T->lchild);
      printf("%d ",T->data);
      midorder(T->rchild);
   }
}

BSTree RightBalance1(BSTree p)
{   /*删除结点时对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时*/
   /*指针T指向新的根结点*/
   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;
      }
   }
   return p;
}

BSTree LeftBalance1(BSTree p)
{   /*删除结点时对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时*/
   /*指针T指向新的根结点*/
   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;
  }
   }
   return p;
}

BSTree Delete(BSTree q, BSTree r)
{   /*对结点进行删除处理*/
if(r->rchild==NULL)
{
                q->data=r->data;
  q=r;
  r=r->lchild;
  free(q);
  shorter=1;
}
else
{
  r->rchild=Delete(q,r->rchild);
  if(shorter==1)
   r=RightBalance1(r);
}
return r;
}

BSTree DeleteAVL(BSTree p, int e)
{   /*找到要删除的结点,并调用删除函数对其进行删除*/
BSTree q;
if(p==NULL)
  return NULL;
else if(e < p->data)
{
  p->lchild = DeleteAVL(p->lchild,e);
  if(shorter==1)
   p=LeftBalance1(p);
  return p;
}
else if(e > p->data)
{
  p->rchild=DeleteAVL(p->rchild,e);
  if(shorter==1)
   p=RightBalance1(p);
  return p;
}
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
  {
   q->lchild=Delete(q,q->lchild);
   if(shorter==1)
    q=LeftBalance1(q);
   p=q;
  }
}
return p;
}