SHARE
TWEET

Untitled

a guest Dec 6th, 2010 34 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
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top