正文

二叉排序树与平衡树算法实现及演示2006-05-11 21:05:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/wojiele/13926.html

分享到:

这个程序是我学数据结构时候,老师说让我做个演示程序时候做的一个最初版本程序。当然这不是教给老师的演示程序版本,演示版本的算法是套用书上的,这版本算法是我自己写的,所以我不能保证它没BUG(PS:在删除平衡树节点时候,由于我采用不同于书上的删除策略,所以后面演示程序可能不会象想象中那样旋转)。下面我给出程序中主要的算法及功能模块函数概要说明,最后附上源代码。

算法1:平衡树创建
说明:1,输入数列以整数零结束;2,平衡树HEAD初始化为空树
(1) 从输入数列接收一个DATA
(2) IF DATA!=0 THEN DATA转化成NODE
ELSE 返回
(3) 将NODE插入平衡树HEAD中
(4) 转到(1)继续实行

算法2:平衡树中插入的实现
说明:作左旋转和作右旋转的同时,相关节点的BF均置0。
(1)从调用函数中接收一个节点NODE
(2)IF HEAD=NULL THEN 将NODE节点直接插入平衡树HEAD
转到(6);
(3)IF HEAD>NODE
THEN 将NODE节点插入HEAD->LCHILD平衡树
转到(4);
ELSE IF HEAD<NODE
THEN 将NODE节点插入HEAD->RCHILD平衡树
转到(4);
ELSE 转到(6)
(4) 计算HEAD根节点平衡因子BF0
(5) IF –2<BF0<2 THEN 转到(6)
ELSE IF HEAD根节点BF==2
THEN IF HEAD左子树根节点BF==1 THEN 右旋转
ELSE (说明左子树根节点BF==-1)
做先左后右旋转,修改相关节点BF;
ELSE IF HEAD根节点BF==-2
THEN IF HEAD右子树根节点BF==-1 THEN 左旋转
ELSE (说明右子树根节点BF==1)
作先右后左旋转,修改相关节点BF
(6)返回


功能模块概要说明:
1,创建二叉排序树 Insert(BNODE **head),InitBST(int *p)
2,打印二叉排序数 PrintData(BNODE*p),PrintBF(BNODE*p) ,PrintBST(BNODE*head,int(*p)(BNODE*))
3, 统计节点个数 CountNodes(BNODE*head)
4, 查找 SearchBT(BNODE*head,int e)
5,求查找长度 DemoNSL(BNODE*head) Mtravel(BNODE*head) ,CountASL(BNODE *head)
6,求深度 DepthBT(BNODE *head)
7,求平衡因子 QuestNodeBF(BNODE*temp)QuestBF(BNODE*head)
8, 判断平衡树 IsAVL(BNODE*head)
9, 二叉排序数删除 DelHeadBST(BNODE**head) DelNodeBST(BNODE**head,BNODE*p) DelInBST(BNODE **head)
10,平衡树RightRotate(BNODE**head) LeftRotate(BNODE*head)
InitAVL(int *p) PrintAVL(BNODE*) DInsertAVL(BNODE**head)
11, 演示操作 (余下)


/*

功能:二叉排序树与平衡树算法实现及演示

作者:周志明

日期:2/2005

*/

#include<graphics.h>
#include <stdio.h>
#define OK    1
#define FALSE 0
#define NULL    0


#define ESC     0x011b
#define TAB 0x0f09
#define ENTER   0x1c0d
#define UP 0x4800
#define DOWN 0x5000
#define LEFT 0x4b00
#define RIGHT 0x4d00
#define BACKSPACE 0x0e08
#define SPACE   0x3920


typedef struct node{
   int data;
   int x,y,bf;
   struct node *lchild,*rchild;
   }BNODE;

typedef struct bst{
   BNODE *head;
   int  nodes,depth,asl;
   int  avl;   /*flag for AVL*/
   }BST;

typedef struct Queue{
   BNODE *pe;
   int x,y;
}QUEUE;


