Ahora que conocemos los recorridos y las operaciones básicas, es momento de modificar la estructura del árbol general: agregar y quitar nodos de forma segura, reorganizar enlaces y mantener referencias consistentes en Python.
class Nodo:
def __init__(self, valor):
self.valor = valor
self.primer_hijo = None
self.siguiente_hermano = None
self.padre = NoneLa inserción de un hijo en la representación hijo-izquierdo/hermano-derecho se realiza colocando el nuevo nodo al comienzo de la lista de hijos del padre. Esto mantiene la operación en O(1) y permite preservar el orden con una rutina posterior si fuera necesario.
class ArbolGeneral:
def __init__(self):
self.raiz = None
def insertar_hijo(self, padre, valor):
if padre is None:
return None
nuevo = Nodo(valor)
nuevo.padre = padre
nuevo.siguiente_hermano = padre.primer_hijo
padre.primer_hijo = nuevo
return nuevoPara mantener el orden o insertar un nodo en medio de la lista horizontal, creamos una función que se apoya en el puntero siguienteHermano.
class ArbolGeneral:
...
def insertar_hermano_despues(self, referencia, valor):
if referencia is None:
return None
nuevo = Nodo(valor)
nuevo.padre = referencia.padre
nuevo.siguiente_hermano = referencia.siguiente_hermano
referencia.siguiente_hermano = nuevo
return nuevoSi necesitamos insertar antes de un hermano específico conservamos los punteros en una función auxiliar que recorra el listado hasta encontrar el anterior.
Para eliminar una hoja basta con ajustar el puntero del padre y soltar la referencia. Este procedimiento se implementa registrando el hijo previo durante el recorrido de hermanos.
class ArbolGeneral:
...
def eliminar_hoja(self, hoja):
if hoja is None or hoja.primer_hijo is not None:
return False
padre = hoja.padre
if padre is None:
if self.raiz == hoja:
self.raiz = None
return True
anterior = None
actual = padre.primer_hijo
while actual and actual != hoja:
anterior = actual
actual = actual.siguiente_hermano
if actual is None:
return False
if anterior:
anterior.siguiente_hermano = actual.siguiente_hermano
else:
padre.primer_hijo = actual.siguiente_hermano
hoja.padre = None
hoja.siguiente_hermano = None
return TrueCuando el nodo a eliminar tiene descendencia, debemos desconectarlo del padre y limpiar el subárbol completo. Este patrón recursivo es similar al recorrido postorden.
class ArbolGeneral:
...
def _desconectar_de_padre(self, nodo):
if nodo is None or nodo.padre is None:
return
padre = nodo.padre
anterior = None
actual = padre.primer_hijo
while actual and actual != nodo:
anterior = actual
actual = actual.siguiente_hermano
if actual is None:
return
if anterior:
anterior.siguiente_hermano = actual.siguiente_hermano
else:
padre.primer_hijo = actual.siguiente_hermano
nodo.padre = None
nodo.siguiente_hermano = None
def _limpiar_subarbol(self, nodo):
if nodo is None:
return
hijo = nodo.primer_hijo
while hijo:
siguiente = hijo.siguiente_hermano
self._limpiar_subarbol(hijo)
hijo = siguiente
nodo.primer_hijo = None
nodo.siguiente_hermano = None
nodo.padre = None
def eliminar_nodo(self, nodo):
if nodo is None:
return
if nodo == self.raiz:
self.raiz = None
else:
self._desconectar_de_padre(nodo)
self._limpiar_subarbol(nodo)Reubicar un subárbol implica desconectarlo de su padre actual y volver a enlazarlo bajo el nuevo padre. Conviene encapsular esta operación para garantizar que el puntero padre y los hermanos se actualicen correctamente.
class ArbolGeneral:
...
def _es_ancestro(self, nodo, posible_ancestro):
actual = nodo
while actual:
if actual == posible_ancestro:
return True
actual = actual.padre
return False
def mover_subarbol(self, nodo, nuevo_padre):
if nodo is None or nuevo_padre is None or nodo == nuevo_padre:
return False
if self._es_ancestro(nuevo_padre, nodo):
return False
self._desconectar_de_padre(nodo)
nodo.padre = nuevo_padre
nodo.siguiente_hermano = nuevo_padre.primer_hijo
nuevo_padre.primer_hijo = nodo
return TrueAntes de mover nodos verifica que no generes ciclos (por ejemplo, asignando un nodo como hijo de uno de sus descendientes).
Cuando el árbol ya no se necesita conviene borrar la referencia a la raíz y limpiar las conexiones si estamos reutilizando nodos. La siguiente versión usa una pila para recorrer sin recursión y deja cada nodo desconectado.
class ArbolGeneral:
...
def liberar_arbol(self):
if self.raiz is None:
return
pila = [self.raiz]
while pila:
actual = pila.pop()
hijo = actual.primer_hijo
while hijo:
pila.append(hijo)
hijo = hijo.siguiente_hermano
actual.primer_hijo = None
actual.siguiente_hermano = None
actual.padre = None
self.raiz = NoneEn Python el recolector de basura liberará la memoria cuando no existan referencias a los nodos.
padre: genera inconsistencias al calcular profundidades o mover subárboles.Adoptar pruebas unitarias simples que inserten, muevan y eliminen nodos ayuda a detectar estos errores antes de que el árbol crezca en el proyecto real.