zfqzuoye.c

数据结构中关于树、栈、队列等数据结构的一些算法的C语言实现

#include<stdlib.h>
#include<stdio.h>
#include<math.h>
typedef struct Bnode
{ int data;
  struct Bnode *llink, *rlink;
     }Bnode;
extern int asl=0;
extern int flag=0;
extern int k=0;
main()                /*主函数*/
{ int a;
  int j=0;
  int n,b;
  int x,y;
  Bnode *t=NULL;
  printf("please input the date you want to use to create a tree end of with 0:\n");


  createbiordertree(&t);
  inorderprint(t);
  printf("\n");
  opporderprint(t);
  printf("\n");
  printf("please input the data you want to search:\n");
  scanf("%d",&x);
  search(t,x);
  y=depth(t);
  printf("\nThe depth of the tree is    %d",y);
  judge(t,flag);
  if(flag==1)
    printf("\nIt is not a AVL tree!\n");
  else if(flag==0)
    printf("\nIt is  a AVL tree!\n");
  calASL(t);
  a=asl;
  printf("ASL=%f\n",(float)a/k);
  getch();


}

int depth(Bnode *r)    /*计算以r为根结点的树的深度*/
{ int hl,hr;
  if(r==NULL)
    return 0;
  else
   { hl=depth(r->llink);
     hr=depth(r->rlink);
     if(hl>hr)
       return hl+1;
     else
       return hr+1;
     }
}
judge(Bnode *r)          /*判断是否为平衡二叉树*/
    {extern int flag;
     if(r!=NULL)
        {
         if(abs(depth(r->llink)-depth(r->rlink))>1)
               {
            flag=1;
            return;
               }
         judge(r->llink);
         judge(r->rlink);
        }
    }
inorderprint(Bnode* r)       /*中序遍历二叉树*/
{if(r!=NULL)
   {inorderprint(r->llink);
    printf("%d\t",r->data);
    inorderprint(r->rlink);
    }
}

opporderprint(Bnode* r)       /*逆中序遍历二叉树*/
{if(r!=NULL)
   {opporderprint(r->rlink);
    printf("%d\t",r->data);
    opporderprint(r->llink);
    }
}
search(Bnode *r,int x)      /*查找是否存在值为x的结点*/
{Bnode *f,*p;
 p=r;
 while(p&&p->data!=x)
  {if (p->data>x)
     {f=p;
      p=p->llink;
      }
   else
     {f=p;
      p=p->rlink;
      }
   }
 if(p==NULL)
  printf("\nthe data is not exit!\n");
 else
  printf("found it\n");

}

void creatree(int data,Bnode **root)  /*生成排序二叉树*/
    {
     if(*root==NULL)
        {
     *root=(Bnode *)malloc(sizeof(Bnode));
         (*root)->rlink=(*root)->llink=NULL;
         (*root)->data=data;
         return;
        }
     if((*root)->data<data)
        creatree(data,&((*root)->rlink));
     else
        creatree(data,&((*root)->llink));
    }
createbiordertree(Bnode **root)
    {extern int k;
     int data;
     scanf("%d",&data);
     while(data!=0)
        {
         creatree(data,root);
         scanf("%d",&data);
         k++;
        }
    }
int calASL(Bnode *r)          /*计算平均查找长度asl*/
{ extern int asl;
  if(r!=NULL)
    { calASL(r->llink);
      asl+=depth(r);
      calASL(r->rlink);
      }
}