int InsertBST(BNODE **pp,BNODE *e){
    if(*pp==NULL){ *pp=e; return OK;}
    if(e->data==(*pp)->data) return OK;
    if(e->data>(*pp)->data)  InsertBST(&(*pp)->rchild,e);
    else InsertBST(&(*pp)->lchild,e);
    return OK;
}/*Insert*/


BNODE *InitBST(int *p){
   BNODE *temp=NULL,*head=NULL;

   if(*p==0){ printf("\nEmptyTree!"); return NULL; }
   do{
      temp=(BNODE *)malloc(sizeof(BNODE));
      if(!temp) printf("OutOfError!");
      temp->data=*p++;
      temp->x=temp->y=0;
      temp->lchild=temp->rchild=NULL;
      temp->bf=0;
      InsertBST(&head,temp);
   }while(*p);
   printf("\nHaveCreatedBST");
   return head;
}/*Initbbst*/

int PrintData(BNODE *p){
    printf("%5d",p->data);
}/*PrintData*/

int PrintBF(BNODE *p){
    printf("%4d(%3d)",p->data,p->bf);
}/*PrintBF*/

int PrintBST(BNODE *head,int (*p)(BNODE*)){
   if(!head) return OK;
   PrintBST(head->lchild,p);
   (*p)(head);
   PrintBST(head->rchild,p);
   return OK;
}/*Print*/

int CountNodes(BNODE *head){
   int n=1;
   if(!head) return 0;
   if(head->lchild) n+=CountNodes(head->lchild);
   if(head->rchild) n+=CountNodes(head->rchild);
   return n;
}/*CountNodes*/

BNODE* SearchBT(BNODE *head,int e){
   if(!head) return NULL;
   if(head->data==e) return head;
   else if(head->data>e) SearchBT(head->lchild,e);
   else SearchBT(head->rchild,e);
}/*SearchBT*/


int NodeSL(BNODE *head,int e){
   int n=0;
   if(head->data==e) return 1;
   else if(head->lchild && e<head->data) n+=NodeSL(head->lchild,e)+1;
   else if(head->rchild && e>head->data) n+=NodeSL(head->rchild,e)+1;
   return n;
}/*NodeSL*/


int DemoNSL(BNODE *head){
   int temp;
   printf("\nDemoNodeSearchLength:\n");
   do{ printf("\t\t|__Scanf a sort number:");
   scanf("%d",&temp);
       if(temp && SearchBT(head,temp)) printf("\t\t   |__NodeSortLength:%d\n",NodeSL(head,temp));
      }while(temp);
}/*DemoNSL*/

int *MTravel(BNODE *head){
   static int nodes[5000];
   static int *p=nodes;
   if(!head) return NULL;
   MTravel(head->lchild);
   *p++=head->data;
   MTravel(head->rchild);
   return p;
}/*MTravel*/

float CountASL(BNODE *head){
   int i,sum=0,n=0,*p;
   if(!head){ printf("EmptyTree "); return 0; }
   p=MTravel(head);
   n=CountNodes(head);
   p=p-n;
   for(i=0;i<n;i++){
     sum+=NodeSL(head,p[i]);
     p[i]=0;  /*clear*/
     }
   return (float)sum/n;
}/*CountASL*/

int DepthBT(BNODE *head){
   int a,b;
   if(!head) return 0;
   a=DepthBT(head->lchild);
   b=DepthBT(head->rchild);
   return a>b?a+1:b+1;
}/*DepthBT*/

int QuestNodeBF(BNODE *temp){
    temp->bf=DepthBT(temp->lchild)-DepthBT(temp->rchild);
}/*QuestNodeBF*/

int QuestBF(BNODE *head){
   if(!head) return FALSE;
   QuestNodeBF(head);
   QuestBF(head->lchild);
   QuestBF(head->rchild);
   return OK;
}/*QuestBF*/

