• Entre dos nodos cualesquiera, existe un único camino que los conecta.
• Un árbol con n nodos posee exactamente n-1 aristas.
• No contienen ciclos.

A continuación se ilustran conceptos clave:

• Nodo: Elemento individual del árbol.
• Raíz: Nodo sin ancestros, como A en el ejemplo.
• Padre: Nodo con hijos; por ejemplo, B es padre de D y E.
• Hijos: Nodos descendientes dierctos; D e H son hijos de B y C, respectivamente.
• Hermanos: Nodos que comparten el mismo padre, como D y E.
• Hojas: Nodos sin descendencia, tales como D, F, H e I.
• Altura de un nodo: Longitud del camino más largo hasta una hoja.
• Profundidad: Distancia desde la raíz al nodo.
• Nivel: Profundidad más uno.
• Altura del árbol: Altura de la raíz.

Clasificación de los árboles binarios

Un árbol binario es aquel donde cada nodo tiene como máximo dos hijos, denominados izquierdo y derecho, con un orden establecido.

En el nivel i, un árbol binario puede contener hasta 2i-1 nodos. Un árbol de altura k tiene entre 2k y 2k+1-1 nodos.

Árbol binario completo

Es aquel donde todos los niveles están llenos, excepto posiblemente el último, que se completa de iqzuierda a derecha. Esta propiedad permite un almacenamiento eficiente en arreglos, ya que si un nodo está en el índice i, sus hijos se encuentran en 2i y 2i+1.

Árbol binario lleno

Cada nivel posee el máximo número de nodos posible, resultando en un total de 2k+1-1 nodos para un árbol de altura k.

Árbol binario balanceado

Es un árbol de búsqueda donde la diferencia de altura entre subárboles izquierdo y derecho no excede uno. Ejemplos comunes incluyen árboles AVL y árboles rojo-negro. Su objetivo es evitar la degradación a una lista enlazada, manteniendo operaciones eficientes.

Almacenamiento de árboles binarios

Almacenamiento enlazado

Utiliza punteros o referencias para conectar nodos. Cada nodo almacena datos y referencias a sus hijos izquierdo y derecho. Este método es flexible pero consume más memoria por nodo.

Almacenamiento secuencial

Emplea un arreglo donde el nodo raíz ocupa el índice 1. Para un nodo en el índice i, su hijo izquierdo está en 2i y el derecho en 2i+1. Es eficiente para árboles completos, pero desperdicia espacio en árboles irregulares.

Recorridos de árboles binarios

Recorrido en preorden

Visita primero la raíz, luego el subárbol izquierdo y finalmente el derecho. Implementación recursiva en Java:

public void preOrdenRecursivo(Nodo nodoActual) {
    if (nodoActual == null) return;
    System.out.print(nodoActual.valor + " ");
    preOrdenRecursivo(nodoActual.hijoIzq);
    preOrdenRecursivo(nodoActual.hijoDer);
}

Recorrido en inorden

Recorre primero el subárbol izquierdo, luego la raíz, y finalmente el derecho. Para árboles de búsqueda, produce valores ordenados.

public void inOrdenRecursivo(Nodo subArbol) {
    if (subArbol == null) return;
    inOrdenRecursivo(subArbol.hijoIzq);
    System.out.print(subArbol.valor + " ");
    inOrdenRecursivo(subArbol.hijoDer);
}

Recorrido en postorden

Procesa los subárboles izquierdo y derecho antes que la raíz. Útil para operaciones como la eliminación de nodos.

public void postOrdenRecursivo(Nodo nodo) {
    if (nodo == null) return;
    postOrdenRecursivo(nodo.hijoIzq);
    postOrdenRecursivo(nodo.hijoDer);
    System.out.print(nodo.valor + " ");
}