home *** CD-ROM | disk | FTP | other *** search
/ ftp.disi.unige.it / 2015-02-11.ftp.disi.unige.it.tar / ftp.disi.unige.it / pub / .person / CataniaB / teach-act / testi-esami / labo-9.98 / parte4.c < prev    next >
C/C++ Source or Header  |  1999-03-11  |  2KB  |  105 lines
  1. /* Esame 14 settembre '98 - parte 4 */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. #define MAX 30
  7.  
  8. typedef struct node *tree;
  9.  
  10. struct node
  11. {
  12.   int el;
  13.   tree left,right;
  14. };
  15.  
  16. void insert(int,tree*);
  17.  
  18. void print(tree);
  19.  
  20. void delete(int,tree*);
  21.  
  22. void insert(int i, tree *t)
  23. {
  24.   if (*t==NULL) /* caso base: albero vuoto */
  25.     {
  26.       *t=(tree) malloc(sizeof(struct node));
  27.       (*t)->el=i;
  28.       (*t)->left=NULL;
  29.       (*t)->right=NULL;
  30.     }
  31.   else if (i<=(*t)->el) /* passo induttivo, sottoalbero sinistro */
  32.     insert(i,&((*t)->left));
  33.   else                 /* passo induttivo, sottoalbero destro (i>(*t)->el) */
  34.     insert(i,&((*t)->right));
  35. }   
  36.  
  37.  
  38. void print(tree t)
  39. {
  40.   if (t!=NULL) /* se l'albero e` vuoto non stampa nulla */
  41.     {
  42.       print(t->left);
  43.       printf(" %d",t->el);
  44.       print(t->right);
  45.     }
  46. }
  47.  
  48. void delete(int i, tree *t)
  49. {
  50.   if (*t!=NULL) /* se l'albero e` vuoto non fa  nulla */
  51.     if (i<(*t)->el)
  52.       delete(i,&((*t)->left));
  53.     else
  54.       if (i>(*t)->el)
  55.     delete(i,&((*t)->right));
  56.     else /* i==(*t)->el */
  57.       if ((*t)->left==NULL && (*t)->right==NULL) /* foglia */
  58.     {
  59.       free(*t);
  60.       *t=NULL;
  61.     }
  62.       else
  63.     if ((*t)->left==NULL) /* nodo solo con figlio destro */
  64.       {
  65.         tree aux=*t;
  66.         *t=(*t)->right;
  67.         free(aux);
  68.       }
  69.       else
  70.     if ((*t)->right==NULL) /* nodo solo con figlio sinistro */
  71.       {
  72.         tree aux=*t;
  73.         *t=(*t)->left;
  74.         free(aux);
  75.       }  
  76.    /* nota bene: se il nodo ha 2 figli non fa nulla! */
  77. }
  78.  
  79. int main(void)
  80. {
  81.   char fname[MAX];
  82.   tree t=NULL;
  83.   FILE *fd=NULL;
  84.   int i;
  85.  
  86.   printf("Enter file name: ");
  87.   scanf("%s",fname);
  88.   if (fd=fopen(fname,"r"))
  89.     {
  90.       while (fscanf(fd,"%d",&i)==1 && i!=-1)
  91.       insert(i,&t);
  92.       printf("Tree from file %s: ",fname);
  93.       print(t);
  94.       printf("\n");        
  95.       fscanf(fd,"%d",&i);
  96.       delete(i,&t);
  97.       printf("Tree after delete: ");
  98.       print(t);
  99.       printf("\n");
  100.       fclose(fd);
  101.     }
  102.   else
  103.     printf("Error opening file %s\n",fname);
  104. }
  105.