int IsAVL(BNODE *head){
   int a,b;
   static int flag1,flag2;
   flag1=flag2=1;
   if(!head) return OK;
   a=DepthBT(head->lchild);
   b=DepthBT(head->rchild);
   if(a-b>=2||a-b<=-2)  return FALSE;
   else{ flag1=IsAVL(head->lchild);
  flag2=IsAVL(head->rchild);
  }
   if(flag1 && flag2) return OK;
}/*IsAVL*/

int RightRotate(BNODE **head){
   BNODE *lboot=(*head)->lchild;
   (*head)->lchild=(*head)->lchild->rchild;
   lboot->rchild=*head;
   *head=lboot;
   (*head)->bf=(*head)->rchild->bf=0;
}/*RightRotate*/

int LeftRotate(BNODE **head){
   BNODE *rboot=(*head)->rchild;
   (*head)->rchild=(*head)->rchild->lchild;
   rboot->lchild=*head;
   *head=rboot;
   (*head)->bf=(*head)->lchild->bf=0;
}/*LeftRotate*/

int InsertAVL(BNODE** head,BNODE *p){
    int a,b;
    if(*head==NULL){ *head=p;(*head)->bf=0;return OK;}
    if((*head)->data==p->data) return OK;
    if((*head)->data > p->data){
       InsertAVL(&(*head)->lchild,p);
       a=DepthBT((*head)->lchild); b=DepthBT((*head)->rchild);
       (*head)->bf=a-b;
       if((*head)->bf>-2 && (*head)->bf<2) return OK;
 /** (*head)->bf==2 **/
       if((*head)->lchild->bf==1) RightRotate(head);
       if((*head)->lchild->bf==-1)
    { LeftRotate(&(*head)->lchild); RightRotate(head);
      QuestNodeBF((*head)->lchild); QuestNodeBF((*head)->rchild);
    }
    }/*if*/
    else{ InsertAVL(&(*head)->rchild,p);
       a=DepthBT((*head)->lchild); b=DepthBT((*head)->rchild);
       (*head)->bf=a-b;
       if((*head)->bf>-2 && (*head)->bf<2) return OK;
       /** (*head)->bf==-2**/
       if((*head)->rchild->bf==-1) LeftRotate(head);
       if((*head)->rchild->bf==1)
    { RightRotate(&(*head)->rchild); LeftRotate(head);
      QuestNodeBF((*head)->lchild); QuestNodeBF((*head)->rchild);
    }
    }/*else*/
}/*InsertAVL*/

BNODE* InitAVL(int *p){
    BNODE *head=NULL,*temp;
    if(*p==0) return NULL;
    do{ temp=(BNODE*)malloc(sizeof(BNODE));
 if(temp){temp->data=*p++;temp->lchild=temp->rchild=NULL;}
 InsertAVL(&head,temp);
      }while(*p);
    return head;
}/*InitAVL*/

int PrintAVL(BNODE *head,int flag){
   if(!head) return OK;
   if(flag==1) printf("%d ",head->data);
   PrintAVL(head->lchild,flag);
   if(flag==2) printf("%d ",head->data);
   PrintAVL(head->rchild,flag);
   if(flag==3) printf("%d ",head->data);
   return OK;
}/*PrintAVL*/


int DInsertAVL(BNODE **head){
    BNODE *temp=NULL;
    int e;
    printf("\n\n******Demo Insert A Number To AVL******");
    printf("\n|__Scanf A Intager Number:");
 scanf("%d",&e);
    while(e){ temp=(BNODE*)malloc(sizeof(BNODE));
 if(temp){temp->data=e;temp->lchild=temp->rchild=NULL;}
 InsertAVL(head,temp);
 printf("\nFirstTravel:"); PrintAVL(*head,1);
 printf("\nMiddleTravel:"); PrintAVL(*head,2);
 printf("\nQuestBalanceFactors:"); PrintBST(*head,PrintBF);
 printf("\nQuestBF_______CHEAK:");QuestBF(*head);PrintBST(*head,PrintBF);
 printf("\n|__Insert A Intager Number:");
     scanf("%d",&e);
      }/*while*/
}/*InsertAVL*/

