SHARE
TWEET

Untitled

a guest Dec 6th, 2010 45 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2.  
  3. #include <stdlib.h>
  4.  
  5.  
  6.  
  7. typedef struct pointer
  8.  
  9. {
  10.  
  11.         int info;
  12.  
  13.         struct pointer *LPTR;
  14.  
  15.         struct pointer *RPTR;
  16.  
  17. }pointer;
  18.  
  19.  
  20.  
  21. int dem;
  22.  
  23.  
  24.  
  25. void inorder(pointer*);
  26.  
  27. pointer *search(pointer*,int);
  28.  
  29. pointer *ins_node(pointer**,int);
  30.  
  31. int del_node(pointer**,int);
  32.  
  33. void creat_tree(pointer**,int);
  34.  
  35. void del_tree(pointer**);
  36.  
  37. pointer *first_even(pointer*);
  38.  
  39. float avg_total(pointer*);
  40.  
  41. int num_leaves(pointer*);
  42.  
  43.  
  44.  
  45. int main()
  46.  
  47. {
  48.  
  49.         pointer *T;
  50.  
  51.         int info,num;
  52.  
  53.         pointer *m;
  54.  
  55.         float s;
  56.  
  57.        
  58.  
  59.         printf("Tao cay nhi phan tim kiem gom 10 nut!\n");
  60.  
  61.         creat_tree(&T,10);
  62.  
  63.         inorder(T);
  64.  
  65.         printf("\n\n\n");
  66.  
  67.        
  68.  
  69.         printf("Tim mot nut co khoa cho truoc!\n");
  70.  
  71.         printf("Thong tin cua nut can tim la:");
  72.  
  73.         scanf("%d",&info);
  74.  
  75.         m=search(T,info);
  76.  
  77.         printf("\n\n\n");
  78.  
  79.        
  80.  
  81.         printf("Xoa nut!\n");
  82.  
  83.         if(del_node(&T,info)) printf("Nut da duoc xoa!\n");
  84.  
  85.         else printf("Chua xoa duoc nut!\n");
  86.  
  87.         inorder(T);
  88.  
  89.         printf("\n\n\n");
  90.  
  91.        
  92.  
  93.         printf("Xac dinh nut chan dau tien duyet theo thu tu giua!\n");
  94.  
  95.         m=first_even(T);
  96.  
  97.         if(m==NULL) printf("Khong co phan tu chan nao!\n");
  98.  
  99.         else
  100.  
  101.         {      
  102.  
  103.                 printf("Phan tu chan dau tien la:%d\n",m->info);
  104.  
  105.         }
  106.  
  107.         printf("\n\n\n");
  108.  
  109.        
  110.  
  111.         printf("Tinh trung binh cong cua cac phan tu duong!\n");
  112.  
  113.         dem=0;
  114.  
  115.         s=avg_total(T);
  116.  
  117.         if(s==0) printf("Khong co phan tu duong nao!\n");
  118.  
  119.         else printf("Ket qua:%g\n",s/dem);
  120.  
  121.         printf("\n\n\n");
  122.  
  123.        
  124.  
  125.         printf("Dem so nut la!\n");
  126.  
  127.         num=num_leaves(T);
  128.  
  129.         printf("Ket qua:%d\n",num);
  130.  
  131.         printf("\n\n\n");
  132.  
  133.        
  134.  
  135.         printf("Xoa cay!\n");
  136.  
  137.         del_tree(&T);
  138.  
  139.         if(T==NULL) printf("Cay da duoc xoa!\n");
  140.  
  141.         else printf("Cay chua duoc xoa!\n");
  142.  
  143.  
  144.  
  145.         return 1;
  146.  
  147. }
  148.  
  149.  
  150.  
  151. void inorder(pointer *p)
  152.  
  153. {
  154.  
  155.         if(p->LPTR != NULL) inorder(p->LPTR);
  156.  
  157.         printf("%3d",p->info);
  158.  
  159.         if(p->RPTR != NULL) inorder(p->RPTR);
  160.  
  161. }
  162.  
  163.  
  164.  
  165. pointer *search(pointer *p,int info)
  166.  
  167. {
  168.  
  169.         while(p!=NULL)
  170.  
  171.         {
  172.  
  173.                 if(p->info == info) return p;
  174.  
  175.                 else if(p->info < info) p=p->RPTR;
  176.  
  177.                 else p=p->LPTR;
  178.  
  179.         }
  180.  
  181.         return p;
  182.  
  183. }
  184.  
  185.  
  186.  
  187. pointer *ins_node(pointer **p,int info)
  188.  
  189. {
  190.  
  191.         pointer *m,*q;
  192.  
  193.         q=NULL;
  194.  
  195.         m=*p;
  196.  
  197.         while(m!=NULL)
  198.  
  199.         {
  200.  
  201.                 if(m->info == info) return m;
  202.  
  203.                 else if(m->info < info)
  204.  
  205.                 {
  206.  
  207.                         q=m;
  208.  
  209.                         m=m->RPTR;
  210.  
  211.                 }
  212.  
  213.                 else
  214.  
  215.                 {
  216.  
  217.                         q=m;
  218.  
  219.                         m=m->LPTR;
  220.  
  221.                 }
  222.  
  223.         }
  224.  
  225.         m=(pointer*)malloc(sizeof(pointer));
  226.  
  227.         m->info = info;
  228.  
  229.         m->LPTR = m->RPTR = NULL;
  230.  
  231.         if(*p==NULL) *p=m;
  232.  
  233.         else if(q->info < info) q->RPTR = m;
  234.  
  235.         else q->LPTR = m;
  236.  
  237.         return m;
  238.  
  239. }
  240.  
  241.  
  242.  
  243. void creat_tree(pointer **p,int n)
  244.  
  245. {
  246.  
  247.         int i,x;
  248.  
  249.         *p = NULL;
  250.  
  251.         if(n>0)
  252.  
  253.         {
  254.  
  255.                 printf("Nhap thong tin cac nut!\n");
  256.  
  257.                 for(i=1;i<=n;i++)
  258.  
  259.                 {
  260.  
  261.                         printf("Nut %d:",i);
  262.  
  263.                         scanf("%d",&x);
  264.  
  265.                         if(search(*p,x)==NULL) ins_node(p,x);
  266.  
  267.                 }
  268.  
  269.         }
  270.  
  271. }
  272.  
  273.  
  274.  
  275. int del_node(pointer **p,int info)
  276.  
  277. {
  278.  
  279.         pointer *a,*b,*c,*d;
  280.  
  281.         if(*p==NULL) return -1;
  282.  
  283.         else
  284.  
  285.         {
  286.  
  287.                 a=*p;
  288.  
  289.                 b=NULL;
  290.  
  291.                 while(a!=NULL)
  292.  
  293.                 {
  294.  
  295.                         if(info==a->info) break;
  296.  
  297.                         else if(info>a->info)
  298.  
  299.                         {
  300.  
  301.                                 b=a;
  302.  
  303.                                 a=a->RPTR;
  304.  
  305.                         }
  306.  
  307.                         else
  308.  
  309.                         {
  310.  
  311.                                 b=a;
  312.  
  313.                                 a=a->LPTR;
  314.  
  315.                         }
  316.  
  317.                 }
  318.  
  319.                 if(a==NULL) return 0;
  320.  
  321.                 else
  322.  
  323.                 {
  324.  
  325.                         if((*p)->LPTR==(*p)->RPTR)
  326.  
  327.                         {
  328.  
  329.                                 free(*p);
  330.  
  331.                                 *p=NULL;
  332.  
  333.                                 return 1;
  334.  
  335.                         }
  336.  
  337.                         else
  338.  
  339.                         {
  340.  
  341.                                 if(a->LPTR==NULL)
  342.  
  343.                                 {
  344.  
  345.                                         if(b!=NULL)
  346.  
  347.                                         {
  348.  
  349.                                                 if(info < b->info) b->LPTR=a->RPTR;
  350.  
  351.                                                 else b->RPTR=a->RPTR;
  352.  
  353.                                         }
  354.  
  355.                                         else *p=a->RPTR;
  356.  
  357.                                 }
  358.  
  359.                                 else if(a->RPTR==NULL)
  360.  
  361.                                 {
  362.  
  363.                                         if(b!=NULL)
  364.  
  365.                                         {
  366.  
  367.                                                 if(info < b->info) b->LPTR=a->LPTR;
  368.  
  369.                                                 else b->RPTR=a->LPTR;
  370.  
  371.                                         }
  372.  
  373.                                         else *p=a->LPTR;
  374.  
  375.                                 }
  376.  
  377.                                 else
  378.  
  379.                                 {
  380.  
  381.                                         d=a;
  382.  
  383.                                         c=a->LPTR;
  384.  
  385.                                         while(c->RPTR!=NULL)
  386.  
  387.                                         {
  388.  
  389.                                                 d=c;
  390.  
  391.                                                 c=c->RPTR;
  392.  
  393.                                         }
  394.  
  395.                                         if(c->info > d->info)d->RPTR=c->LPTR;
  396.  
  397.                                         else d->LPTR = c->LPTR;
  398.  
  399.                                         if(b!=NULL)
  400.  
  401.                                         {
  402.  
  403.                                                 if(info < b->info) b->LPTR=c;
  404.  
  405.                                                 else b->RPTR=c;
  406.  
  407.                                         }
  408.  
  409.                                         else *p=c;
  410.  
  411.                                         c->RPTR=a->RPTR;
  412.  
  413.                                         c->LPTR=a->LPTR;
  414.  
  415.                                 }
  416.  
  417.                                 free(a);
  418.  
  419.                                 return 1;
  420.  
  421.                         }
  422.  
  423.                 }
  424.  
  425.         }
  426.  
  427. }
  428.  
  429.  
  430.  
  431. void del_tree(pointer **p)
  432.  
  433. {
  434.  
  435.         while(*p!=NULL)
  436.  
  437.         {
  438.  
  439.                 del_node(p,(*p)->info);
  440.  
  441.         }
  442.  
  443. }
  444.  
  445.  
  446.  
  447. pointer *first_even(pointer *p)
  448.  
  449. {
  450.  
  451.         pointer *l;
  452.  
  453.         if(p==NULL) return NULL;
  454.  
  455.         else
  456.  
  457.         {
  458.  
  459.                 if(p->LPTR != NULL)
  460.  
  461.                 {
  462.  
  463.                         l=first_even(p->LPTR);
  464.  
  465.                         if(l!=NULL) return l;
  466.  
  467.                 }
  468.  
  469.                
  470.  
  471.                 if(p->info%2==0) return p;
  472.  
  473.                
  474.  
  475.                 if(p->RPTR != NULL) return first_even(p->RPTR);
  476.  
  477.         }
  478.  
  479.         return NULL;
  480.  
  481. }
  482.  
  483.  
  484.  
  485. float avg_total(pointer *p)
  486.  
  487. {
  488.  
  489.         float s=0;
  490.  
  491.         if(p!=NULL)
  492.  
  493.         {
  494.  
  495.                 if(p->LPTR != NULL) s+=avg_total(p->LPTR);
  496.  
  497.                 if(p->info>0)
  498.  
  499.                 {
  500.  
  501.                         s+=p->info;
  502.  
  503.                         dem++;
  504.  
  505.                 }
  506.  
  507.                 if(p->RPTR != NULL) s+=avg_total(p->RPTR);
  508.  
  509.         }
  510.  
  511.         return s;
  512.  
  513. }
  514.  
  515.  
  516.  
  517. int num_leaves(pointer *p)
  518.  
  519. {
  520.  
  521.         int d=0;
  522.  
  523.         if(p!=NULL)
  524.  
  525.         {
  526.  
  527.                 if(p->LPTR != NULL) d=num_leaves(p->LPTR);
  528.  
  529.                 if(p->LPTR == p->RPTR) d++;
  530.  
  531.                 if(p->RPTR != NULL) d+=num_leaves(p->RPTR);
  532.  
  533.         }
  534.  
  535.         return d;
  536.  
  537. }
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