Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct pointer
- {
- int info;
- struct pointer *LPTR;
- struct pointer *RPTR;
- }pointer;
- int dem;
- void inorder(pointer*);
- pointer *search(pointer*,int);
- pointer *ins_node(pointer**,int);
- int del_node(pointer**,int);
- void creat_tree(pointer**,int);
- void del_tree(pointer**);
- pointer *first_even(pointer*);
- float avg_total(pointer*);
- int num_leaves(pointer*);
- int main()
- {
- pointer *T;
- int info,num;
- pointer *m;
- float s;
- printf("Tao cay nhi phan tim kiem gom 10 nut!\n");
- creat_tree(&T,10);
- inorder(T);
- printf("\n\n\n");
- printf("Tim mot nut co khoa cho truoc!\n");
- printf("Thong tin cua nut can tim la:");
- scanf("%d",&info);
- m=search(T,info);
- printf("\n\n\n");
- printf("Xoa nut!\n");
- if(del_node(&T,info)) printf("Nut da duoc xoa!\n");
- else printf("Chua xoa duoc nut!\n");
- inorder(T);
- printf("\n\n\n");
- printf("Xac dinh nut chan dau tien duyet theo thu tu giua!\n");
- m=first_even(T);
- if(m==NULL) printf("Khong co phan tu chan nao!\n");
- else
- {
- printf("Phan tu chan dau tien la:%d\n",m->info);
- }
- printf("\n\n\n");
- printf("Tinh trung binh cong cua cac phan tu duong!\n");
- dem=0;
- s=avg_total(T);
- if(s==0) printf("Khong co phan tu duong nao!\n");
- else printf("Ket qua:%g\n",s/dem);
- printf("\n\n\n");
- printf("Dem so nut la!\n");
- num=num_leaves(T);
- printf("Ket qua:%d\n",num);
- printf("\n\n\n");
- printf("Xoa cay!\n");
- del_tree(&T);
- if(T==NULL) printf("Cay da duoc xoa!\n");
- else printf("Cay chua duoc xoa!\n");
- return 1;
- }
- void inorder(pointer *p)
- {
- if(p->LPTR != NULL) inorder(p->LPTR);
- printf("%3d",p->info);
- if(p->RPTR != NULL) inorder(p->RPTR);
- }
- pointer *search(pointer *p,int info)
- {
- while(p!=NULL)
- {
- if(p->info == info) return p;
- else if(p->info < info) p=p->RPTR;
- else p=p->LPTR;
- }
- return p;
- }
- pointer *ins_node(pointer **p,int info)
- {
- pointer *m,*q;
- q=NULL;
- m=*p;
- while(m!=NULL)
- {
- if(m->info == info) return m;
- else if(m->info < info)
- {
- q=m;
- m=m->RPTR;
- }
- else
- {
- q=m;
- m=m->LPTR;
- }
- }
- m=(pointer*)malloc(sizeof(pointer));
- m->info = info;
- m->LPTR = m->RPTR = NULL;
- if(*p==NULL) *p=m;
- else if(q->info < info) q->RPTR = m;
- else q->LPTR = m;
- return m;
- }
- void creat_tree(pointer **p,int n)
- {
- int i,x;
- *p = NULL;
- if(n>0)
- {
- printf("Nhap thong tin cac nut!\n");
- for(i=1;i<=n;i++)
- {
- printf("Nut %d:",i);
- scanf("%d",&x);
- if(search(*p,x)==NULL) ins_node(p,x);
- }
- }
- }
- int del_node(pointer **p,int info)
- {
- pointer *a,*b,*c,*d;
- if(*p==NULL) return -1;
- else
- {
- a=*p;
- b=NULL;
- while(a!=NULL)
- {
- if(info==a->info) break;
- else if(info>a->info)
- {
- b=a;
- a=a->RPTR;
- }
- else
- {
- b=a;
- a=a->LPTR;
- }
- }
- if(a==NULL) return 0;
- else
- {
- if((*p)->LPTR==(*p)->RPTR)
- {
- free(*p);
- *p=NULL;
- return 1;
- }
- else
- {
- if(a->LPTR==NULL)
- {
- if(b!=NULL)
- {
- if(info < b->info) b->LPTR=a->RPTR;
- else b->RPTR=a->RPTR;
- }
- else *p=a->RPTR;
- }
- else if(a->RPTR==NULL)
- {
- if(b!=NULL)
- {
- if(info < b->info) b->LPTR=a->LPTR;
- else b->RPTR=a->LPTR;
- }
- else *p=a->LPTR;
- }
- else
- {
- d=a;
- c=a->LPTR;
- while(c->RPTR!=NULL)
- {
- d=c;
- c=c->RPTR;
- }
- if(c->info > d->info)d->RPTR=c->LPTR;
- else d->LPTR = c->LPTR;
- if(b!=NULL)
- {
- if(info < b->info) b->LPTR=c;
- else b->RPTR=c;
- }
- else *p=c;
- c->RPTR=a->RPTR;
- c->LPTR=a->LPTR;
- }
- free(a);
- return 1;
- }
- }
- }
- }
- void del_tree(pointer **p)
- {
- while(*p!=NULL)
- {
- del_node(p,(*p)->info);
- }
- }
- pointer *first_even(pointer *p)
- {
- pointer *l;
- if(p==NULL) return NULL;
- else
- {
- if(p->LPTR != NULL)
- {
- l=first_even(p->LPTR);
- if(l!=NULL) return l;
- }
- if(p->info%2==0) return p;
- if(p->RPTR != NULL) return first_even(p->RPTR);
- }
- return NULL;
- }
- float avg_total(pointer *p)
- {
- float s=0;
- if(p!=NULL)
- {
- if(p->LPTR != NULL) s+=avg_total(p->LPTR);
- if(p->info>0)
- {
- s+=p->info;
- dem++;
- }
- if(p->RPTR != NULL) s+=avg_total(p->RPTR);
- }
- return s;
- }
- int num_leaves(pointer *p)
- {
- int d=0;
- if(p!=NULL)
- {
- if(p->LPTR != NULL) d=num_leaves(p->LPTR);
- if(p->LPTR == p->RPTR) d++;
- if(p->RPTR != NULL) d+=num_leaves(p->RPTR);
- }
- return d;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement