aleix616

Cerca de subarbres binaris

Jun 17th, 2015
301
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.10 KB | None | 0 0
  1. static node_arbre* i_sub_arrel(node_arbre *n, const T& x, int& altura){
  2.     node_arbre *m = NULL;
  3.     if (n != NULL){
  4.         if (n->info == x){
  5.             m = copia_node_arbre(n);
  6.         } else {
  7.             int alt1, alt2;
  8.             alt1 = alt2 = altura+1;
  9.             m = i_sub_arrel(n->segE,x,alt1);
  10.             node_arbre *aux = NULL;
  11.             aux = i_sub_arrel(n->segD,x,alt2);
  12.             if (m == NULL){ // No hi ha cap aparicio al fill esquerra
  13.                 m = aux;
  14.                 altura += alt2;
  15.             } else if (aux != NULL){ // m != NULL comparem les altures per determinar
  16.                 if (alt1 > alt2){
  17.                     m = aux;
  18.                     altura += alt2;
  19.                 }
  20.             } else altura += alt1; // No hi ha aparicions al fill dret
  21.         }
  22.     }
  23.     return m;
  24. }
  25.  
  26. void sub_arrel(Arbre& asub, const T& x)
  27.  /* Pre: p.i. = A, asub es buit */
  28.  /* Post: si A conte x, asub es el subarbre d'A resultat de la cerca;
  29.     si A no conte x, asub es buit */
  30. {
  31.     int altura = 0;
  32.     asub.primer_node = i_sub_arrel(primer_node, x, altura);
  33. }
Advertisement
Add Comment
Please, Sign In to add comment