Teoría Fundamental de Árbores Binarios:
Árbol Binario Completo:
Un árbol binario completo tiene exactamente 2^k - 1 nodos, donde k es la profundidad del árbol.
Árbol Binari Casi Completo:
El último nivel puede no estar completamente lleno, pero si un nodo tiene hijo derecho, también debe tener hijo izquierdo.
Árbol Binario de Búsqueda:
Todos los nodos en el subárbol izquierdo de un nodo tienen valores menores que el nodo, y todos los nodos en el subárbol derecho tienen valores mayores.
Árbol Binario de Búsqueda Equilibrado:
La diferencia de altura entre el subárbol izquierdo y derecho de cualquier nodo no puede superar 1.
Métodos de Almacenamiento: Almacenamiento lineal / Almacenamiento enlazado
Recorrido de Árboles (Recursivo/Iterativo):
Tres Pasos de la Recursión:
- Determinar los parámetros y valores de retorno de la función recursiva
- Determinar la condición de terminación
I. Recorridos en Preorden, Inorden y Postorden (Método Recursivo)
Basado en las características de cada recorrido:
- Preorden: Nodo actual, subárbol izquierdo, subárbol derecho
- Inorden: Subárbol izquierdo, nodo actual, subárbol derecho
- Postorden: Subárbol izquierdo, subárbol derecho, nodo actual
Tomando como ejemplo el recorrido en preorden:
Primero debemos mostrar el valor del nodo actual, luego realizar llamadas recursivas para el hijo izquierdo y el hijo derecho.
Código:
public List<Integer> recorrerArbol(NodoArbol raiz) {
List<Integer> lista = new ArrayList<>();
transversal(raiz, lista);
return lista;
}
public void transversal(NodoArbol nodo, List<Integer> lista) {
if(nodo == null) return;
lista.add(nodo.valor);
transversal(nodo.izquierda, lista);
transversal(nodo.derecha, lista);
}
II. Recorridos en Preorden, Inorden y Postorden (Método Iterativo)
La lógica para recorridos en preorden y postorden es similar (en el preorden, cuando visitamos un nodo, lo añadimos al resultado; el postorden puede derivarse del preorden mediante una transformación específica). Sin embargo, el recorrido en inorden requiere llegar siempre al nodo más izquierdo antes de procesar el nodo actual.
Recorrido en preorden: Utilizamos una pila, introducimos el nodo raíz, lo extraemos (procesando el nodo actual), luego añadimos sus hijos derecho e izquierdo a la pila en ese orden. Así, el elemento en la cima de la pila será el hijo izquierdo.
// Definimos una pila para almacenar nodos del árbol
Stack<NodoArbol> pila = new Stack<>();
// Definimos una colección para almacenar los resultados del recorrido
List<Integer> lista = new ArrayList<>();
if(raiz == null) return lista;
pila.push(raiz);
while(!pila.isEmpty()){
NodoArbol nodo = pila.pop();
lista.add(nodo.valor);
if(nodo.izquierda != null) pila.push(nodo.izquierda);
if(nodo.derecha != null) pila.push(nodo.derecha);
}
Recorrido en postorden: Se basa en el preorden pero cambiando el orden de inserción de los hijos (primero izqiuerdo, luego derecho) y finalmente invirtiendo el resultado.
Recorrido en inorden:
Avanzamos siempre hacia la izquierda hasta encontrar un nodo nulo. En ese caso, extraemos el elemento de la cima de la pila (procesando el nodo actual) y luego nos movemos a su hijo derecho.
public List<Integer> recorridoInorden(NodoArbol raiz) {
List<Integer> lista = new ArrayList<>();
if(raiz == null) return lista;
Stack<NodoArbol> pila = new Stack<>();
NodoArbol actual = raiz;
while(actual != null || !pila.isEmpty()){
if(actual != null){
pila.push(actual);
actual = actual.izquierda;
}
else{
actual = pila.pop();
lista.add(actual.valor);
actual = actual.derecha;
}
}
return lista;
}
III. Recorrido por Niveles de un Árbol Binario
Utilizamos una Deque como estructura de datos, con un valor de retorno de List>, donde cada List contiene los datos de un nivel específico.
El número de elementos que introducimos en la cola determina su tamaño. El orden de entrada y salida sigue el principio FIFO (primero en entrar, primero en salir). Durante el ciclo de procesamiento de un nivel, añadimos nuevos elementos (hasta 2n elementos). Una vez procesado un nivel completo, recalculamos el tamaño de la cola y procedemos a procesar el siguiente nivel.
public List<List<Integer>> recorridoPorNiveles(NodoArbol raiz) {
List<List<Integer>> listas = new ArrayList<>();
Queue<NodoArbol> cola = new ArrayDeque<>();
if(raiz != null){
cola.add(raiz);
}
while(!cola.isEmpty()){
int tamaño = cola.size();
List<Integer> lista = new ArrayList<>();
while(tamaño-- > 0){
NodoArbol nodo = cola.poll();
lista.add(nodo.valor);
if(nodo.izquierda != null) cola.add(nodo.izquierda);
if(nodo.derecha != null) cola.add(nodo.derecha);
}
listas.add(lista);
}
return listas;
}
IV. Espejo de un Árbol Binario
Utilizamos un método recursivo: los tres pasos de la recursión: determinar parámetros y valores de retorno, definir condiciones de terminación, y establecer la lógica recursiva.
Primero intercambiamos los hijos izquierdo y derecho del nodo raíz mediante una función intercambiar(NodoArbol nodo). Luego aplicamos recursivamente al hijo izquierdo y después al hijo derecho, siguiendo un patrón de preorden. Para un postorden, simplemente colocaríamos la función intercambiar al final.
Nota: En el caso de un recorrido inorden (izquierda-actual-derecha), primero intercambiamos los hijos del nodo izquierdo, luego los del nodo actual, pero esto altera el orden original. Por lo tanto, se requiere un tercer intercambio en el hijo izquierdo del nodo actual.
Código:
public NodoArbol arbolEspejo(NodoArbol raiz) {
return invertirArbol(raiz);
}
/**
Tres pasos de la recursión
1. Determinar parámetros y valores de retorno
2. Definir condición de terminación
3. Establecer lógica recursiva
**/
public NodoArbol invertirArbol(NodoArbol nodo){
if(nodo == null) return nodo;
// Recursivamente invertir los subárboles
invertirArbol(nodo.izquierda);
intercambiar(nodo);
invertirArbol(nodo.izquierda);
return nodo;
}
public void intercambiar(NodoArbol nodo){
NodoArbol temp = nodo.izquierda;
nodo.izquierda = nodo.derecha;
nodo.derecha = temp;
}
V. Árbol Binario Simétrico
Mi enfoque inicial para determinar si un árbol era simétrico se basaba en: realizar un recorrido inorden y comparar los elementos desde el centro hacia ambos lados. Sin embargo, no consideré el caso de nodos nulos, que no pueden almacenarse en una colección.
Por lo tanto, siguiendo el enfoque de un experto, para determinar si un árbol es simétrico, debemos comparar pares de nodos simétricos. Existen cuatro casos:
- Hijo izquierdo nulo, hijo derecho no nulo
- Hijo izquierdo no nulo, hijo derecho nulo
- Ambos hijos nulos
- Valores de los nodos diferentes
Si ambos son nulos, podemos devolver true directamente. En el caso de valores iguales, procedemos a comparar los subárboles.
Al comparar subárboles, debemos verificar las combinaciones: hijo izquierdo del nodo izquierdo con hijo derecho del nodo derecho, y viceversa.
Código:
public boolean esSimetrico(NodoArbol raiz) {
return sonEspejos(raiz.izquierda, raiz.derecha);
}
public boolean sonEspejos(NodoArbol izq, NodoArbol der){
// Hijo izquierdo nulo, hijo derecho no nulo
if(izq == null && der != null) return false;
// Hijo izquierdo no nulo, hijo derecho nulo
if(izq != null && der == null) return false;
// Ambos nulos
if(izq == null && der == null) return true;
// Valores diferentes
if(izq.valor != der.valor) return false;
boolean izquierda = sonEspejos(izq.izquierda, der.derecha); // Comparar izquierdas con derechas
boolean derecha = sonEspejos(izq.derecha, der.izquierda); // Comparar derechas con izquierdas
return izquierda && derecha;
}
VI. Cálculo de la Profundidad de un Árbol Binario (Recorrido por Niveles/Recursivo)
Recorrido por Niveles (ya explicado anteriormente, no se detalla nuevamente)
public int calcularProfundidad(NodoArbol raiz) {
// Usando recorrido por niveles
// Creamos una cola para almacenar nodos
Queue<NodoArbol> cola = new ArrayDeque<>();
// Creamos listas para almacenar resultados por nivel
List<List<Integer>> listas = new ArrayList<>();
if(raiz != null) cola.add(raiz);
while(!cola.isEmpty()){
int tamaño = cola.size();
List<Integer> lista = new ArrayList<>();
while(tamaño-- > 0){
NodoArbol nodo = cola.poll();
lista.add(nodo.valor);
if(nodo.izquierda != null) cola.add(nodo.izquierda);
if(nodo.derecha != null) cola.add(nodo.derecha);
}
listas.add(lista);
}
return listas.size();
}
Método Recursivo: La lógica es que la altura de cada nodo es max(altura(subárbol_izquierdo), altura(subárbol_derecho)) + 1.
Tres pasos de la recursión:
- Valor de retorno: int (altura), parámetro: nodo
- Condición de terminación: nodo == null
- Lógica recursiva:
obtenerAltura(NodoArbol nodo){
if(nodo == null) return 0;
return Math.max(obtenerAltura(nodo.izquierda), obtenerAltura(nodo.derecha)) + 1;
}
VII. Cálculo de la Altura Mínima de un Árbol Binario (Recorrido por Niveles/Recursivo)
Recursivo:
Nota: La altura mínima se define como la longitud del camino más corto desde el nodo raíz hasta el nodo hoja más cercano. Los nodos hoja deben ser no nulos.
Método recursivo:
public int profundidadMinima(NodoArbol raiz) {
return obtenerAlturaMinima(raiz);
}
public int obtenerAlturaMinima(NodoArbol nodo) {
if (nodo == null)
return 0;
int alturaIzquierda = obtenerAlturaMinima(nodo.izquierda);
int alturaDerecha = obtenerAlturaMinima(nodo.derecha);
if (nodo.izquierda == null) {
return alturaDerecha + 1;
}
if (nodo.derecha == null) {
return alturaIzquierda + 1;
}
return Math.min(alturaIzquierda, alturaDerecha) + 1;
}
Recorrido por Niveles:
La idea general: durante el recorrido por niveles, si encontramos un nodo que no tiene hijos, la distancia desde la raíz hasta este nodo es la altura mínima.
Código:
public int profundidadMinima(NodoArbol raiz) {
// Recorrido por niveles: si encontramos un nodo sin hijos, devolvemos el nivel actual
Queue<NodoArbol> cola = new ArrayDeque<>();
if (raiz == null)
return 0;
List<List<Integer>> listas = new ArrayList<>();
cola.add(raiz);
int distancia = 0;
while (!cola.isEmpty()) {
int tamaño = cola.size();
List<Integer> lista = new ArrayList<>();
while (tamaño-- > 0) {
NodoArbol nodo = cola.poll();
lista.add(nodo.valor);
boolean esHoja = esNodoHoja(nodo);
if (esHoja) {
return listas.size() + 1;
}
if(nodo.izquierda != null) cola.add(nodo.izquierda);
if(nodo.derecha != null) cola.add(nodo.derecha);
}
listas.add(lista);
}
return 0;
}
public boolean esNodoHoja(NodoArbol nodo) {
if (nodo.izquierda == null && nodo.derecha == null)
return true;
else
return false;
}
VIII. Conteo de Nodos en un Árbol Binario Casi Completo (Recorrido por Niveles/Utilizando Propiedades de Árboles Binarios Completos)
Recorrido por Niveles: Recorremos cada nivel y sumamos los elementos, devolviendo el total total.
Utilizando propiedades de árboles binarios completos:
Tres pasos de la recursión:
- Parámetro: NodoArbol nodo, valor de retorno: int
- Cuando nodo == null, devuelve 0; si el subárbol es un árbol binario completo, devuelve 2 << alturaIzquierda - 1
- Lógica recursiva: si no se cumple, la función recursiva devuelve conteo(subárbol_izquierdo) + conteo(subárbol_derecho) + 1
Luego buscamos en los subárboles si alguno cumple con la propiedad de árbol binario completo.
Código:
public int contarNodos(NodoArbol raiz) {
if (raiz == null)
return 0;
NodoArbol izquierda = raiz.izquierda;
NodoArbol derecha = raiz.derecha;
int alturaIzquierda = 0;
int alturaDerecha = 0;
while(izquierda != null){
alturaIzquierda++;
izquierda = izquierda.izquierda;
}
while(derecha != null){
alturaDerecha++;
derecha = derecha.derecha;
}
if(alturaIzquierda == alturaDerecha){
return (2 << alturaIzquierda) - 1;
}
return contarNodos(raiz.izquierda) + contarNodos(raiz.derecha) + 1;
}
IX. Árbol Binario Equilibrado (Método Recursivo/Iteratiov)
Árbol Binario: La diferencia de altura entre los subárboles izquierdo y derecho de cualquier nodo debe ser ≤ 1.
Método Recursivo:
La función recursiva devuelve un int, con parámetro NodoArbol raiz
Condición de terminación: nodo == null
Lógica recursiva:
- Si en algún subárbol la diferencia de altura > 1, no es un árbol binario equilibrado, devuelve -1
- Si la diferencia de altura del nodo actual > 1, no es equilibrado, devuelve -1
- Si ambos subárboles cumplen, devuelve la altura máxima de los subárboles + 1