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

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

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.


Estoy disponible para trabajar en tu proyecto o realizar tu tarea pendiente, no dudes en ponerte en contacto conmigo.
Si el post fue de tu agrado muestra tu apoyo compartiéndolo, suscribiéndote al blog, siguiéndome o realizando una donación.

Suscribir por correo

Ingresa tu correo y recibirás mis últimas entradas sobre programación, open source, bases de datos y todo lo relacionado con informática

Únete a otros 1,134 suscriptores


parzibyte

Programador freelancer listo para trabajar contigo. Aplicaciones web, móviles y de escritorio. PHP, Java, Go, Python, JavaScript, Kotlin y más :) https://parzibyte.me/blog/software-creado-por-parzibyte/

0 Comentarios

Deja un comentario

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

A %d blogueros les gusta esto: