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 / esempi / Tipi_di_dato / Alberi / trees.c < prev    next >
C/C++ Source or Header  |  1997-05-15  |  3KB  |  115 lines
  1. #include<stdio.h>
  2. #include "trees.h"
  3. #include "queue.h"
  4.  
  5. tree  emptytree(void)  { return NULL;}
  6.  
  7. int   is_empty_tree(tree T)    { return (T==emptytree());}
  8.  
  9. int   is_leaf(tree T)    
  10.   { 
  11.      return (T!=emptytree() && 
  12.               T->left==emptytree() && 
  13.                 T->right==emptytree());
  14.   }
  15.            
  16. tree  maketree(int root, tree left, tree right)
  17.  { 
  18.    tree T;
  19.  
  20.    T=(tree)malloc(sizeof(struct node));
  21.    T->root=root;
  22.    T->left=left;
  23.    T->right=right;  
  24.    return T;
  25.  }
  26.  
  27. int  root(tree T)        { return T->root;  }
  28.  
  29. int length(tree T)
  30.  {
  31.    int N,M;
  32.  
  33.    if (is_empty_tree(T)) return 0;
  34.    else
  35.      {
  36.        N=length(T->left);
  37.        M=length(T->right);
  38.        return (N>M?N+1:M+1);
  39.      }   
  40.  }
  41.  
  42. int append(int Leaf,tree T,tree T1,tree T2)
  43.  /* aggiunge alla prima foglia piu' a sx */
  44.  {
  45.    if (is_empty_tree(T)) return 0;
  46.    if (is_leaf(T) && root(T)==Leaf)
  47.       {
  48.         T->left=T1;
  49.         T->right=T2;
  50.         return 1;
  51.       } 
  52.    else return 
  53.     (append(Leaf,T->left,T1,T2) || append(Leaf,T->right,T1,T2));   
  54.  }
  55.  
  56. void copy(tree T,tree *C)
  57.  {
  58.    tree L,R;
  59.  
  60.    if (is_empty_tree(T)) (*C)=emptytree(); 
  61.    else
  62.     { 
  63.       copy(T->left,&L);
  64.       copy(T->right,&R);
  65.       (*C)=maketree(root(T),L,R);   
  66.     }
  67.  }
  68.  
  69. void dfs(tree T)
  70. {
  71.   if (!is_empty_tree(T))
  72.    {
  73.      dfs(T->left);
  74.      printf(" %d",root(T));  
  75.      dfs(T->right);
  76.    }
  77. }
  78.  
  79. void bfs(tree T)
  80. {
  81.   queue Q; 
  82.    /* le code hanno come elementi un puntatore a nodo (tree), 
  83.       il livello del nodo considerato  e l'etichetta del padre 
  84.       Qui mi interessa stamapare l'albero a livelli (cioe' andare a capo
  85.      alla fine di ogni livello) e' per questo che memorizzo il livello
  86.      dei nodi nella coda. Memorizzare anche il padre puo' essere utile leggere 
  87.      poi il risultato in stampa.
  88.    */
  89.  
  90.  
  91.   int level=0;
  92.   int level1,father;
  93.  
  94.   empty_queue(&Q);  
  95.   enqueue(T,level,0,&Q);   /* T e' il puntatore alla radice! */
  96.   printf("\n");
  97.   while (!is_empty_queue(&Q)) 
  98.   {
  99.      T=(tree)dequeue(&Q,&level1,&father);  /* seleziono il prossimo nodo da visitare cioe` T */
  100.      if (level1>level)                     /* se e' ad un livello inf. a quello corr. vado a capo */ 
  101.            { 
  102.              printf("\n");
  103.              level=level1;
  104.            }     
  105.      if (!is_empty_tree(T))                /* visito il nodo e salvo nella coda i puntatori ai figli */  
  106.       {
  107.         printf(" %d(%d,%d)",T->root,father,level);
  108.         enqueue(T->left,level+1,T->root,&Q);
  109.         enqueue(T->right,level+1,T->root,&Q);
  110.       }
  111.   }
  112.   destroy(&Q);
  113. }
  114.  
  115.