6.6. Nodos y referencias¶
Nuestro segundo método para representar un árbol utiliza nodos y referencias. En este caso definiremos una clase que tiene atributos para el valor raíz, así como para los subárboles izquierdo y derecho. Dado que esta representación sigue más de cerca el paradigma de programación orientado a objetos, continuaremos usando esta representación para el resto del capítulo.
Usando nodos y referencias, podríamos pensar que el árbol está estructurado como el que se muestra en la Figura 2.
Figura 2: Un árbol sencillo que utiliza un enfoque de nodos y referencias¶
Figura 2: Un árbol sencillo que utiliza un enfoque de nodos y referencias
Comenzaremos con una definición de clase muy simple para el enfoque de nodos y referencias como se muestra en el Programa 4. Lo importante a recordar sobre esta representación es que los atributos izquierdo y derecho se convertirán en referencias a otras instancias de la clase ArbolBinario. Por ejemplo, cuando insertamos un nuevo hijo izquierdo en el árbol, creamos otra instancia de ArbolBinario y modificamos self.hijoIzquierdo en la raíz para hacer referencia al nuevo árbol.
Programa 4
class ArbolBinario:
def __init__(self,objetoRaiz):
self.clave = objetoRaiz
self.hijoIzquierdo = None
self.hijoDerecho = None
Observe que en el Programa 4, el método constructor espera obtener algún tipo de objeto para almacenar en la raíz. Al igual que usted puede almacenar cualquier objeto que desee en una lista, el objeto raíz de un árbol puede ser una referencia a cualquier objeto. Para nuestros primeros ejemplos, almacenaremos el nombre del nodo como valor raíz. Usando nodos y referencias para representar el árbol de la Figura 2, crearíamos seis instancias de la clase ArbolBinario.
A continuación, echemos un vistazo a las funciones que necesitamos para construir el árbol más allá del nodo raíz. Para añadir un hijo izquierdo al árbol, crearemos un nuevo objeto árbol binario y fijaremos el atributo izquierdo de la raíz para referirnos a este nuevo objeto. El código para insertarIzquierdo se muestra en el Programa 5.
Programa 5
1def insertarIzquierdo(self,nuevoNodo):
2 if self.hijoIzquierdo == None:
3 self.hijoIzquierdo = ArbolBinario(nuevoNodo)
4 else:
5 t = ArbolBinario(nuevoNodo)
6 t.hijoIzquierdo = self.hijoIzquierdo
7 self.hijoIzquierdo = t
Debemos considerar dos casos para la inserción. El primer caso se caracteriza por un nodo sin hijo izquierdo. Cuando no hay un hijo izquierdo, simplemente se agrega un nodo al árbol. El segundo caso se caracteriza por un nodo con un hijo izquierdo ya existente. En el segundo caso, insertamos un nodo y empujamos al hijo ya existente un nivel hacia abajo en el árbol. El segundo caso es manejado por la instrucción else en la línea 4 del Programa 5.
El código de insertarDerecho debe considerar un conjunto simétrico de casos. O no habrá ningún hijo derecho, o tendremos que insertar el nodo entre la raíz y un hijo derecho ya existente. El código de inserción se muestra en el Programa 6.
Programa 6
def insertarDerecho(self,nuevoNodo):
if self.hijoDerecho == None:
self.hijoDerecho = ArbolBinario(nuevoNodo)
else:
t = ArbolBinario(nuevoNodo)
t.hijoDerecho = self.hijoDerecho
self.hijoDerecho = t
Para redondear la definición de una estructura de datos simple de árbol binario, escribiremos métodos de acceso (ver el Programa 7) para los hijos izquierdo y derecho, así como para los valores raíz.
Programa 7
def obtenerHijoDerecho(self):
return self.hijoDerecho
def obtenerHijoIzquierdo(self):
return self.hijoIzquierdo
def asignarValorRaiz(self,obj):
self.clave = obj
def obtenerValorRaiz(self):
return self.clave
Ahora que tenemos todas las piezas para crear y manipular un árbol binario, vamos a usarlas para comprobar un poco más la estructura. Hagamos un árbol simple con el nodo a como raíz, y añadamos los nodos b y c como hijos. El ActiveCode 1 crea el árbol y mira algunos de los valores almacenados en clave, izquierdo y derecho. Observe que tanto el hijo izquierdo de la raíz como el hijo derecho son instancias distintas de la clase ArbolBinario. Como dijimos en nuestra definición recursiva original para un árbol, esto nos permite tratar a cualquier hijo de un árbol binario como un árbol binario en sí mismo.
Autoevaluación
Escriba una función crearArbol que devuelva un árbol usando la implementación de nodos y referencias y que corresponda al siguiente árbol:
