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.
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:
class Nodo:
def __init__(self, dato):
# "dato" puede ser de cualquier tipo, incluso un objeto si se sobrescriben los operadores de comparación
self.dato = dato
self.izquierda = None
self.derecha = None
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
.
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.
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)
else:
if nodo.derecha is None:
nodo.derecha = Nodo(dato)
else:
self.__agregar_recursivo(nodo.derecha, dato)
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:
def __inorden_recursivo(self, nodo):
if nodo is not None:
self.__inorden_recursivo(nodo.izquierda)
print(nodo.dato, end=", ")
self.__inorden_recursivo(nodo.derecha)
def __preorden_recursivo(self, nodo):
if nodo is not None:
print(nodo.dato, end=", ")
self.__preorden_recursivo(nodo.izquierda)
self.__preorden_recursivo(nodo.derecha)
def __postorden_recursivo(self, nodo):
if nodo is not None:
self.__postorden_recursivo(nodo.izquierda)
self.__postorden_recursivo(nodo.derecha)
print(nodo.dato, end=", ")
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.
def __buscar(self, nodo, busqueda):
if nodo is None:
return None
if nodo.dato == busqueda:
return nodo
if busqueda < nodo.dato:
return self.__buscar(nodo.izquierda, busqueda)
else:
return self.__buscar(nodo.derecha, busqueda)
Es momento de ver la clase del Árbol. La misma usará al nodo y los métodos que vimos anteriormente. Queda así:
class Arbol:
# Funciones privadas
def __init__(self, dato):
self.raiz = Nodo(dato)
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)
else:
if nodo.derecha is None:
nodo.derecha = Nodo(dato)
else:
self.__agregar_recursivo(nodo.derecha, dato)
def __inorden_recursivo(self, nodo):
if nodo is not None:
self.__inorden_recursivo(nodo.izquierda)
print(nodo.dato, end=", ")
self.__inorden_recursivo(nodo.derecha)
def __preorden_recursivo(self, nodo):
if nodo is not None:
print(nodo.dato, end=", ")
self.__preorden_recursivo(nodo.izquierda)
self.__preorden_recursivo(nodo.derecha)
def __postorden_recursivo(self, nodo):
if nodo is not None:
self.__postorden_recursivo(nodo.izquierda)
self.__postorden_recursivo(nodo.derecha)
print(nodo.dato, end=", ")
def __buscar(self, nodo, busqueda):
if nodo is None:
return None
if nodo.dato == busqueda:
return nodo
if busqueda < nodo.dato:
return self.__buscar(nodo.izquierda, busqueda)
else:
return self.__buscar(nodo.derecha, busqueda)
# Funciones públicas
def agregar(self, dato):
self.__agregar_recursivo(self.raiz, dato)
def inorden(self):
print("Imprimiendo árbol inorden: ")
self.__inorden_recursivo(self.raiz)
print("")
def preorden(self):
print("Imprimiendo árbol preorden: ")
self.__preorden_recursivo(self.raiz)
print("")
def postorden(self):
print("Imprimiendo árbol postorden: ")
self.__postorden_recursivo(self.raiz)
print("")
def buscar(self, busqueda):
return self.__buscar(self.raiz, busqueda)
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.
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:
arbol = Arbol("Luis")
arbol.agregar("María José")
arbol.agregar("Maggie")
arbol.agregar("Leon")
arbol.agregar("Cuphead")
arbol.agregar("Aloy")
arbol.agregar("Jack")
nombre = input("Ingresa algo para agregar al árbol: ")
arbol.agregar(nombre)
arbol.preorden()
arbol.inorden()
arbol.postorden()
# Búsqueda
busqueda = input("Busca algo en el árbol: ")
nodo = arbol.buscar(busqueda)
if nodo is None:
print(f"{busqueda} no existe")
else:
print(f"{busqueda} sí existe")
# Aquí tienes en "nodo" toda la información del nodo. Tanto su izquierda, derecha, dato y otros atributos que le hayas agregado
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.
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:
"""
https://parzibyte.me/blog
"""
from arbol import Arbol
arbol = Arbol("Luis")
arbol.agregar("María José")
arbol.agregar("Maggie")
arbol.agregar("Leon")
arbol.agregar("Cuphead")
arbol.agregar("Aloy")
arbol.agregar("Jack")
nombre = input("Ingresa algo para agregar al árbol: ")
arbol.agregar(nombre)
arbol.preorden()
arbol.inorden()
arbol.postorden()
# Búsqueda
busqueda = input("Busca algo en el árbol: ")
nodo = arbol.buscar(busqueda)
if nodo is None:
print(f"{busqueda} no existe")
else:
print(f"{busqueda} sí existe")
# Aquí tienes en "nodo" toda la información del nodo. Tanto su izquierda, derecha, dato y otros atributos que le hayas agregado
arbol_numeros = Arbol(5)
arbol_numeros.agregar(1984)
arbol_numeros.agregar(60)
arbol_numeros.agregar(10)
arbol_numeros.agregar(20)
arbol_numeros.agregar(10)
arbol_numeros.agregar(25)
arbol_numeros.agregar(59)
arbol_numeros.agregar(64)
arbol_numeros.agregar(10)
arbol_numeros.agregar(19)
arbol_numeros.agregar(23)
arbol_numeros.agregar(18)
arbol_numeros.agregar(1)
arbol_numeros.agregar(2013)
arbol_numeros.preorden()
arbol_numeros.inorden()
arbol_numeros.postorden()
busqueda = int(input("Ingresa un número para buscar en el árbol: "))
n = arbol_numeros.buscar(busqueda)
if n is None:
print(f"{busqueda} no existe")
else:
print(f"{busqueda} sí existe")
Al ejecutarlo y probar los métodos, todos los resultados son correctos.
Por aquí te dejo más artículos sobre programación en Python y Estructura de datos.
Hoy te voy a presentar un creador de credenciales que acabo de programar y que…
Ya te enseñé cómo convertir una aplicación web de Vue 3 en una PWA. Al…
En este artículo voy a documentar la arquitectura que yo utilizo al trabajar con WebAssembly…
En un artículo anterior te enseñé a crear un PWA. Al final, cualquier aplicación que…
Al usar Comlink para trabajar con los workers usando JavaScript me han aparecido algunos errores…
En este artículo te voy a enseñar cómo usar un "top level await" esperando a…
Esta web usa cookies.
Ver comentarios
en dado caso que quisiera agregarle uno o mas hijos al nodo, de que manera podria hacerlo?
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