BNODE* DelHeadBST(BNODE **head){
   BNODE *temp=*head,*pro=NULL,*p=NULL;
   if(!(*head)) return NULL;
   if(!(*head)->lchild && !(*head)->rchild){  *head=NULL;
   temp->lchild=temp->rchild=NULL; return (temp);}
   if(!(*head)->rchild) *head=(*head)->lchild;
   else if(!(*head)->lchild) *head=(*head)->rchild;
   else{ p=(*head)->rchild;
      if(!p->lchild){ p->lchild=(*head)->lchild; *head=p;}
      else{
    while(p->lchild){pro=p; p=p->lchild;}
    if(!p->rchild)  pro->lchild=NULL;
    else pro->lchild=p->rchild;
    p->lchild=(*head)->lchild;p->rchild=(*head)->rchild;
    *head=p;
    }/*else*/
 }/*else*/
   temp->lchild=temp->rchild=NULL; return (temp);
}/*DelHeadBST*/

int DelNodeBST(BNODE **head,BNODE *pe){
   if(*head==NULL) return FALSE;
   if((*head)->data==pe->data) DelHeadBST(head);
   else if((*head)->data>pe->data) DelNodeBST(&(*head)->lchild,pe);
   else DelNodeBST(&(*head)->rchild,pe);
   return OK;
}/*DelNodeBST*/

int DelInBST(BNODE **head){
   int e;
   BNODE *temp;
   printf("\nDel A Int Number:");
       scanf("%d",&e);
   while(e){
       temp=(BNODE *)malloc(sizeof(BNODE));
       if(temp){temp->data=e;temp->lchild=temp->rchild=NULL;}
       DelNodeBST(head,temp);
       printf("\nCHEAK:");PrintBST(*head,PrintBF);
       printf("\nDel A Int Number:");
       scanf("%d",&e);
       }
}/*DelInBST*/


/********************************************************************************/

void SETGRAPH(){     /*图形模式初始化*/
   int driver,mode;
   detectgraph(&driver,&mode);
   initgraph(&driver,&mode,"");
   }

int BackGround(char *array){
   cleardevice();
   setbkcolor(1);
   setfillstyle(1,2); setcolor(14);
   bar3d(0,10,165,50,0,1);
   settextstyle(0,0,1); setcolor(4);
   outtextxy(0,25,array);
}/*BackGround*/

int InToChar(int e,char *p){
   char temp[10];
   char *t=temp;
   while(e){
    *t=e%10+48;
    e=e/10; t++;
    }
   while(t!=temp)
      *p++=*(--t);
   *p='\0';
}/*InToChar*/

int PainNode(int x,int y,int flag,BNODE *head,BNODE *pe,QUEUE *queue,int fontcolor,int fillcolor){
   int temp=1,lx=x,ly=y;
   char array[10];
   setfillstyle(1,fillcolor);setcolor(fillcolor);
     temp=NodeSL(head,pe->data);
     switch(temp){
     case 1: break;
     case 2: if(flag==1){x-=120;y+=80;}
      else if(flag==2){ x+=120;y+=80;}
      break;
     case 3: if(flag==1){ x-=60;y+=80;}
      else if(flag==2){ x+=60;y+=80;}
      break;
     case 4: if(flag==1){ x-=30;y+=80;}
      else if(flag==2){ x+=30;y+=80;}
      break;
     case 5: if(flag==1){ x-=15;y+=80;}
      if(flag==2){ x+=15;y+=80;}
      break;
     }
   sector(x,y,0,360,15,15); line(lx,ly,x,y);
   pe->x=x;pe->y=y;
   queue->x=x,queue->y=y;
   settextstyle(0,0,1); setcolor(fontcolor);
     InToChar(pe->data,array);
     outtextxy(x-5,y,array);
     if(!pe->bf){array[0]='0',array[1]='\0';}
     else if(pe->bf<0){array[0]='-';array[1]=-pe->bf+'0';array[2]='\0';}
     else {array[0]=pe->bf+'0';array[1]='\0';}
     outtextxy(x,y-10,array);
}/*PainNode*/

