arboles/apl_ab.pas

   1 unit apl_ab;\r
   2 \r
   3 {\r
   4         IMPLEMENTACION : APLICACIONES ARBOLES BINARIOS\r
   5         \r
   6 }\r
   7 interface\r
   8 \r
   9 uses tda_gral, arbol_bin;\r
  10 \r
  11 { procesa todos los nodos de un arbol recursivamente en INORDEN}\r
  12 PROCEDURE APL_AB_recorrer_rec_in( a: AB_arbol);\r
  13 \r
  14 { procesa todos los nodos de un arbol recursivamente en PREORDEN}\r
  15 PROCEDURE APL_AB_recorrer_rec_pre( a: AB_arbol);\r
  16 \r
  17 { procesa todos los nodos de un arbol recursivamente en POSORDEN}\r
  18 PROCEDURE APL_AB_recorrer_rec_pos( a: AB_arbol);\r
  19 \r
  20 { busca un elemento segun una clave determinada exhaustivamente (BUSQUEDA EXTERNA) RECURSIVO }\r
  21 PROCEDURE APL_AB_buscar_externo( VAR a: AB_arbol; e: Tipo_Elem; VAR error: boolean );\r
  22 \r
  23 implementation\r
  24 \r
  25 { recorrer todos los nodos del arbol procesando todos los elementos }\r
  26 { ORDEN de recorrido: INORDEN, o sea, izquierda, nodo, derecha }\r
  27 PROCEDURE APL_AB_recorrer_rec_in( a: AB_arbol);\r
  28         PROCEDURE recorrer_rec( a: AB_arbol );\r
  29         VAR\r
  30                 error: boolean;\r
  31                 e: Tipo_Elem;\r
  32         BEGIN\r
  33                 { proceso el subarbol izquierdo }\r
  34                 AB_mover_cte( a, AB_izquierda, error );\r
  35                 IF not error\r
  36                 THEN BEGIN\r
  37                         recorrer_rec( a);\r
  38                         AB_mover_cte( a, AB_padre, error );\r
  39                 END;\r
  40                 { proceso el nodo corriente }\r
  41                 AB_elem_cte( a, e);\r
  42                 Procesar_Elem_Recorrido( e );\r
  43                 { proceso el subarbol izquierdo }\r
  44                 AB_mover_cte( a, AB_derecha, error );\r
  45                 IF not error\r
  46                 THEN BEGIN\r
  47                         recorrer_rec( a);\r
  48 {                       AB_mover_cte( a, AB_padre, error ); no hace falta }\r
  49                 END;\r
  50         END;\r
  51 VAR\r
  52         error: boolean;\r
  53 BEGIN\r
  54         { me voy a la raiz y desde allí proceso todo }\r
  55         AB_mover_cte( a, AB_raiz, error );\r
  56    recorrer_rec( a );\r
  57 END;\r
  58 \r
  59 { recorrer todos los nodos del arbol procesando todos los elementos }\r
  60 { ORDEN de recorrido: PREORDEN, o sea, nodo, izquierda, derecha }\r
  61 PROCEDURE APL_AB_recorrer_rec_pre( a: AB_arbol);\r
  62         PROCEDURE recorrer_rec( a: AB_arbol );\r
  63         VAR\r
  64                 error: boolean;\r
  65                 e: Tipo_Elem;\r
  66         BEGIN\r
  67                 { proceso el nodo corriente }\r
  68                 AB_elem_cte( a, e);\r
  69                 Procesar_Elem_Recorrido( e );\r
  70                 { proceso el subarbol izquierdo }\r
  71                 AB_mover_cte( a, AB_izquierda, error );\r
  72                 IF not error\r
  73                 THEN BEGIN\r
  74                         recorrer_rec( a);\r
  75                         AB_mover_cte( a, AB_padre, error );\r
  76                 END;\r
  77                 { proceso el subarbol izquierdo }\r
  78                 AB_mover_cte( a, AB_derecha, error );\r
  79                 IF not error\r
  80                 THEN BEGIN\r
  81                         recorrer_rec( a);\r
  82 {                       AB_mover_cte( a, AB_padre, error ); no hace falta }\r
  83                 END;\r
  84         END;\r
  85 VAR\r
  86         error: boolean;\r
  87 BEGIN\r
  88         { me voy a la raiz y desde allí proceso todo }\r
  89         AB_mover_cte( a, AB_raiz, error );\r
  90    recorrer_rec( a );\r
  91 END;\r
  92 \r
  93 { recorrer todos los nodos del arbol procesando todos los elementos }\r
  94 { ORDEN de recorrido: POSORDEN, o sea, izquierda, derecha, nodo }\r
  95 PROCEDURE APL_AB_recorrer_rec_pos( a: AB_arbol);\r
  96         PROCEDURE recorrer_rec( a: AB_arbol );\r
  97         VAR\r
  98                 error: boolean;\r
  99                 e: Tipo_Elem;\r
 100         BEGIN\r
 101                 { proceso el subarbol izquierdo }\r
 102                 AB_mover_cte( a, AB_izquierda, error );\r
 103                 IF not error\r
 104                 THEN BEGIN\r
 105                         recorrer_rec( a);\r
 106                         AB_mover_cte( a, AB_padre, error );\r
 107                 END;\r
 108                 { proceso el subarbol izquierdo }\r
 109                 AB_mover_cte( a, AB_derecha, error );\r
 110                 IF not error\r
 111                 THEN BEGIN\r
 112                         recorrer_rec( a);\r
 113                         AB_mover_cte( a, AB_padre, error );\r
 114                 END;\r
 115                 { proceso el nodo corriente }\r
 116                 AB_elem_cte( a, e);\r
 117                 Procesar_Elem_Recorrido( e );\r
 118         END;\r
 119 VAR\r
 120         error: boolean;\r
 121 BEGIN\r
 122         { me voy a la raiz y desde allí proceso todo }\r
 123         AB_mover_cte( a, AB_raiz, error );\r
 124    recorrer_rec( a );\r
 125 END;\r
 126 \r
 127 { busca un elemento segun una clave determinada exhaustivamente (BUSQUEDA EXTERNA) }\r
 128 PROCEDURE APL_AB_buscar_externo( VAR a: AB_arbol; e: Tipo_Elem; VAR error: boolean );\r
 129         FUNCTION buscar_rec( VAR a: AB_arbol; e: Tipo_Elem): boolean;\r
 130         VAR\r
 131                 d: Tipo_Elem;\r
 132                 resultado: boolean;\r
 133         BEGIN\r
 134                 { proceso el nodo corriente }\r
 135                 AB_elem_cte( a, e);\r
 136                 resultado := Comparar_Elementos( e, d );\r
 137                 IF NOT resultado\r
 138                 THEN BEGIN\r
 139                         { no era el buscado }\r
 140          { proceso el subarbol izquierdo }\r
 141                         AB_mover_cte( a, AB_izquierda, error );\r
 142                         IF not error\r
 143                         THEN BEGIN\r
 144                                 resultado := buscar_rec( a, e );\r
 145                                 IF NOT resultado\r
 146                                 THEN BEGIN\r
 147                                         { proceso el subarbol izquierdo }\r
 148                                         AB_mover_cte( a, AB_padre, error );\r
 149                                         AB_mover_cte( a, AB_derecha, error );\r
 150                                         IF not error\r
 151                                         THEN BEGIN\r
 152                                                 resultado := buscar_rec( a, e );\r
 153                                                 IF NOT resultado\r
 154                                                 THEN\r
 155                                                         AB_mover_cte( a, AB_padre, error );\r
 156                                         END;\r
 157             END;\r
 158                         END;\r
 159                 END;\r
 160                 buscar_rec := resultado;                \r
 161         END;\r
 162 BEGIN\r
 163         { me voy a la raiz y desde allí proceso todo }\r
 164         AB_mover_cte( a, AB_raiz, error );\r
 165    error := buscar_rec( a, e );\r
 166 END;\r
 167 \r
 168 end.\r
 169 \r