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 / bstrees.c next >
C/C++ Source or Header  |  1997-05-15  |  2KB  |  97 lines
  1. #include<stdio.h>
  2. #include "trees.h"
  3.  
  4. void   insert(int x,tree *T);
  5.  /* inserisce x nell'albero T (passaggio x rif) */
  6.  
  7. tree   search(int x,tree T);
  8.  /* restituisce un puntatore al nodo con etichetta x  */  
  9.  
  10. void   delete(int x,tree *T);
  11.  /* cancella x da T */
  12.  
  13. main()
  14.   {
  15.     tree R,S,T;
  16.     int i,x;
  17.  
  18. /* inserisce in un albero (ordinato) e calcola la sua altezza */
  19.  
  20.     for (i=0;i<10;scanf("%d",&x),insert(x,&R),i++);
  21.     bfs(R);
  22.     printf("\n Altezza albero %d",length(R));
  23.  
  24. /* cancello un elemento */
  25.  
  26.     printf("\n Delete: which one?"); 
  27.     scanf("%d",&x);
  28.     delete(x,&R);
  29. /* stampo l'albero */
  30.     bfs(R);
  31. /* cerco un elemnto */
  32.     printf("\n Find: which one?"); 
  33.     scanf("%d",&x);
  34.     printf("Found? %d",(search(x,R)!=NULL)?1:0);
  35. /* oss: search restituisce un puntatore! */
  36.   } 
  37.  
  38. void insert(int x,tree *T) 
  39. {     
  40.   if (is_empty_tree(*T))  
  41.         *T=maketree(x,emptytree(),emptytree());
  42.   else if (x<root(*T))   
  43.             insert(x,&(*T)->left); 
  44.   else if (root(*T)<x)   
  45.             insert(x,&(*T)->right); 
  46. }
  47.  
  48. tree search(int x,tree T)
  49.   /* cerca l'etich. x nell'albero e restituisce un puntatore al nodo che la contiene */
  50. {
  51.  if (is_empty_tree(T))  
  52.      return NULL;
  53.  if (x==root(T))       
  54.      return T;
  55.  else if (x<root(T))   
  56.           return search(x,T->left); 
  57.  else if (x>root(T))   
  58.           return search(x,T->right);
  59. }
  60.  
  61.  
  62. int  deletemin(tree *T) 
  63.    /* T non e' vuoto per ipotesi (vedi proc. "delete" )  cancello nodo con etichetta di valore minimo
  64.       (quello + a sx) da T */
  65. {     
  66.   int min;
  67.               
  68.   if (is_empty_tree((*T)->left))
  69.       {
  70.         min=root(*T);
  71.         *T=(*T)->right;
  72.         return min;
  73.       } 
  74.   else return deletemin(&(*T)->left);       
  75. }
  76.  
  77. void  delete(int x,tree *T)
  78.   /* cancello nodo con etichetta x da T: vari casi*/
  79.  
  80. {     
  81.   if (!is_empty_tree(*T))
  82.     if (root(*T) >x)                     
  83.        delete(x,&(*T)->left);             /*  */
  84.     else if (root(*T) <x)                 /*  non ho ancora trovato x: scendo nell'albero */
  85.        delete(x,&(*T)->right);            /*  */
  86.   
  87.     else if (is_empty_tree((*T)->left))      /* ho trovato x e il suo figlio sx e' NULL */
  88.        *T=(*T)->right;
  89.     else if (is_empty_tree((*T)->right))    /*  "   "                   "   dx    "   */
  90.        *T=(*T)->left;
  91.     else (*T)->root=deletemin(&(*T)->right);  /* "  "       e i figli non sono vuoti sostituisco  */
  92.                                               /* x con il minimo del sottoalbero destro (non vuoto) */
  93. }
  94.  
  95.  
  96.  
  97.