Con el modelo de nodos definido en el tema anterior podemos concentrarnos en construir árboles binarios de distintas formas. Este capítulo cubre las inserciones iterativas, la carga desde listas, la generación balanceada y algunas rutas para recibir datos del usuario sin comprometer la integridad del árbol en Python.
Antes de escribir código conviene definir si los datos llegan ordenados, desordenados o en un flujo interactivo. De esto depende si necesitamos herramientas extra para balancear el árbol o si basta con aplicar la inserción secuencial.
Usaremos las mismas clases del tema 3 junto con las utilidades de inicialización y limpieza para comenzar desde un estado conocido.
class Nodo:
def __init__(self, valor, nivel=0):
self.valor = valor
self.izquierdo = None
self.derecho = None
self.nivel = nivel
class ArbolBinarioOrdenado:
def __init__(self):
self.raiz = None
self.cantidad = 0
def crear_nodo(self, valor, nivel=0):
return Nodo(valor, nivel=nivel)
def limpiar_arbol(self):
self.liberar_subarbol(self.raiz)
self.raiz = None
self.cantidad = 0
def liberar_subarbol(self, nodo):
if nodo is None:
return
self.liberar_subarbol(nodo.izquierdo)
self.liberar_subarbol(nodo.derecho)
nodo.izquierdo = None
nodo.derecho = None
Estas utilidades se reutilizan en cada variante de construcción, por lo que conviene mantenerlas en un módulo independiente del proyecto.
Partimos de la misma estructura del tema 3: el recorrido es iterativo, compara valores y enlaza el nuevo nodo al encontrar una referencia nula.
class ArbolBinarioOrdenado:
# ...
def insertar(self, valor):
if self.raiz is None:
self.raiz = self.crear_nodo(valor)
self.cantidad = 1
return self.raiz
actual = self.raiz
while True:
if valor < actual.valor:
if actual.izquierdo is None:
actual.izquierdo = self.crear_nodo(valor, nivel=actual.nivel + 1)
self.cantidad += 1
return actual.izquierdo
actual = actual.izquierdo
else:
if actual.derecho is None:
actual.derecho = self.crear_nodo(valor, nivel=actual.nivel + 1)
self.cantidad += 1
return actual.derecho
actual = actual.derecho
El nivel se calcula sumando uno al nivel del nodo padre, lo que simplifica recorridos posteriores.
La forma más rápida de poblar el árbol con datos desordenados es recorrer una lista y enviar cada valor a insertar. El método siguiente también reinicia el árbol cuando se indica.
class ArbolBinarioOrdenado:
# ...
def construir_desde_lista(self, valores, reiniciar=True):
if reiniciar:
self.limpiar_arbol()
for valor in valores:
self.insertar(valor)
Esta rutina es ideal para pruebas: basta con definir una lista de enteros y llamarla con reiniciar en True para descartar el contenido anterior.
Si la lista ya viene ordenada podemos crear un árbol balanceado seleccionando el elemento central como raíz y repitiendo el proceso en cada mitad. El resultado mantiene alturas similares entre los subárboles.
class ArbolBinarioOrdenado:
# ...
def _construir_balanceado_rec(self, valores, inicio, fin, nivel):
if inicio > fin:
return None
medio = (inicio + fin) // 2
nodo = self.crear_nodo(valores[medio], nivel=nivel)
nodo.izquierdo = self._construir_balanceado_rec(valores, inicio, medio - 1, nivel + 1)
nodo.derecho = self._construir_balanceado_rec(valores, medio + 1, fin, nivel + 1)
self.cantidad += 1
return nodo
def construir_balanceado(self, valores):
self.limpiar_arbol()
if not valores:
return True
self.cantidad = 0
self.raiz = self._construir_balanceado_rec(valores, 0, len(valores) - 1, 0)
return self.raiz is not None
El método devuelve True si pudo crear la estructura completa; en caso de fallo deja el árbol vacío para evitar estados inconsistentes.
Cuando los datos provienen de la entrada estándar debemos validar cada valor. El siguiente ejemplo solicita enteros hasta que el usuario ingresa 0:
def cargar_interactivo(arbol):
while True:
try:
valor = int(input("Ingrese un entero (0 para terminar): "))
except ValueError:
print("Entrada invalida, cancelando.")
break
if valor == 0:
break
arbol.insertar(valor)
Este patrón se adapta a cualquier fuente de datos mientras podamos convertir la entrada a entero.
Para comprobar que la construcción fue correcta conviene implementar al menos un recorrido en preorden y otro en inorden.
def imprimir_preorden(nodo):
if nodo is None:
return
print(f"{nodo.valor} (nivel {nodo.nivel})")
imprimir_preorden(nodo.izquierdo)
imprimir_preorden(nodo.derecho)
def imprimir_inorden(nodo):
if nodo is None:
return
imprimir_inorden(nodo.izquierdo)
print(nodo.valor, end=" ")
imprimir_inorden(nodo.derecho)
El recorrido inorden de un árbol de búsqueda binaria debería producir una secuencia ordenada ascendentemente; si no ocurre, la construcción contiene errores.
Juntando todo podemos construir un árbol con datos desordenados, revisarlo y luego reemplazarlo por una versión balanceada:
def demo_construccion():
arbol = ArbolBinarioOrdenado()
datos = [10, 5, 20, 3, 7, 15]
arbol.construir_desde_lista(datos)
print("Preorden original:")
arbol.imprimir_preorden(arbol.raiz)
ordenados = [2, 4, 6, 8, 12, 16, 18]
arbol.construir_balanceado(ordenados)
print("\\nPreorden balanceado:")
arbol.imprimir_preorden(arbol.raiz)
arbol.limpiar_arbol()El ejemplo anterior permite comparar la distribución de niveles antes y después de balancear.
El siguiente archivo integra todas las funciones y crea dos árboles: uno con inserciones secuenciales y otro balanceado a partir de una lista ordenada.
class Nodo:
def __init__(self, valor, nivel=0):
self.valor = valor
self.izquierdo = None
self.derecho = None
self.nivel = nivel
class ArbolBinarioOrdenado:
def __init__(self):
self.raiz = None
self.cantidad = 0
def crear_nodo(self, valor, nivel=0):
return Nodo(valor, nivel=nivel)
def insertar(self, valor):
if self.raiz is None:
self.raiz = self.crear_nodo(valor)
self.cantidad = 1
return self.raiz
actual = self.raiz
while True:
if valor < actual.valor:
if actual.izquierdo is None:
actual.izquierdo = self.crear_nodo(valor, nivel=actual.nivel + 1)
self.cantidad += 1
return actual.izquierdo
actual = actual.izquierdo
else:
if actual.derecho is None:
actual.derecho = self.crear_nodo(valor, nivel=actual.nivel + 1)
self.cantidad += 1
return actual.derecho
actual = actual.derecho
def construir_desde_lista(self, valores, reiniciar=True):
if reiniciar:
self.limpiar_arbol()
for valor in valores:
self.insertar(valor)
def _construir_balanceado_rec(self, valores, inicio, fin, nivel):
if inicio > fin:
return None
medio = (inicio + fin) // 2
nodo = self.crear_nodo(valores[medio], nivel=nivel)
nodo.izquierdo = self._construir_balanceado_rec(valores, inicio, medio - 1, nivel + 1)
nodo.derecho = self._construir_balanceado_rec(valores, medio + 1, fin, nivel + 1)
self.cantidad += 1
return nodo
def construir_balanceado(self, valores):
self.limpiar_arbol()
if not valores:
return True
self.cantidad = 0
self.raiz = self._construir_balanceado_rec(valores, 0, len(valores) - 1, 0)
return self.raiz is not None
def imprimir_preorden(self, nodo):
if nodo is None:
return
print(f"{nodo.valor} (nivel {nodo.nivel})")
self.imprimir_preorden(nodo.izquierdo)
self.imprimir_preorden(nodo.derecho)
def liberar_subarbol(self, nodo):
if nodo is None:
return
self.liberar_subarbol(nodo.izquierdo)
self.liberar_subarbol(nodo.derecho)
nodo.izquierdo = None
nodo.derecho = None
def limpiar_arbol(self):
self.liberar_subarbol(self.raiz)
self.raiz = None
self.cantidad = 0
def imprimir_inorden(nodo):
if nodo is None:
return
imprimir_inorden(nodo.izquierdo)
print(nodo.valor, end=" ")
imprimir_inorden(nodo.derecho)
if __name__ == "__main__":
arbol = ArbolBinarioOrdenado()
datos = [10, 5, 20, 3, 7, 15]
arbol.construir_desde_lista(datos)
print("Arbol generado con inserciones secuenciales:")
arbol.imprimir_preorden(arbol.raiz)
print("Inorden:")
imprimir_inorden(arbol.raiz)
print()
ordenados = [2, 4, 6, 8, 12, 16, 18]
if arbol.construir_balanceado(ordenados):
print("\nArbol balanceado:")
arbol.imprimir_preorden(arbol.raiz)
print("Inorden:")
imprimir_inorden(arbol.raiz)
print()
else:
print("No se pudo construir el arbol balanceado.")
arbol.limpiar_arbol()