Guest User

Untitled

a guest
Dec 6th, 2010
66
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

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.

×