BNODE* SearchFatherBST(BNODE *head,BNODE *pe){
   BNODE *pro=NULL;
   if(!head) return NULL;
   if(head->data==pe->data) return NULL;
   if((head->lchild->data==pe->data)||(head->rchild->data==pe->data)) return  head;
   else if(head->data>pe->data) pro=SearchFatherBST(head->lchild,pe);
   else pro=SearchFatherBST(head->rchild,pe);
   return pro;
}/*SearchBT*/

QUEUE* QuestFather(QUEUE *qhead,BNODE *head,BNODE *pe){
    BNODE *temp=NULL;
    temp=SearchFatherBST(head,pe);
    while(temp->data!=qhead->pe->data) qhead++;
    return qhead;
}/*QUEUE*/

int PainTree(int x,int y,BNODE *head,int fontcolor,int fillcolor){
    QUEUE boot[100],*father=NULL;
    BNODE *temp=head;
    int i=x,j=y,top=0,rear=0;
    if(!head) return OK;
    boot[top++].pe=temp;
    PainNode(i,j,0,head,head,&boot[0],fontcolor,fillcolor);
    rear++;
    do{
  if(temp->lchild){   boot[top].pe=temp->lchild;
     father=QuestFather(boot,head,boot[top].pe);
     PainNode(father->x,father->y,1,head,boot[top].pe,&boot[top],fontcolor,fillcolor);
   /*  PainNode(boot[top].pe->x,boot[top].pe->y,1,head,boot[top].pe,&boot[top]); */
   top++;   }
       if(temp->rchild){   boot[top].pe=temp->rchild;
   father=QuestFather(boot,head,boot[top].pe);
   PainNode(father->x,father->y,2,head,boot[top].pe,&boot[top],fontcolor,fillcolor);
   top++;   }
       temp=boot[rear++].pe;
    }while(top>=rear);
}/*PainTree*/


/***********************************  TEST    ***********************************************/

char* uscanf(sx,sy,max)  /*图形模式下输入函数*/
int sx,sy,max;
{
     int bsx=sx,bsy=sy,n;
     int key=0,keylow;
     char *p,*ch;

     settextstyle(0,0,2);
     ch=p=(char*)malloc(sizeof(char)*100);
     n=0;
     do{
 setcolor(RED);
 if(key!=BACKSPACE || sx<=bsx)
 line(sx,sy+15,sx+15,sy+15);
 key=bioskey(0);
 keylow=key & 0xff;
 if(key==BACKSPACE && sx>bsx){       /*退格纠错处理*/
      if(n!=max) sx-=15; p--;
      setfillstyle(1,1);setcolor(1);
      if(n==max) bar(sx,sy,sx+15,sy+16);
      else bar(sx,sy,sx+16,sy+16);
      n-=1;
      }
 else if(keylow>=48 && keylow<=57 || keylow=='-'
 /* || keylow>=65 && keylow<=90
      || keylow>=97 && keylow<=122 || key==SPACE*/)       /*输入字符控制*/
      if(n<max){
         sprintf(p,"%c",keylow);
         setfillstyle(1,1);setcolor(1);
      bar(sx,sy,sx+15,sy+16);
         setcolor(RED);
         moveto(sx,sy);  outtext(p);
         n+=1;
         p++;
         sx+=15;
         if(n==max) sx-=15;
         }
       }while(key!=ENTER && key!=TAB);
       *p='\0';
       setfillstyle(1,8); setcolor(8);
   bar(bsx,bsy,bsx+60,bsy+18);
       settextstyle(0,0,2);  setcolor(14);
   outtextxy(bsx,bsy,ch);
       settextstyle(0,0,1);  setcolor(14);
      return(ch);
}/*uscanf*/

