Guest User

BinarySearchTree_FamiHug

a guest
Dec 6th, 2010
181
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Problem
  2.  *  viết c.tr
  3.  * 1.tạo 1 cây tìm kiếm chứa số nguyên
  4.  * 2.Tìm 1 nút nào đấy
  5.  * 3.xóa 1 nút nào đó trên cây
  6.  * 4.xóa hết
  7.  * 5.xác định nút chẵn đầu tiên trong danh sách duyệt giữa
  8.  * 6.tìm trung bình cộng của các phần tử duong
  9.  * 7.đếm số nút lá
  10.  * Ver 1.0
  11.  * Nhap cac gtri tu file
  12.  
  13.  * Future: 2.0
  14.  * Chinh lai gtri nhap vao TRUC TIEP: truong hop a, aa, a-4759234
  15.  */
  16.  
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19.  
  20. typedef struct nod
  21. {
  22.     int info;
  23.     //int count;
  24.     struct nod * Lptr;
  25.     struct nod * Rptr;
  26. } Node_Type;
  27.  
  28. Node_Type* Add(Node_Type*,int);
  29. Node_Type* Create_Node(int);
  30. void Traverse(Node_Type* );
  31. void Visit(Node_Type*);
  32. Node_Type* Find(Node_Type*, int);
  33. Node_Type* Find_R(Node_Type*,int);
  34. Node_Type* First_Even(Node_Type *);
  35. Node_Type* Create_Tree(Node_Type*,int);
  36. float Mean(Node_Type *);
  37. int Count_Leaf(Node_Type* );
  38. Node_Type* Delete_Node(Node_Type*,int);
  39. void Delete_Tree(Node_Type *p);
  40.  
  41. Node_Type *T,*p,*r,*u,*k,*d;
  42.  
  43. int f=0,cntr=0;
  44. float s=0;
  45. int main(int argc, char** argv)
  46. {
  47.     T=NULL;
  48.     r=NULL;
  49.     char Choice, w[80];
  50.     int x;
  51.     int l=0;
  52.    
  53.     printf( "\nCHUONG TRINH MINH HOA CAY NHI PHAN"
  54.             "\n Go aX de nhap so nguyen X."
  55.             "\n-Go rX de xoa nut co noi dung X khoi cay"
  56.             "\n-Go fX de tim kiem nut co noi dung X"
  57.             "\n-Go D de xoa tat ca cac nut"
  58.             "\n-Go P de in ra cay theo cach duyet giua"
  59.             "\n-Go E de tim phan tu chan dau tien theo cach duyet giua"
  60.             "\n-Go M de tinh trung binh cong cac phan tu duong"
  61.             "\n Go L de dem so nut la"
  62.             "\n-Go ! de thoat khoi chuong trinh\n");
  63.    
  64.     while(1)
  65.     {
  66.         Choice=0;
  67.         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)
  68.         fflush(stdin);
  69.         printf("Nhap: ");
  70.         sscanf(gets(w),"%c %d",&Choice,&x);
  71.         if((x>=(-32768))&&(x<=32767))//g.han kieu int
  72.         {
  73.             switch (Choice)
  74.             {
  75.                 case 'a':
  76.                     T = Add(T,x);
  77.                     break;
  78.                 case 'P':
  79.                     if(T==NULL)
  80.                         printf("Cay rong\n\n");
  81.                     else
  82.                     {
  83.                         Traverse(T);
  84.                         printf("\n\n");
  85.                     }
  86.                     break;
  87.                 case 'f':
  88.                     p=Find(T,x);
  89.                     if(p!=NULL)
  90.                         printf("Tim thay nut %d trong cay\n\n",x);
  91.                     else
  92.                         printf("KHONG tim thay nut %d trong cay\n\n",x);
  93.                     break;
  94.                                    
  95.                 case 'd':
  96.                     d=Find_R(T,x);
  97.                     printf("Nut cha cua %d la %d\n",x,d->info);
  98.                     break;
  99.                    
  100.                 case 'r':
  101.                     r=Find(T,x);
  102.                     if(r==NULL)
  103.                         printf("Khong tim thay so %d trong cay\n\n",x);
  104.                     else
  105.                     {r=Delete_Node(T,x);
  106.                     if(r==NULL)
  107.                     {
  108.                         T=(Node_Type *)malloc(sizeof(Node_Type));
  109.                         T=NULL;
  110.                     }}
  111.                     break;
  112.                    
  113.                 case 'D':
  114.                     if(T==NULL)
  115.                         printf("Cay rong, khong the xoa!\n\n");
  116.                     else
  117.                     {
  118.                     Delete_Tree(T);
  119.                     printf("Da xoa cay\n\n");
  120.                     T=(Node_Type *)malloc(sizeof(Node_Type));
  121.                     T=NULL;
  122.                     }
  123.                     break;
  124.                    
  125.                 case 'E':
  126.                     k=First_Even(T);
  127.                     if(k!=NULL)
  128.                         printf("Phan tu chan dau tien theo cach duyet giua la: %d\n\n",k->info);
  129.                     else
  130.                         printf("Cay khong co nut chan nao!\n\n");
  131.                     break;
  132.                    
  133.                 case 'L':
  134.                     l=Count_Leaf(T);
  135.                     printf("So nut la cua cay da cho la: %d\n\n",l);
  136.                     break;
  137.                    
  138.                 case 'M':
  139.                     s=0;
  140.                     cntr=0;
  141.                     s=Mean(T);
  142.                     printf("Trung binh cong cua cac phan tu duong la : %f\n\n",s/cntr);
  143.                     break;
  144.                
  145.                 case '!':
  146.                     printf("\nChuong trinh ket thuc!");
  147.                     exit(1);                               
  148.             }
  149.         }
  150.        
  151.     }
  152.    
  153.     return 0;
  154. }
  155.  
  156. Node_Type* Add(Node_Type* p,int x)
  157. {
  158.     if(p==NULL)
  159.         p=Create_Node(x);
  160.     else
  161.         {  
  162.            
  163.             if(x<p->info)
  164.                 p->Lptr=Add(p->Lptr,x);
  165.             else
  166.                 if(x>p->info)
  167.                     p->Rptr=Add(p->Rptr,x);
  168.                 else
  169.                     printf("Gia tri nhap vao da co trong cay. Nhap lai so khac!\n");
  170.                    
  171.         }
  172.     return p;  
  173. }
  174.  
  175. Node_Type* Create_Node(int x)
  176. {
  177.     Node_Type *l;
  178.     l=(Node_Type *)malloc(sizeof(Node_Type));
  179.     l->info=x;
  180.     l->Lptr=NULL;
  181.     l->Rptr=NULL;
  182.     printf("Da them %d vao cay nhi phan\n",x);
  183.     return l;
  184. }
  185.    
  186. void Traverse(Node_Type* pt)
  187. {
  188.     if(pt!=NULL)
  189.     {
  190.         Traverse(pt->Lptr);
  191.         Visit(pt);
  192.         Traverse(pt->Rptr);
  193.     }
  194. }
  195.  
  196. void Visit(Node_Type* p)
  197. {
  198.     printf("%d ",p->info);
  199. }
  200.  
  201. Node_Type * Find(Node_Type *p, int x)
  202. {
  203.     int i=0;
  204.     while(p!=NULL)
  205.     {
  206.         if(x<p->info)
  207.         {
  208.             p=p->Lptr;
  209.         }
  210.         else
  211.             if(x==p->info)
  212.                 {  
  213.                     i++;
  214.                     return p;
  215.                 }
  216.             else
  217.                 {
  218.                     p=p->Rptr;
  219.                 }
  220.     }
  221.     return p;
  222. }
  223. Node_Type* Find_R(Node_Type *p,int x)
  224. {
  225.     int i=0;
  226.     r=p;
  227.     while(p!=NULL)
  228.     {
  229.         if(x<p->info)
  230.         {
  231.             r=p;
  232.             p=p->Lptr;
  233.         }
  234.         else
  235.             if(x==p->info)
  236.                 {  
  237.                     i++;
  238.                     return r;
  239.                 }
  240.             else
  241.                 {
  242.                     r=p;
  243.                     p=p->Rptr;
  244.                 }
  245.     }
  246.     return r;
  247. }
  248.  
  249.  
  250. Node_Type* Delete_Node(Node_Type *T,int x)
  251. {
  252.     Node_Type *p,*temp,*nr;
  253.    
  254.     p=Find(T,x);
  255.     r=Find_R(T,x);
  256.     if(p==T)//Xoa Goc
  257.         {
  258.             if((p->Lptr==NULL)&&(r->Rptr==NULL))
  259.             {
  260.                
  261.                 r=NULL;
  262.                 printf("Da xoa nut %d\n",x);
  263.                 free(p);
  264.                 return r;              
  265.             }
  266.             else if((p->Lptr!=NULL)&&(r->Rptr==NULL))//Goc chi co con trai
  267.             {
  268.                 r=r->Lptr;
  269.                 T=r;
  270.                 printf("Da xoa nut %d\n",x);
  271.                 free(p);
  272.                 return r;
  273.             }
  274.             else if((p->Lptr==NULL)&&(r->Rptr!=NULL))
  275.             {
  276.                 r=r->Rptr;
  277.                 T=r;
  278.                 printf("Da xoa nut %d\n",x);
  279.                 free(p);
  280.                 return r;          
  281.             }
  282.             else if(p->Lptr!=NULL&&p->Rptr!=NULL)
  283.             {
  284.                 nr=p->Rptr;
  285.                 r=p->Lptr;
  286.                 temp=nr;
  287.                 while(temp->Lptr!=NULL)
  288.                     temp=temp->Lptr;
  289.                 temp->Lptr=r;
  290.                 r=nr;
  291.                 T=nr;
  292.                 free(p);
  293.                 printf("Da xoa nut %d\n",x);
  294.                 return r;  
  295.             }
  296.         }
  297.        
  298.         //P la nut la
  299.     else if((p->Lptr==NULL)&&(r->Rptr==NULL))
  300.         {
  301.             printf("Da xoa la %d\n",p->info);
  302.             if(r->Lptr==p)
  303.                 r->Lptr=NULL;
  304.             if(r->Rptr==p)
  305.                 r->Rptr=NULL;
  306.             r=T;
  307.             free(p);
  308.             return r;
  309.            
  310.         }
  311.        
  312.        
  313.        
  314.         //TH p chi co 1 con
  315.             if(p->Lptr==NULL&&p->Rptr!=NULL)//p chi co con phai
  316.                 {
  317.                     if(p==r->Lptr)//p la con trai cua R
  318.                         r->Lptr=p->Rptr;
  319.                     else if(p==r->Rptr)
  320.                         r->Rptr=p->Rptr;
  321.                     p->Rptr=NULL;
  322.                     free(p);
  323.                     r=T;
  324.                     printf("Da xoa nut %d\n",x);
  325.                     return r;
  326.                 }
  327.             if(p->Lptr!=NULL&&p->Rptr==NULL)//p chi co con trai
  328.                 {
  329.                     if(p==r->Lptr)
  330.                         r->Lptr=p->Lptr;
  331.                     else if(p==r->Rptr)
  332.                         r->Rptr=p->Lptr;
  333.                     p->Lptr=NULL;
  334.                     free(p);
  335.                     r=T;
  336.                     printf("Da xoa nut %d\n",x);
  337.                     return r;  
  338.                 }              
  339.         //p co 2 con
  340.         if(p->Lptr!=NULL&&p->Rptr!=NULL)
  341.         {
  342.             if(r->Lptr==p)
  343.             {
  344.                 temp=p->Lptr;
  345.                 r->Lptr=p->Lptr;
  346.                 while(temp->Rptr!=NULL)
  347.                     temp=temp->Rptr;
  348.                 temp->Rptr=p->Rptr;
  349.                 p->Lptr=NULL;
  350.                 p->Rptr=NULL;
  351.             }
  352.             else if(r->Rptr==p)
  353.             {
  354.                 temp=p->Rptr;
  355.                 r->Rptr=p->Rptr;
  356.                 while(temp->Lptr!=NULL)
  357.                     temp=temp->Lptr;
  358.                 temp->Lptr=p->Lptr;
  359.                 p->Lptr=NULL;
  360.                 p->Rptr=NULL;
  361.             }
  362.            
  363.             free(p);
  364.             r=T;
  365.             printf("Da xoa nut %d\n",x);
  366.             return r;
  367.         }
  368.        
  369.     return T;
  370. }
  371.  
  372.  
  373.  
  374. Node_Type* First_Even(Node_Type *p) {
  375.     if(p!=NULL) {
  376.         Node_Type *found = First_Even(p->Lptr);
  377.         if(found!=NULL) { return found; }
  378.         return (p->info%2==0) ? p : First_Even(p->Rptr);
  379.     }
  380.     return NULL;
  381. }
  382.  
  383. int Count_Leaf(Node_Type* p)
  384. {
  385.     if(p == NULL) return 0;
  386.     if(p->Lptr == NULL && p->Rptr==NULL)
  387.     return 1;
  388.   else
  389.     return Count_Leaf(p->Lptr)+ Count_Leaf(p->Rptr);
  390. }
  391.  
  392. float Mean(Node_Type *p)
  393. {
  394.     float s=0;
  395.     if(p!=NULL)
  396.     {
  397.         if(p->Lptr != NULL) s+=Mean(p->Lptr);
  398.         if(p->info>0)
  399.         {
  400.             s+=p->info;
  401.             cntr++;
  402.         }
  403.         if(p->Rptr != NULL) s+=Mean(p->Rptr);
  404.     }
  405.     return s;
  406. }
  407.  
  408. void Delete_Tree(Node_Type *p)
  409. {
  410.     if(p->Lptr!=NULL)
  411.     {
  412.         Delete_Tree(p->Lptr);
  413.         p->Lptr=NULL;
  414.     }
  415.     if(p->Lptr!=NULL)
  416.     {
  417.         Delete_Tree(p->Rptr);
  418.         p->Rptr=NULL;
  419.     }
  420.     free(p);
  421. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×