En este post vamos a implementar la estructura de datos Árbol binario en Python, además de implementar la declaración de un Nodo o rama.
También veremos cómo agregar al nodo sus partes izquierda y derecha, el método para agregar un valor de manera recursiva (y acomodarlo de acuerdo a la raíz) al árbol, recorrido inorden, postorden y preorden, así como la búsqueda de determinado valor en el árbol.
Básicamente implementaremos un árbol en Python con los métodos más comunes. Recuerda que los árboles binarios son una estructura de datos bastante interesante en donde la búsqueda de un elemento se hace de manera rápida por la naturaleza del mismo.
La rama o nodo
Voy a referirme a Nodo como lo que se agrega a este árbol, aunque si lo vemos bien puede que en realidad sea una rama, pues de una rama salen más ramas. Como sea, este nodo tendrá izquierda y derecha que al inicio estarán en None.
Vamos a aprovechar la programación orientada a objetos para encapsular esto en una clase:
Como puedes ver, el valor o dato que guarda cada nodo de este árbol es de tipo genérico. Podría ser una cadena, un entero, un flotante o incluso un objeto como lo dicen los comentarios.
Fíjate en que el nodo recibe el dato que llevará dentro de sí y que al construirse define sus ramas en None.
Insertar dato
Veamos la operación de inserción. Recuerda que todo comienza en la raíz, y después todos los valores se agregan de acuerdo a ésta, ya que si el valor es menor lo ponemos en la rama izquierda, y si es mayor en la derecha.
En caso de que la rama ya esté ocupada, buscamos su subrama para, de nuevo, acomodar el valor. Es por eso que usamos recursión, ya que no se sabe cuándo se encontrará una rama disponible.
Recorrido
Es momento de ver el recorrido del árbol. En este caso existen 3 y solo cambia el orden en el que se visita cada nodo del árbol. El que me parece más útil es el recorrido inorden pues al hacer esto, se van a imprimir los valores ya ordenados.
Veamos el código de Python para el recorrido. Igualmente se aplica recursión:
Búsqueda dentro del árbol binario en Python
Para buscar, igualmente recorremos el árbol. Como estamos en un árbol binario que tiene los datos ya acomodados (pues lo hicimos al insertarlos) podemos usar esto a nuestro favor para hacer una búsqueda binaria y localizar la búsqueda en menos tiempo.
Eso sí, en caso de que el nodo que visitemos sea None, regresamos None, pues no encontramos lo que buscamos. Pero en caso de que sí lo encontremos, regresamos el nodo en donde está la búsqueda.
Árbol binario en Python
Es momento de ver la clase del Árbol. La misma usará al nodo y los métodos que vimos anteriormente. Queda así:
Como puedes ver he dividido las verdaderas funciones del árbol y las que se llaman desde el exterior. Las primeras son privadas y se encargan de hacer las operaciones de manera recursiva, mientras que las públicas son las que se llaman desde la instancia de esta clase.
En pocas palabras solo he separado los conceptos y protegido a los métodos privados, por eso se ve el __ al inicio. Después solo estoy aplicando los algoritmos para el recorrido del árbol, la inserción, etcétera.
Modo de uso del árbol binario en Python
Ya expuse el árbol y su nodo o rama, es momento de ver cómo usarlo. Lo que tenemos que hacer es crear una instancia de la clase Arbol y agregarle cuantos datos queramos con agregar.
En cualquier momento del tiempo podemos buscar un valor o hacer el recorrido que queramos. Veamos un primer ejemplo para un árbol de tipo string:
En la línea 1 instanciamos al árbol pasándole el dato que tendrá en la raíz. Después insertamos varios elementos. En la línea 8 le solicitamos un valor al usuario para que lo pueda insertar, y en la línea 14 lo hacemos de nuevo pero para una búsqueda.
Por cierto, el recorrido se ve en la línea 10 hasta la línea 12.
Poniendo todo junto
El código completo lo dejaré en GitHub, pues he separado los archivos para que el código sea más claro y los podamos importar desde cualquier otro lugar. Aquí mostraré el código completo para el uso de esta estructura de datos:
Al ejecutarlo y probar los métodos, todos los resultados son correctos. Si quieres puedes ejecutarlo online.
Por aquí te dejo más artículos sobre programación en Python y Estructura de datos.
Tengo una duda, como puedo imprimir el recorrido de la busqueda?
demasiado bueno el tutorial por cierto
¿Como se haria la eliminacion de un nodo?
Hola. Gracias por sus comentarios. Si tiene alguna consulta, solicitud de creación de un programa o solicitud de cambio de software estoy para servirle en https://parzibyte.me/#contacto
Saludos!
Una pregunta, pensando en esta estructura, dónde guarda los nodos??, sabemos que tenemos listas, tuplas, etc. Aqui cada valor lo mandas izquierda o derecha, pero dónde van quedando los nodos alojados??
Todo empieza en el primer nodo, ese tiene un “apuntador” a su derecha e izquierda. Y cada uno de esos apuntadores son igualmente nodos que tienen derecha e izquierda, así sucesivamente hasta el final del árbol
Hola, la libreria que usas “nodo” lo intento instalar pero me sale error.
C:\Users\danie>pip install nodo
Defaulting to user installation because normal site-packages is not writeable
ERROR: Could not find a version that satisfies the requirement nodo (from versions: none)
ERROR: No matching distribution found for nodo
No es una librería
ya tiene tiempo que deje de estudiar POO pero nunca vi una cosa como esto.
def __agregar_recursivo(self, nodo, dato):
if dato < nodo.dato:
if nodo.izquierda is None:
nodo.izquierda = Nodo(dato)
else:
self.__agregar_recursivo(nodo.izquierda, dato)
(nodo.izquierda) ¿estas utilizando alguna libreria? izquierda no estoy seguro que sea un metodo de python que tenga. ¿Me puedes explicar que hace?
nodo.izquierda es una propiedad, es el nodo que “nodo” tiene a su izquierda. No es un método, es una propiedad. El método sería __agregar_recursivo, al que le pasamos dos argumentos: el nodo izquierdo del nodo actual y el dato