int buttom(int x,int y,int fillcolor,int fontcolor,char *p){
    setfillstyle(1,fillcolor); setlinestyle(0,0,NORM_WIDTH);setcolor(fillcolor);
    bar3d(x,y,x+50,y+15,3,1);
    settextstyle(0,0,1);setcolor(fontcolor);
    outtextxy(x+2,y+2,p);
}/*buttom*/

int DemoCreatAVL(){
   char*p[3],*chp;
   int key,line=40,keyflag=1;
   BNODE *headavl=NULL;
   p[0]="Insert";p[1]="Delete";p[2]="exit";

   SETGRAPH();
   cleardevice();
   setbkcolor(1);
   setfillstyle(1,2); setcolor(14);
   bar3d(0,10,165,100,0,3);
   setfillstyle(1,2); setcolor(14);
   settextstyle(0,0,1); setcolor(4);
   outtextxy(0,15,"----DemoCreatAVL----");
   setfillstyle(1,8); setlinestyle(0,0,NORM_WIDTH);setcolor(7);
    bar3d(5,40,90,100,2,0);
    outtextxy(5,50,"ScanfNumber");
    buttom(100,40,1,14,*p);buttom(100,60,1,14,p[1]);buttom(100,80,1,14,p[2]);
    chp=uscanf(15,70,4);
    buttom(100,40,4,14,*p);
    do{ key=bioskey(0);
      switch(key){
  case LEFT:  buttom(100,40,1,14,p[0]);
       setfillstyle(1,8); setlinestyle(0,0,NORM_WIDTH);setcolor(7);
       bar3d(5,40,90,100,2,0);
       outtextxy(5,50,"ScanfNumber");
       buttom(100,40,1,14,*p);buttom(100,60,1,14,p[1]);buttom(100,80,1,14,p[2]);
       chp=uscanf(15,70,4);
       if(keyflag==1) buttom(100,40,4,14,*p);
       else if(keyflag==2) buttom(100,60,4,14,p[1]);
       break;
  case ENTER: switch(keyflag){
     case 1:DemoInsertAVL(&headavl,chp); break;
     case 2:DemoDelAVL(&headavl,chp);  break;
     case 3:exit(0);
       }
       break;
  case DOWN : if(line==40){ line=60;
       buttom(100,40,1,14,*p);buttom(100,60,4,14,p[1]);
       keyflag=2;break;}
       if(line==60){ line=80;
       buttom(100,60,1,14,p[1]);buttom(100,80,4,14,p[2]);
       keyflag=3;break;}
       break;
  case UP:    if(line==60){ line=40;
       buttom(100,60,1,14,p[1]);buttom(100,40,4,14,p[0]);
       keyflag=1;break;}
       if(line==80){ line=60;
       buttom(100,80,1,14,p[2]);buttom(100,60,4,14,p[1]);
       keyflag=2;break;}
       break;
  }/*switch*/
      }while(1);
    /*if(key==ENTER)    outtextxy(200,200,chp); */

}/*DemoCreatAVL*/

int CharToInt(char *p){
    int temp[10],i,sum=0;
    for(i=0;i<10;i++) temp[i]=-2;
    if(*p=='-'){
       temp[0]=-1;
       i=1;
       while(p[i]){ temp[i]=p[i]-'0'; i++; }
    }
    else{ temp[0]=1;i=0;
       while(p[i]){ temp[i+1]=p[i]-'0';i++;}
    }
    for(i=1;temp[i]!=-2;i++){
 sum=sum*10+temp[i];
 }
    sum*=temp[0];
    return sum;
}/*CharToInt*/

int DemoInsertAVL(BNODE **head,char *chp){
    BNODE *temp=NULL;
    int e;
    e=CharToInt(chp);
    if(e){ temp=(BNODE*)malloc(sizeof(BNODE));
 if(temp){temp->data=e;temp->lchild=temp->rchild=NULL;
   temp->x=temp->y=0;}
    InsertBST(head,temp); QuestBF(*head);
 PainTree(320,20,*head,14,8);
 getch();getch();
    PainTree(320,20,*head,1,1);DelNodeBST(head,temp);
    InsertAVL(head,temp);QuestBF(*head);
    PainTree(320,20,*head,14,8);
    }
}/*DemoInsertAVL*/

