738
Capítulo 17 Estructuras de datos
El método
ayudanteInorden
(líneas 87 a 95) defi ne los pasos para un recorrido inorden:
1.
Recorrer el subárbol izquierdo con una llamada a
ayudanteInorden
(línea 92).
2.
Procesar el valor en el nodo (línea 93).
3.
Recorrer el subárbol derecho con una llamada a
ayudanteInorden
(línea 94).
El recorrido inorden no procesa el valor en un nodo sino hasta que se procesan los valores en el subárbol izquierdo
de ese nodo. El recorrido inorden del árbol de la fi gura 17.19 es:
6 13 17 27 33 42 48
Observe que el recorrido inorden de un árbol de búsqueda binaria imprime los valores de los nodos en orden
ascendente. El proceso de crear un árbol de búsqueda binaria ordena los datos de antemano; por lo tanto, a este
proceso se le conoce como
ordenamiento de árbol binario
.
El método
ayudantePreorden
(líneas 70 a 78) defi ne los pasos para un recorrido preorden:
1.
Procesar el valor en el nodo (línea 75).
2.
Recorrer el subárbol izquierdo con una llamada a
ayudantePreorden
(línea 76).
3.
Recorrer el subárbol derecho con una llamada a
ayudantePreorden
(línea 77).
El recorrido preorden procesa el valor en cada uno de los nodos, a medida que se van visitando. Después de pro-
cesar el valor en un nodo dado, el recorrido preorden procesa los valores en el subárbol izquierdo y después los
valores en el subárbol derecho. El recorrido preorden del árbol de la fi gura 17.19 es:
27 13 6 17 42 33 48
El método
ayudantePostorden
(líneas 104 a 112) defi ne los pasos para un recorrido postorden:
1.
Recorrer el subárbol izquierdo con una llamada a
ayudantePostorden
(línea 109).
2.
Recorrer el subárbol derecho con una llamada a
ayudantePostorden
(línea 110).
3.
Procesar el valor en el nodo (línea 111).
El recorrido postorden procesa el valor en cada nodo después de procesar los valores de todos los hijos de ese
nodo. El
recorridoPostorden
del árbol de la fi gura 17.19 es:
6 17 13 33 48 42 27
El árbol de búsqueda binaria facilita la
eliminación de valores duplicados
. Al crear un árbol, la operación
de inserción reconoce los intentos de insertar un valor duplicado, ya que éste sigue las mismas decisiones de “ir a
la izquierda” o “ir a la derecha” en cada comparación, al igual que el valor original. Por lo tanto, la operación de
inserción eventualmente comparará el valor duplicado con un nodo que contenga el mismo valor. En este punto,
la operación de inserción puede decidir descartar el valor duplicado (como lo hicimos en este ejemplo).
Buscar en un árbol binario un valor que concuerde con una clave es un proceso rápido, especialmente
para los árboles
estrechamente empaquetados
(o
balanceados
). En un árbol estrechamente empaquetado, cada
nivel contiene aproximadamente el doble de elementos que el nivel anterior. La fi gura 17.19 es un árbol binario
estrechamente empaquetado. Un árbol de búsqueda binaria estrechamente empaquetado con
n elementos tiene
log
2
n niveles. Por lo tanto, se requieren cuando mucho log
2
n comparaciones para encontrar una concordancia o
determinar que no existe una. La búsqueda en un árbol de búsqueda binaria de 1000 elementos (estrechamente
empaquetado) requiere cuando mucho de 10 comparaciones, ya que 2
10
> 1000. La búsqueda en un árbol de
Figura 17.19
| Árbol de búsqueda binaria con siete valores.
27
13
617
33
48
42
17_MAQ_CAP_17_DEITEL.indd738
4/19/081:30:10AM