Árbol binario en Python - Estructura de datos

Árbol binario en Python

10 comentarios / Algoritmos, Estructura de datos, python / Por

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:

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.

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.

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)

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:

    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=", ")

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.

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)

Á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í:

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.

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:

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.

Poniendo todo junto

Árbol binario en Python - Estructura de datos
Árbol binario en Python – Estructura de datos

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.

Estoy aquí para ayudarte 🤝💻

Estoy aquí para ayudarte en todo lo que necesites. Si requieres alguna modificación en lo presentado en este post, deseas asistencia con tu tarea, proyecto o precisas desarrollar un software a medida, no dudes en contactarme. Estoy comprometido a brindarte el apoyo necesario para que logres tus objetivos. Mi correo es parzibyte(arroba)gmail.com, estoy como@parzibyte en Telegram o en mi página de contacto

No te pierdas ninguno de mis posts 🚀🔔

Suscríbete a mi canal de Telegram para recibir una notificación cuando escriba un nuevo tutorial de programación.

10 comentarios en “Árbol binario en Python”

  4. Juan Gerardo

    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??

    Responder
    1. parzibyte

      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

  5. Daniel

    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

    Responder
  6. Daniel

    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?

    Responder
    1. parzibyte

      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

Dejar un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *