¿Cómo Programar un Árbol Binario de búsqueda en Python ?

Árbol binario de búsqueda 

En este blog nos centraremos principalmente a  programar un árbol binario sin embargo si aun tienes duda de que es te damos la definición resumida: 

Un árbol Binario de búsqueda es un estructura de datos  que permite una búsqueda muy eficiente, similar a la búsqueda binaria en un arreglo ordenado; en un   árbol binario donde cada nodo tiene un valor, y los nodos están organizados de tal manera que, para cada nodo:

      1. Todos los nodos en el subárbol izquierdo tienen valores menores que el valor del               nodo.
     2.  Todos los nodos en el subárbol derecho tienen valores mayores que el valor del                 nodo.

Ejemplo de un árbol binario.

Si aun tiene dudas sobre los arboles binarios le recomendamos visitar nuestro blog sobre los mismos https://asimov.cloud/blog/programacion-5/que-es-un-arbol-binario-de-busqueda-296.

Programación en Python. 

Lo primero que debemos hacer es incluir la  biblioteca matplotlib  que permite crear gráficos y figuras.

import matplotlib.pyplot as plt

Postreramente necesitaremos una clase Nodo que estará dentro de  nutra clase árbol.

 class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izquierda = None
        self.derecha = None

Posteriormente crearemos la clase Árbol binario con sus respectivo constructor y métodos.

class ArbolBinario:

    def __init__(self, raiz):  # Constructor de la clase ArbolBinario
        self.raiz = raiz  # Inicialización de la raíz del árbol
        self.valores_x = []  # Lista para almacenar las coordenadas x de los nodos
        self.valores_y = []  # Lista para almacenar las coordenadas y de los nodos
        self.etiquetas = {}  # Diccionario para almacenar las etiquetas de los nodos

    def insertar(self, valor):  # Método para insertar un nuevo nodo en el árbol

        if self.raiz is None:  # Si el árbol está vacío, el nuevo nodo se convierte en la raíz
            self.raiz = Nodo(valor)
        else:
            self._insertar_recursivo(valor, self.raiz)  # Llama al método de inserción recursivo

    def _insertar_recursivo(self, valor, nodo_actual):  # Método de inserción recursivo
        if valor < nodo_actual.valor:  # Si el valor es menor que el valor del nodo actual
            if nodo_actual.izquierda is None:  # Si no hay un nodo a la izquierda, se inserta aquí
                nodo_actual.izquierda = Nodo(valor)
            else:
                self._insertar_recursivo(valor, nodo_actual.izquierda)  # Insertar recursivamente hacia la izquierda
        elif valor > nodo_actual.valor:  # Si el valor es mayor que el valor del nodo actual
            if nodo_actual.derecha is None:  # Si no hay un nodo a la derecha, se inserta aquí
                nodo_actual.derecha = Nodo(valor)
            else:
                self._insertar_recursivo(valor, nodo_actual.derecha)  # Insertar recursivamente hacia la derecha
        else:
            # Valor ya existe, se puede manejar según el caso
            pass

    def _generar_coordenadas(self, nodo, nivel, pos):  # Método para generar las coordenadas de los nodos
        if nodo is not None:
            self.valores_x.append(pos)  # Agregar la coordenada x del nodo a la lista
            self.valores_y.append(nivel)  # Agregar la coordenada y del nodo a la lista
            self.etiquetas[(pos, nivel)] = nodo.valor  # Agregar la etiqueta del nodo al diccionario
            self._generar_coordenadas(nodo.izquierda, nivel-1, pos-2)  # Generar coordenadas para el subárbol izquierdo
            self._generar_coordenadas(nodo.derecha, nivel-1, pos+2)  # Generar coordenadas para el subárbol derecho

    def _dibujar_conexiones(self, nodo, nivel, pos):  # Método para dibujar las conexiones entre los nodos
        if nodo is not None:
            if nodo.izquierda is not None:  # Si hay un nodo hijo izquierdo
                plt.plot([pos, pos-2], [nivel, nivel-1], color='black')  # Dibujar una línea de conexión hacia él
                self._dibujar_conexiones(nodo.izquierda, nivel-1, pos-2)  # Dibujar conexiones recursivamente

            if nodo.derecha is not None:  # Si hay un nodo hijo derecho
                plt.plot([pos, pos+2], [nivel, nivel-1], color='black')  # Dibujar una línea de conexión hacia él
                self._dibujar_conexiones(nodo.derecha, nivel-1, pos+2)  # Dibujar conexiones recursivamente

    def mostrar_graficamente(self):  # Método para mostrar el árbol gráficamente
        self._generar_coordenadas(self.raiz, 0, 0)  # Generar las coordenadas de los nodos
        for (x, y), etiqueta in self.etiquetas.items():  # Iterar sobre las etiquetas del diccionario
            plt.text(x, y, str(etiqueta), fontsize=12, ha='center')  # Mostrar la etiqueta de cada nodo

        self._dibujar_conexiones(self.raiz, 0, 0)  # Dibujar las conexiones entre los nodos
        plt.scatter(self.valores_x, self.valores_y, c='blue', s=300, alpha=0.5)  # Graficar los nodos como puntos
        plt.axis('off')  # Desactivar los ejes
        plt.show()  # Mostrar el gráfico

Ahora a manera de ejemplo le pedirnos que realice inserciones de valores y muestre el resultado gráficamente.

# Ejemplo de uso

if __name__ == "__main__":
    arbol = ArbolBinario(None)
    valores = [5,2,6,8,4,3,9]
    for valor in valores:
        arbol.insertar(valor)
    arbol.mostrar_graficamente()

Resultado.