• Un árbol binario es un árbol cuyos nodos contienen dos enlaces. El nodo raíz es el primer nodo en un árbol.
• Cada enlace en el nodo raíz hace referencia a un hijo. El hijo izquierdo es el primer nodo en el subárbol izquierdo, 

y el hijo derecho es el primer nodo en el subárbol derecho.

• Los hijos de un nodo se llaman hermanos. Un nodo sin hijos se llama nodo hoja.
• En un árbol de búsqueda binaria sin valores de nodo duplicados, los valores en cualquier subárbol izquierdo son 

menores que el valor en su nodo padre, y los valores en cualquier subárbol derecho son mayores que el valor en su 
nodo padre.  En un árbol de búsqueda binaria, un nodo puede insertarse solamente como nodo hoja.

• El recorrido inorden de un árbol de búsqueda binaria procesa los valores de los nodos en orden ascendente.
• En un recorrido preorden, el valor en cada uno de los nodos se procesa a medida que se van visitando. Después se 

procesan los valores en el subárbol izquierdo y, por último, los valores en el subárbol derecho.

• En un recorrido postorden, el valor en cada uno de los nodos se procesa después de los valores de sus hijos.
• El árbol de búsqueda binaria facilita la eliminación de valores duplicados. Al crear un árbol se reconocen 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, eventualmente se compara el valor duplicado con un 
nodo que contenga el mismo valor. El valor duplicado puede descartarse en este punto.

• Buscar en un árbol binario un valor que concuerde con una clave es también un proceso rápido, especialmente para 

los árboles estrechamente empaquetados. En un árbol estrechamente empaquetado, cada nivel contiene aproxi-
madamente el doble de elementos que el nivel anterior. Por lo tanto, un árbol de búsqueda binaria estrechamente 
empaquetado con 

n elementos tiene log

2

n niveles, por lo que tendrían que hacerse cuando mucho log

2

n com-

paraciones 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 búsqueda binaria de 1,000,000 de elementos (estrechamente empaquetado) 

requiere cuando mucho de 20 comparaciones, ya que 2

20

 > 1,000,000.

Terminología

algoritmos recursivos para recorrer árboles 
árbol
árbol balanceado
árbol binario
árbol de búsqueda binaria
árbol empaquetado
autoboxing
autounboxing

Boolean

, clase

Byte

, clase

clase autorreferenciada
clases de envoltura de tipos
cola
conversión boxing
conversión unboxing

Character

, clase

delegar la llamada a un método
dequeue
eliminación de valores duplicados
eliminar un nodo
enqueue
estructura de datos lineal
estructura de datos no lineal
estructura dinámica de datos

Float

, clase

hijo derecho
hijo izquierdo
hijos de un nodo
insertar un nodo

Integer

, clase

lista enlazada

Long

, clase

método predicado
nodo 
nodo hijo
nodo hoja
nodo padre
nodo raíz

null

, referencia

ordenamiento de árboles binarios

OutOfMemoryError

parte fi nal de una cola
parte inicial (cabeza) de una cola
parte superior de una pila
PEPS (primero en entrar, primero en salir)
pila
pila de ejecución del programa
pop
push
recorrido
recorrido en orden de niveles de un árbol binario
recorrido inorden de un árbol binario
recorrido postorden de un árbol binario
recorrido preorden de un árbol binario

Short

, clase

subárbol
subárbol derecho
subárbol izquierdo
UEPS (último en entrar, primero en salir)
visitar un nodo

Terminología 

741

17_MAQ_CAP_17_DEITEL.indd741

4/19/081:30:11AM