int* Transform(BNODE *head){
    QUEUE boot[100];
    BNODE *temp=head;
    int top=0,rear=0;
    int i,*inthead=NULL,*inttemp=NULL;

    inttemp=inthead=(int*)malloc(sizeof(int)*50);
    for(i=0;i<50;i++) inttemp[i]=0;
    inttemp=inthead;i=0;

    if(!head) return NULL;
    boot[top++].pe=temp;
    inttemp[i++]=temp->data;
    rear++;
    do{
       if(temp->lchild){ boot[top].pe=temp->lchild;
     inttemp[i++]=boot[top].pe->data;
     top++;   }
       if(temp->rchild){ boot[top].pe=temp->rchild;
     inttemp[i++]=boot[top].pe->data;
     top++;   }
       temp=boot[rear++].pe;
    }while(top>=rear);
    return inthead;
}/*Transform*/

int DemoDelAVL(BNODE **head,char *chp){
    BNODE *temp=NULL;
    int e;
    e=CharToInt(chp);
    if(!e) return 0;
    temp=(BNODE*)malloc(sizeof(BNODE));
    temp->data=e;temp->bf=0;temp->lchild=temp->rchild=NULL;
    PainTree(320,20,*head,1,1);
    DelNodeBST(head,temp); QuestBF(*head);
    PainTree(320,20,*head,14,8);
    getch();getch();
    PainTree(320,20,*head,1,1);
    *head=InitAVL(Transform(*head));
    QuestBF(*head);
    PainTree(320,20,*head,14,8);


}/**/
/******************************************************************************/


DemoMain(BNODE *head,char *array){
   SETGRAPH();
   BackGround(array);
   PainTree(320,20,head,14,8);
   getch();getch();
    cleardevice();
  /* closegraph();*/
}/*DemoMain*/


/********************************************************************************/
main(){
   int elem[500],i;
   int *p=elem,temp=0;
   clrscr();
   for(i=0;i<500;i++) elem[i]=0;
   printf("Input Numbers(end in '0'):");
   do{
     scanf("%d",p);
     temp=*p++;
     }while(temp);
   DemoMainBST(elem);
   DemoMainAVL(elem);

   DemoCreatAVL();
}/*main*/


int DemoMainBST(int *elem){
   BST BSTree;

   BSTree.head=InitBST(elem);
   printf("\nNodesNumber:%d",BSTree.nodes=CountNodes(BSTree.head));
   printf("\nTreeDepth:%d",BSTree.depth=DepthBT(BSTree.head));
   printf("\nMiddleTravel: ");
      PrintBST(BSTree.head,PrintData);
   DemoNSL(BSTree.head);
   printf("\nBinarySortTreeASL:");
      printf("%5.2f ",CountASL(BSTree.head));
   printf("\nQuestBalanceFactors:");
      QuestBF(BSTree.head);
      PrintBST(BSTree.head,PrintBF);
   printf("\nBinarySortTreeAVL:");
      BSTree.avl=IsAVL(BSTree.head);
      printf("--%s!",BSTree.avl?"YES":"NO");
   printf("\nDELET DEMO\n");
      DelInBST(&BSTree.head);

   DemoMain(BSTree.head,"BinarySortTree");
}/**/


int DemoMainAVL(int *elem){
 BNODE *AVLhead;
   printf("\n*******CreatBalanceBinaryTree");
      AVLhead=InitAVL(elem);
      printf("\nFirstTravel:");PrintAVL(AVLhead,1);
      printf("\nMiddleTravel:");PrintAVL(AVLhead,2);
      printf("\nQuestBalanceFactors:");
    PrintBST(AVLhead,PrintBF);
      DInsertAVL(&AVLhead);

   DemoMain(AVLhead,"BalanceBinarySortTree");

}/**/

阅读(5899) | 评论(5)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册