bst bbt.c

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

/*                            数 据 结 构 大型 作业
              计算机0205班   刘三民   学号：012002013712
3.1输入一个数列L，生成一棵二叉排序树T；
3.2对二叉排序树T作中序遍历，输出结果；
3.3计算二叉排序树T的平均查找长度, 输出结果；
3.4判断二叉排序树T是否为平衡二叉树，输出信息“OK！”/“NO！”；
3.5再使用上述数列L，生成平衡的二叉排序树BT，每当插入新元素，发现当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平衡的二叉排序树BT；
3.6计算平衡的二叉排序树BT的平均查找长度，输出结果。
3.6分析对比未平衡化的二叉排序树和平衡的二叉排序树的查找效率(最好、最坏平均比较关键字数)
*/

#include<stdio.h>             
#include <stdlib.h>
struct bnode                                /* Bnode为二叉树结点(结构)类型 */
{int data;                                  /* data为整形类型 */
 int bf;                                   /* 节点的平衡因子 */
 struct bnode *lchild,*rchild;              /* 左小孩，右小孩为指针类型  */
};
struct qnode                                /* qnode为队列结点类型 */
{struct bnode *data;                        /* data为二叉树结点指针 */
 struct qnode *next;                        /* next指向下一队列结点 */
};
struct linkqueue
{struct qnode *front;                       /* 队头结点指针 */
 struct qnode *rear;                        /* 队尾结点指针 */
};
#define N    50                             /* 数组初始大小 */
#define LENG1 sizeof(struct bnode)          /* 节点所占空间 */   
#define LENG2 sizeof(struct qnode)
#define LENG3 sizeof(struct linkqueue)

#define LH +1
#define EH 0
#define RH -1

struct bnode *creat_tree(struct bnode *t,int x)  /* 生成一棵二叉排序树 */
{if(t==NULL)                                     /* 生成空二叉排序树 */
  { t=(struct bnode *)malloc(LENG1);             /* 分配空间 */
	t->data=x;
	t->lchild=t->rchild=NULL;                /* 左右小孩置为空 */
 } 
 else
  { if(x<t->data)                                /* x大于结点 */
	  t->lchild=creat_tree(t->lchild,x);     /* 访问左子树 */
   else
	  t->rchild=creat_tree(t->rchild,x);     /* 访问右子树 */
  }
return t;                                        /* 返回根节点 */
}

struct bnode *inorder(struct bnode *root)        /* 中序遍历 */
{if(root)
 {root->lchild=inorder(root->lchild);            /* 访问左小孩 */
 printf("%d  ",root->data);                       /* 打印结点 */
 root->rchild=inorder(root->rchild);             /* 访问右小孩  */
 }
 return root;
}

struct bnode *preorder1(struct bnode *root,int *nu)  /* 先序遍历二叉树 */
{
 if(root)                                            
 {
  (*nu)++;                                           /* 计算非空结点个数 */
 root->lchild=preorder1(root->lchild,nu);            /* 访问左小孩 */    
  root->rchild=preorder1(root->rchild,nu);           /* 访问右小孩 */
 }
 return root;
}

struct bnode *preorder2(struct bnode *root)          /* 先序遍历二叉树 */
{
 if(root)
 {printf("%d  ",root->data);
  root->lchild=preorder2(root->lchild);              /* 访问左小孩 */
  root->rchild=preorder2(root->rchild);              /* 访问右小孩 */
 }
 return root;
}

struct linkqueue *enqueue(struct linkqueue *q,struct bnode *e)   /* 队列中插入结点 */
{struct qnode *p;
 p=(struct qnode *)malloc(LENG2);                   /* 给结点分配空间 */
 p->data=e;
 p->next=NULL;
 q->rear->next=p;
 q->rear=p;
 return q;
}



int compare(struct bnode *t,int x,int *Q)     
{if(t) 
  {
    if(x<t->data)                                    /* x大于结点 */
	{ (*Q)++;
           compare(t->lchild,x,Q);                   /* 访问左子树 */
          return;  
        }  
   else
    { if(x>t->data)                                  /* x小于结点 */
	 { (*Q)++;
           compare(t->rchild,x,Q);                   /* 访问右子树 */
           return;
         }     
      else return;
    }
  }
 else return;
}

float ASL(struct bnode *root,int s[N],int i)      /* 求二叉排序树T的平均查找长度 */
{ int j,L=0,*Q,A;
  float  ASL=0;
  for(j=0;j<=i;j++)
 {A=1;
  Q=&A;                                         /* Q初始值为1 */
  compare(root,s[j],Q);                         /* 求各结点查找长度 */
  L+=(*Q);                                      /* L为所有结点查找长度之和 */
 } 
  ASL=((float)L)/(i+1);                         /* ASL为二叉排序树T的平均查找长度 */
  printf("ASL=%.2f\n",ASL);                     /* 打印ASL */      
  return ASL;
}   

int depth(struct bnode *root,int *nu)           /* 求以root为根结点的二叉树的深度*/
{int c=0,n=0,u,v=0; 
 struct bnode *no;                              /* 定义空结点no */              
  struct qnode *s;                              /* 定义结点s */
  struct linkqueue *q;                          /* 定义结点q */
  if(root)
  { no=(struct bnode *)malloc(LENG1);           /* 为no分配空间 */      
    s=(struct qnode *)malloc(LENG2);            /* 为s分配空间 */
    q=(struct linkqueue *)malloc(LENG3);        /* 为q分配空间 */
    no->lchild=NULL;                            /* no左小孩为空 */
     no->data=0;                                /* no->data为零 */
     no->rchild=NULL;                           /* no右小孩为空 */
    q->front=q->rear=(struct qnode *)malloc(LENG2);
    q->front->next=NULL;
    enqueue(q,root);                            /* 调用enqueue函数 */
    s=q->front->next;
  while(c<*nu)                                  /* *nu二叉树非零结点个数 */                                 
   { n++;                                       /* n为队列结点个数 */
     if(s->data->data!=0)  c++; 
     if(s->data->lchild)
     enqueue(q,s->data->lchild);                /* 左小孩插入队列 */                               
     else enqueue(q,no);                        /* 空结点插入队列 */
     if(s->data->rchild)
     enqueue(q,s->data->rchild);                /* 右小孩插入队列 */
     else enqueue(q,no);                        /* 空结点插入队列 */
     s=s->next;
   }
   u=n;
   while(u)
   {  u=u/2;
      v++;                                      /* v为深度 */                                         
   } 
  }
 return v;                                      /* 返回v */
}
/* **************** 第1，2，3，4问 ************************ */

struct bnode *R_Rotate(struct bnode *p)             /* 对以*p为根的二叉排序树作右旋处理 */
{ struct bnode *lc;
  lc=(struct bnode *)malloc(LENG1);
  lc=p->lchild;                                     /* lc指向p左子树根结点 */
  p->lchild=lc->rchild;                             /* lc的右子树挂接为P的左子树 */
  lc->rchild=p;
  p=lc;                                             /* p指向新的根结点 */
  return p;
}

struct bnode *L_Rotate(struct bnode *p)             /* 对以*p为根的二叉排序树作左旋处理 */
{ struct bnode *rc;
  rc=(struct bnode *)malloc(LENG1);
  rc=p->rchild;                                     /* lc指向p右子树根结点 */
  p->rchild=rc->lchild;                             /* lc的左子树挂接为P的右子树*/
  rc->lchild=p;
  p=rc;                                             /* p指向新的根结点 */
  return p; 
}