Guest User

Untitled

a guest
Dec 6th, 2010
100
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //      minhhoaTREE_yoyolove.c
  2. //      
  3. //      Copyright 2010 YoYoLove <traitimbanggia.199x@gmail.com>
  4.  
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8.  
  9. typedef struct pointer
  10. {
  11.     struct pointer *lptr, *rptr;
  12.     int info;
  13. } tree;
  14.  
  15. int S[100];
  16. int j=0;
  17. float s;
  18.  
  19. tree *add_node(tree *p, int giatrinut)
  20. {
  21.     tree *A=NULL,*B=NULL;
  22.     if(p == NULL)
  23.     {
  24.         p=(tree*)malloc(sizeof(tree));
  25.         p->info = giatrinut;
  26.         p->lptr = NULL;
  27.         p->rptr = NULL;
  28.     }
  29.     else
  30.     {
  31.         A = p;
  32.         while(A != NULL)
  33.         {
  34.                 if(giatrinut == A->info)
  35.                 {
  36.                 printf("\n Exit...");
  37.                 exit(0);
  38.                 }
  39.  
  40.                 else if(giatrinut < A->info)
  41.                 {
  42.                     B=A; A=A->lptr;
  43.                 }
  44.                 else
  45.                 {
  46.                     B=A; A=A->rptr;
  47.                 }
  48.            
  49.         }
  50.         A=(tree*)malloc(sizeof(tree));
  51.         A->info = giatrinut;
  52.         A->lptr = A->rptr = NULL;
  53.         if(giatrinut < B->info)
  54.         {
  55.             B->lptr = A;
  56.         }
  57.         else
  58.         {
  59.             B->rptr = A;
  60.         }
  61.     }
  62.     return p;
  63. }
  64.  
  65. void duyetgiua(tree *p)
  66. {
  67.     if(p->lptr !=NULL)
  68.     {
  69.     duyetgiua(p->lptr);
  70.     }
  71.     printf(" %5d",p->info);
  72.     if(p->rptr !=NULL)
  73.     {
  74.     duyetgiua(p->rptr);
  75.     }
  76. }
  77.  
  78. tree *timkiem(tree *p,int xxx)
  79. {
  80.     while(p!=NULL)
  81.     {
  82.         if(xxx== p->info)
  83.         {
  84.             return p; break;
  85.         }
  86.         else
  87.         {
  88.             if(xxx < p->info)
  89.             {
  90.                 if(p->lptr == NULL) return NULL;
  91.                 else p=p->lptr;
  92.             } else
  93.             {
  94.                 if(p->rptr == NULL) return NULL;
  95.                 else p=p->rptr;
  96.             }
  97.         }
  98.     }
  99.     return p;
  100. }
  101.  
  102. int tim_chan(tree *p)
  103. {
  104.     if(p->lptr !=NULL)
  105.         {
  106.             tim_chan(p->lptr);
  107.         }
  108.     if(p->info%2==0)
  109.         {
  110.             ++j; S[j]=p->info;
  111.         }
  112.     if(p->rptr !=NULL)
  113.         {
  114.             tim_chan(p->rptr);
  115.         }
  116.     return j;
  117. }
  118.  
  119. void delete_node(tree *p,int xxx)
  120. {
  121.     tree *A, *B, *C, *D;
  122.     A=p;
  123.     A=timkiem(A,xxx);
  124.     if(A == NULL)
  125.     {
  126.         printf("\n Gia tri vua nhap %d khong ton tai, khong the xoa! \n ket thuc...", xxx);
  127.         exit(0);
  128.     }
  129.     else
  130.     {
  131.         // A->info = xxx
  132.         //tim cha cua nut can xoa
  133.         B=p;
  134.         while(B!=NULL)
  135.         {
  136.             C=B;
  137.             if(xxx < B->info) B=B->lptr;
  138.             if(xxx > B->info) B=B->rptr;
  139.             if(B->info == xxx) break;
  140.         }
  141.         B=C;
  142.         //Cha nut can xoa: B->info)
  143.         //Xoa
  144.         //nut xoa la nut la:
  145.         if(A->lptr==NULL && A->lptr==NULL)
  146.         {
  147.             if(A==B) //A la goc
  148.                 {
  149.                     p=NULL;
  150.                 }
  151.                
  152.             if(A->info < B->info) //A la con trai cua B
  153.                 {
  154.                     B->lptr=NULL;
  155.                 }
  156.                
  157.             if(A->info > B->info) //A la con phai cua B
  158.                 {
  159.                     B->rptr=NULL;  
  160.                 }
  161.         }
  162.        
  163.         if(A->lptr==NULL && A->rptr != NULL) //nut xoa la nut nua la co con phai
  164.             {
  165.                 if(A==B)
  166.                 {
  167.                     B=B->rptr;
  168.                     p=B;
  169.                     A->rptr=NULL;
  170.                 }else              
  171.                     {
  172.                         B->rptr=A->rptr;
  173.                        
  174.                     }A->rptr = NULL;
  175.                
  176.             }
  177.         if(A->rptr==NULL && A->lptr != NULL) //nut xoa la nut nua la co con trai
  178.             {
  179.                 if(A==B)
  180.                 {
  181.                     B=B->lptr;
  182.                     p=B;
  183.                     A->rptr=NULL;
  184.                 }else
  185.                     {
  186.                         B->lptr=A->lptr;
  187.                         A->lptr= NULL;
  188.                     }
  189.             }
  190.        
  191.         if((A->rptr !=NULL) && (A->lptr != NULL)) //Truong hop A la cay con
  192.         {
  193.             C=A->rptr;
  194.             D=C;//tim nut trai tan cung ben phai: C la con cua A
  195.             while(C->lptr!=NULL) //tim cha cua C
  196.             {
  197.                 D=C;
  198.                 C=C->lptr;
  199.             }
  200.             printf("\n A-left= %d", A->lptr->info);
  201.             printf("\n C= %d", C->info);
  202.             printf("\n D= %d", D->info);
  203.             if(A==B) //neu A la goc
  204.             {
  205.                 if(C==D)
  206.                 {
  207.                     C->lptr=A->lptr;
  208.                     C->rptr=NULL;
  209.                     p=C;
  210.                 }else
  211.                     {
  212.                         C->lptr=A->lptr;
  213.                         C->rptr=D;
  214.                         p=C;
  215.                     }
  216.                        
  217.             }
  218.            
  219.             if(B->lptr == A) // A la cay con trai cua B
  220.             {
  221.                 if(C==D) //truong hop  C la nut la: C=D
  222.                 {
  223.                     C->lptr=A->lptr;
  224.                     B->lptr=C;
  225.                     A->lptr=A->rptr=NULL;
  226.                 }
  227.                 else
  228.                     {
  229.                         D->lptr=NULL;
  230.                         B->lptr=C;
  231.                         C->lptr=A->lptr;
  232.                         C->rptr=A->rptr;
  233.                         A->lptr=A->rptr=NULL;
  234.                        
  235.                     }
  236.                
  237.             }
  238.            
  239.             if(B->rptr== A) // A la cay con phai cua B
  240.             {
  241.                 if(C==D) //truong hop  C la nut la: C=D
  242.                 {
  243.                     C->lptr=A->lptr;
  244.                     C->rptr=NULL;
  245.                     B->rptr=C;
  246.                     A->lptr=A->rptr=NULL;
  247.                 }
  248.                 else
  249.                     {
  250.                         D->lptr=NULL;
  251.                         B->rptr=C;
  252.                         C->lptr=A->lptr;
  253.                         C->rptr=A->rptr;
  254.                         A->lptr=A->rptr=NULL;                      
  255.                     }
  256.             }
  257.         }
  258.            
  259.         printf("\n Da xoa: %d", A->info);
  260.         free(A);
  261.        
  262.         if(p!=NULL)
  263.         {
  264.         printf("\n Cay sau khi xoa duyet theo thu tu giua: \n");
  265.         duyetgiua(p);
  266.         }else
  267.                 {
  268.                     printf("\n Cay rong...");
  269.                     exit(0);
  270.                 }
  271.     }
  272. }
  273.  
  274. int dem_nut_la(tree *p)
  275. {
  276.     if(p->lptr !=NULL) dem_nut_la(p->lptr);
  277.    
  278.     if(p->rptr==p->lptr) j++;
  279.    
  280.     if(p->rptr !=NULL) dem_nut_la(p->rptr);
  281.    
  282.     return j;
  283. }
  284.  
  285. float tbc(tree *p)
  286. {
  287.     if(p->lptr !=NULL) tbc(p->lptr);
  288.    
  289.     if(p->info > 0)
  290.     {
  291.         s=s+p->info; j++;
  292.     }  
  293.     if(p->rptr !=NULL) tbc(p->rptr);
  294.    
  295.     return s;
  296. }
  297.  
  298. int main()
  299. {
  300.     tree *root=NULL, *T=NULL;
  301.     int n,i,sonut;
  302.  
  303.     printf("\n So nut ( > 0): ");
  304.     scanf("%d",&sonut);
  305.  
  306.     for(i=1;i<=sonut;i++)
  307.     {
  308.         printf("\n Nut thu %d= ", i);
  309.         scanf("%d",&n);
  310.         root = add_node(root,n);
  311.     }
  312.    
  313.     T=root;
  314.     //duyet
  315.     printf("\n \n Cay da nhap: \n");
  316.     duyetgiua(root);
  317.  
  318.     //tim kiem
  319.     root=T;
  320.     printf("\n\n Nhap vao gia tri tim kiem n= ");
  321.     scanf("%d",&n);
  322.     root = timkiem(root,n);
  323.     if(root!=NULL) printf("\n Ton tai %d", root->info);
  324.     else printf("\n Khong ton tai %d",n);
  325.    
  326.     //them nut
  327.     printf("\n\n Nhap gia tri muon them: ");
  328.     scanf("%d",&n);
  329.     root=T;
  330.     root = timkiem(root,n);
  331.     if(root!=NULL)
  332.     {
  333.         printf("\n Gia tri vua nhap da ton tai (%d) khong the them", root->info);
  334.         exit(0);
  335.     }
  336.     else
  337.     {
  338.         root=T;
  339.         root=add_node(root,n);
  340.         printf("\n Cay moi: \n");
  341.         duyetgiua(root);
  342.     }
  343.  
  344.     printf("\n\n");
  345.     root=T;
  346.     j=tim_chan(root);
  347.     if(j!=0) printf("\n Phan tu chan dau tien duyet theo thu tu giua: %d \n",S[1]);
  348.     else printf("\n Khong co so chan nao trong cay...");
  349.    
  350.     root=T;
  351.     j=0;
  352.     j=dem_nut_la(root);
  353.     printf("\n\n");
  354.     printf("\n So nut la: %d",j);
  355.    
  356.     printf("\n\n");
  357.     root=T;
  358.     j=0;
  359.     s=tbc(root);
  360.     if(j!=0)
  361.     {
  362.         printf("\n TBC= %g",s/j);
  363.     }
  364.     else printf("\n Khong co so duong nao trong cay...");
  365.    
  366.     root=T;
  367.     printf("\n\n");
  368.     printf("\n Nhap gia tri muon xoa: ");
  369.     scanf("%d",&n);
  370.     delete_node(root,n);
  371. return(0);
  372. }
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.

×