Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* Problem
- * viết c.tr
- * 1.tạo 1 cây tìm kiếm chứa số nguyên
- * 2.Tìm 1 nút nào đấy
- * 3.xóa 1 nút nào đó trên cây
- * 4.xóa hết
- * 5.xác định nút chẵn đầu tiên trong danh sách duyệt giữa
- * 6.tìm trung bình cộng của các phần tử duong
- * 7.đếm số nút lá
- * Ver 1.0
- * Nhap cac gtri tu file
- * Future: 2.0
- * Chinh lai gtri nhap vao TRUC TIEP: truong hop a, aa, a-4759234
- */
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct nod
- {
- int info;
- //int count;
- struct nod * Lptr;
- struct nod * Rptr;
- } Node_Type;
- Node_Type* Add(Node_Type*,int);
- Node_Type* Create_Node(int);
- void Traverse(Node_Type* );
- void Visit(Node_Type*);
- Node_Type* Find(Node_Type*, int);
- Node_Type* Find_R(Node_Type*,int);
- Node_Type* First_Even(Node_Type *);
- Node_Type* Create_Tree(Node_Type*,int);
- float Mean(Node_Type *);
- int Count_Leaf(Node_Type* );
- Node_Type* Delete_Node(Node_Type*,int);
- void Delete_Tree(Node_Type *p);
- Node_Type *T,*p,*r,*u,*k,*d;
- int f=0,cntr=0;
- float s=0;
- int main(int argc, char** argv)
- {
- T=NULL;
- r=NULL;
- char Choice, w[80];
- int x;
- int l=0;
- printf( "\nCHUONG TRINH MINH HOA CAY NHI PHAN"
- "\n Go aX de nhap so nguyen X."
- "\n-Go rX de xoa nut co noi dung X khoi cay"
- "\n-Go fX de tim kiem nut co noi dung X"
- "\n-Go D de xoa tat ca cac nut"
- "\n-Go P de in ra cay theo cach duyet giua"
- "\n-Go E de tim phan tu chan dau tien theo cach duyet giua"
- "\n-Go M de tinh trung binh cong cac phan tu duong"
- "\n Go L de dem so nut la"
- "\n-Go ! de thoat khoi chuong trinh\n");
- while(1)
- {
- Choice=0;
- x=0;//phai init x=0 vi ham sscanf lay 2 args, truong hop ta khong dien gtri cho x (dien P de in) thi x van thoa man dk cua if(x!=0)
- fflush(stdin);
- printf("Nhap: ");
- sscanf(gets(w),"%c %d",&Choice,&x);
- if((x>=(-32768))&&(x<=32767))//g.han kieu int
- {
- switch (Choice)
- {
- case 'a':
- T = Add(T,x);
- break;
- case 'P':
- if(T==NULL)
- printf("Cay rong\n\n");
- else
- {
- Traverse(T);
- printf("\n\n");
- }
- break;
- case 'f':
- p=Find(T,x);
- if(p!=NULL)
- printf("Tim thay nut %d trong cay\n\n",x);
- else
- printf("KHONG tim thay nut %d trong cay\n\n",x);
- break;
- case 'd':
- d=Find_R(T,x);
- printf("Nut cha cua %d la %d\n",x,d->info);
- break;
- case 'r':
- r=Find(T,x);
- if(r==NULL)
- printf("Khong tim thay so %d trong cay\n\n",x);
- else
- {r=Delete_Node(T,x);
- if(r==NULL)
- {
- T=(Node_Type *)malloc(sizeof(Node_Type));
- T=NULL;
- }}
- break;
- case 'D':
- if(T==NULL)
- printf("Cay rong, khong the xoa!\n\n");
- else
- {
- Delete_Tree(T);
- printf("Da xoa cay\n\n");
- T=(Node_Type *)malloc(sizeof(Node_Type));
- T=NULL;
- }
- break;
- case 'E':
- k=First_Even(T);
- if(k!=NULL)
- printf("Phan tu chan dau tien theo cach duyet giua la: %d\n\n",k->info);
- else
- printf("Cay khong co nut chan nao!\n\n");
- break;
- case 'L':
- l=Count_Leaf(T);
- printf("So nut la cua cay da cho la: %d\n\n",l);
- break;
- case 'M':
- s=0;
- cntr=0;
- s=Mean(T);
- printf("Trung binh cong cua cac phan tu duong la : %f\n\n",s/cntr);
- break;
- case '!':
- printf("\nChuong trinh ket thuc!");
- exit(1);
- }
- }
- }
- return 0;
- }
- Node_Type* Add(Node_Type* p,int x)
- {
- if(p==NULL)
- p=Create_Node(x);
- else
- {
- if(x<p->info)
- p->Lptr=Add(p->Lptr,x);
- else
- if(x>p->info)
- p->Rptr=Add(p->Rptr,x);
- else
- printf("Gia tri nhap vao da co trong cay. Nhap lai so khac!\n");
- }
- return p;
- }
- Node_Type* Create_Node(int x)
- {
- Node_Type *l;
- l=(Node_Type *)malloc(sizeof(Node_Type));
- l->info=x;
- l->Lptr=NULL;
- l->Rptr=NULL;
- printf("Da them %d vao cay nhi phan\n",x);
- return l;
- }
- void Traverse(Node_Type* pt)
- {
- if(pt!=NULL)
- {
- Traverse(pt->Lptr);
- Visit(pt);
- Traverse(pt->Rptr);
- }
- }
- void Visit(Node_Type* p)
- {
- printf("%d ",p->info);
- }
- Node_Type * Find(Node_Type *p, int x)
- {
- int i=0;
- while(p!=NULL)
- {
- if(x<p->info)
- {
- p=p->Lptr;
- }
- else
- if(x==p->info)
- {
- i++;
- return p;
- }
- else
- {
- p=p->Rptr;
- }
- }
- return p;
- }
- Node_Type* Find_R(Node_Type *p,int x)
- {
- int i=0;
- r=p;
- while(p!=NULL)
- {
- if(x<p->info)
- {
- r=p;
- p=p->Lptr;
- }
- else
- if(x==p->info)
- {
- i++;
- return r;
- }
- else
- {
- r=p;
- p=p->Rptr;
- }
- }
- return r;
- }
- Node_Type* Delete_Node(Node_Type *T,int x)
- {
- Node_Type *p,*temp,*nr;
- p=Find(T,x);
- r=Find_R(T,x);
- if(p==T)//Xoa Goc
- {
- if((p->Lptr==NULL)&&(r->Rptr==NULL))
- {
- r=NULL;
- printf("Da xoa nut %d\n",x);
- free(p);
- return r;
- }
- else if((p->Lptr!=NULL)&&(r->Rptr==NULL))//Goc chi co con trai
- {
- r=r->Lptr;
- T=r;
- printf("Da xoa nut %d\n",x);
- free(p);
- return r;
- }
- else if((p->Lptr==NULL)&&(r->Rptr!=NULL))
- {
- r=r->Rptr;
- T=r;
- printf("Da xoa nut %d\n",x);
- free(p);
- return r;
- }
- else if(p->Lptr!=NULL&&p->Rptr!=NULL)
- {
- nr=p->Rptr;
- r=p->Lptr;
- temp=nr;
- while(temp->Lptr!=NULL)
- temp=temp->Lptr;
- temp->Lptr=r;
- r=nr;
- T=nr;
- free(p);
- printf("Da xoa nut %d\n",x);
- return r;
- }
- }
- //P la nut la
- else if((p->Lptr==NULL)&&(r->Rptr==NULL))
- {
- printf("Da xoa la %d\n",p->info);
- if(r->Lptr==p)
- r->Lptr=NULL;
- if(r->Rptr==p)
- r->Rptr=NULL;
- r=T;
- free(p);
- return r;
- }
- //TH p chi co 1 con
- if(p->Lptr==NULL&&p->Rptr!=NULL)//p chi co con phai
- {
- if(p==r->Lptr)//p la con trai cua R
- r->Lptr=p->Rptr;
- else if(p==r->Rptr)
- r->Rptr=p->Rptr;
- p->Rptr=NULL;
- free(p);
- r=T;
- printf("Da xoa nut %d\n",x);
- return r;
- }
- if(p->Lptr!=NULL&&p->Rptr==NULL)//p chi co con trai
- {
- if(p==r->Lptr)
- r->Lptr=p->Lptr;
- else if(p==r->Rptr)
- r->Rptr=p->Lptr;
- p->Lptr=NULL;
- free(p);
- r=T;
- printf("Da xoa nut %d\n",x);
- return r;
- }
- //p co 2 con
- if(p->Lptr!=NULL&&p->Rptr!=NULL)
- {
- if(r->Lptr==p)
- {
- temp=p->Lptr;
- r->Lptr=p->Lptr;
- while(temp->Rptr!=NULL)
- temp=temp->Rptr;
- temp->Rptr=p->Rptr;
- p->Lptr=NULL;
- p->Rptr=NULL;
- }
- else if(r->Rptr==p)
- {
- temp=p->Rptr;
- r->Rptr=p->Rptr;
- while(temp->Lptr!=NULL)
- temp=temp->Lptr;
- temp->Lptr=p->Lptr;
- p->Lptr=NULL;
- p->Rptr=NULL;
- }
- free(p);
- r=T;
- printf("Da xoa nut %d\n",x);
- return r;
- }
- return T;
- }
- Node_Type* First_Even(Node_Type *p) {
- if(p!=NULL) {
- Node_Type *found = First_Even(p->Lptr);
- if(found!=NULL) { return found; }
- return (p->info%2==0) ? p : First_Even(p->Rptr);
- }
- return NULL;
- }
- int Count_Leaf(Node_Type* p)
- {
- if(p == NULL) return 0;
- if(p->Lptr == NULL && p->Rptr==NULL)
- return 1;
- else
- return Count_Leaf(p->Lptr)+ Count_Leaf(p->Rptr);
- }
- float Mean(Node_Type *p)
- {
- float s=0;
- if(p!=NULL)
- {
- if(p->Lptr != NULL) s+=Mean(p->Lptr);
- if(p->info>0)
- {
- s+=p->info;
- cntr++;
- }
- if(p->Rptr != NULL) s+=Mean(p->Rptr);
- }
- return s;
- }
- void Delete_Tree(Node_Type *p)
- {
- if(p->Lptr!=NULL)
- {
- Delete_Tree(p->Lptr);
- p->Lptr=NULL;
- }
- if(p->Lptr!=NULL)
- {
- Delete_Tree(p->Rptr);
- p->Rptr=NULL;
- }
- free(p);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement