SHARE
TWEET

BinarySearchTree_FamiHug

a guest Dec 6th, 2010 157 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top