Profundizamos en cada pieza que forma un árbol binario: cómo se representa el nodo, qué rol cumplen la raíz y las hojas, y cómo medir niveles, alturas y grados para programar operaciones seguras. Estos cimientos nos acompañarán durante todo el tutorial en Python.
El nodo es una clase simple que almacena el valor y las referencias a sus dos hijos. Mantenerlas inicializadas en None evita estados indefinidos y facilita detectar hojas.
class Nodo:
def __init__(self, valor, nivel=0):
self.valor = valor
self.izquierdo = None
self.derecho = None
self.nivel = nivel
def crear_nodo(valor, nivel=0):
return Nodo(valor, nivel=nivel)
El campo nivel almacena la profundidad relativa del nodo; lo actualizaremos al enlazarlo con su padre.
La raíz es el punto de entrada para cualquier operación. Si la raíz vale None, el árbol está vacío. Conviene encapsular este dato en una clase contenedora junto con el conteo de nodos.
class ArbolBinario:
def __init__(self):
self.raiz = None
self.cantidad = 0
def esta_vacio(arbol):
return arbol.raiz is None
Con este contenedor podemos comprobar si el árbol está vacío antes de insertar o recorrer, evitando accesos a referencias nulas.
Los hijos izquierdo y derecho conectan cada nodo con sus subárboles. Un nodo es una hoja si carece de hijos. Identificarlas permite saber dónde insertar nuevos valores o cómo recorrer el árbol de abajo hacia arriba.
def es_hoja(nodo):
return nodo is not None and nodo.izquierdo is None and nodo.derecho is None
El resto de enlaces se actualiza al crear hijos. Mantener esta relación coherente es clave para los recorridos recursivos.
El nivel indica cuántas aristas separan un nodo de la raíz. Cuando insertamos un hijo, basta con sumar 1 al nivel del padre para conservar la información actualizada.
def crear_hijo(padre, valor, es_izquierdo=True):
nivel_hijo = 0 if padre is None else padre.nivel + 1
hijo = Nodo(valor, nivel=nivel_hijo)
if padre:
if es_izquierdo:
padre.izquierdo = hijo
else:
padre.derecho = hijo
return hijo
Con la profundidad almacenada en cada nodo podemos visualizar el árbol, limitar la exploración o implementar algoritmos como minimax.
La altura corresponde al nivel máximo alcanzado por cualquier nodo. Calcularla deja clara la forma del árbol y es un indicador del costo de búsqueda.
def altura(nodo):
if nodo is None:
return -1 # arbol vacio
izquierda = altura(nodo.izquierdo)
derecha = altura(nodo.derecho)
return 1 + max(izquierda, derecha)
El tamaño total del árbol se mantiene en ArbolBinario.cantidad, incrementándolo al crear nodos y decrementándolo al eliminarlos.
El grado indica cuántos hijos inmediatos posee un nodo. En árboles binarios solo puede ser 0, 1 o 2. Controlarlo sirve para verificar que ninguna rutina rompa las reglas de la estructura.
def grado(nodo):
if nodo is None:
return 0
g = 0
if nodo.izquierdo is not None:
g += 1
if nodo.derecho is not None:
g += 1
return g
Las hojas tienen grado 0 y los nodos internos 1 o 2. Este dato guía las funciones de inserción, eliminación y balanceo.
Conocer estos componentes nos permite inspeccionar el árbol en cualquier punto: sabemos si está vacío, cuántos nodos contiene, dónde están las hojas y cuál es su altura. Estos diagnósticos evitan bugs cuando avancemos hacia el modelado de nodos y la construcción del árbol en Python.