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 / parte3.c < prev    next >
C/C++ Source or Header  |  1999-03-11  |  2KB  |  89 lines
  1. /* Esame 14 settembre '98 - parte 3 */
  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. static int max(int,int);
  17.  
  18. void insert(int,tree*);
  19.  
  20. void print(tree);
  21.  
  22. int height(tree);
  23.  
  24. int max(int i, int j)
  25. {
  26.   return i>j ? i : j;
  27. }
  28.  
  29. void insert(int i, tree *t)
  30. {
  31.   if (*t==NULL) /* caso base: albero vuoto */
  32.     {
  33.       *t=(tree) malloc(sizeof(struct node));
  34.       (*t)->el=i;
  35.       (*t)->left=NULL;
  36.       (*t)->right=NULL;
  37.     }
  38.   else if (i<=(*t)->el) /* passo induttivo, sottoalbero sinistro */
  39.     insert(i,&((*t)->left));
  40.   else                 /* passo induttivo, sottoalbero destro (i>(*t)->el) */
  41.     insert(i,&((*t)->right));
  42. }   
  43.  
  44.  
  45. void print(tree t)
  46. {
  47.   if (t!=NULL) /* se l'albero e` vuoto non stampa nulla */
  48.     {
  49.       print(t->left);
  50.       printf(" %d",t->el);
  51.       print(t->right);
  52.     }
  53. }
  54.  
  55. int height(tree t)
  56. {
  57.   if (t==NULL) 
  58.     return -1; /* albero vuoto */
  59.   else
  60.     if (t->left==NULL && t->right==NULL)
  61.       return 0; /* foglia */
  62.   else
  63.     return 1+max(height(t->left),height(t->right)); /* nodo interno */
  64. }
  65.  
  66. int main(void)
  67. {
  68.   char fname[MAX];
  69.   tree t=NULL;
  70.   FILE *fd=NULL;
  71.   int i;
  72.  
  73.   printf("Enter file name: ");
  74.   scanf("%s",fname);
  75.   if (fd=fopen(fname,"r"))
  76.     {
  77.       while (fscanf(fd,"%d",&i)==1 && i!=-1)
  78.       insert(i,&t);
  79.       printf("Tree from file %s: ",fname);
  80.       print(t);
  81.       printf("\n");
  82.       printf("Height: ");
  83.       printf("%d\n",height(t));
  84.       fclose(fd);
  85.     }
  86.   else
  87.     printf("Error opening file %s\n",fname);
  88. }
  89.