Implementando Estructuras de Datos de Árbol en Python

Tabla de Contenido

• Construyendo un Árbol Binario desde Cero
• Recorriendo Árboles Binarios
• Aprovechando las Bibliotecas de Python para Estructuras de Árbol

Construyendo un Árbol Binario desde Cero

Los árboles son estructuras de datos fundamentales utilizadas para representar relaciones jerárquicas en la ciencia de la computación. Tienen aplicaciones en diversos campos, desde sistemas de archivos y árboles de decisión hasta la representación de HTML y árboles de análisis sintáctico en compiladores. Comencemos implementando un árbol binario en Python. Un árbol binario es un árbol donde cada nodo tiene como máximo dos hijos: un hijo izquierdo y un hijo derecho.

Definiremos una clase Node para representar nodos individuales y una clase BinaryTree para gestionar la estructura general del árbol.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert_recursive(self.root, data)

    def _insert_recursive(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = Node(data)
            else:
                self._insert_recursive(node.left, data)
        else:
            if node.right is None:
                node.right = Node(data)
            else:
                self._insert_recursive(node.right, data)

    def search(self, data):
        return self._search_recursive(self.root, data)

    def _search_recursive(self, node, data):
        if node is None or node.data == data:
            return node
        if data < node.data:
            return self._search_recursive(node.left, data)
        return self._search_recursive(node.right, data)


# Ejemplo de uso
tree = BinaryTree()
tree.insert(8)
tree.insert(3)
tree.insert(10)
tree.insert(1)
tree.insert(6)
tree.insert(14)

print(tree.search(6).data) # Salida: 6
print(tree.search(15)) # Salida: None

  

Este ejemplo demuestra las operaciones de inserción y búsqueda. Tenga en cuenta que el método insert crea un árbol de búsqueda binario (ABB), donde el subárbol izquierdo contiene valores más pequeños y el subárbol derecho contiene valores más grandes. Otros tipos de árboles requerirían una lógica de inserción diferente.

Recorriendo Árboles Binarios

Para acceder a los datos dentro de un árbol, usamos el recorrido del árbol. Esto implica visitar cada nodo exactamente una vez. Los métodos de recorrido comunes incluyen:

• Recorrido en orden: Subárbol izquierdo, raíz, subárbol derecho (para ABB, esto produce una secuencia ordenada).
• Recorrido preorden: Raíz, subárbol izquierdo, subárbol derecho.
• Recorrido postorden: Subárbol izquierdo, subárbol derecho, raíz.

class BinaryTree:
    # ... (código anterior) ...

    def inorder_traversal(self):
        result = []
        self._inorder_recursive(self.root, result)
        return result

    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.data)
            self._inorder_recursive(node.right, result)

# Ejemplo de uso:
print(tree.inorder_traversal())  # Salida: [1, 3, 6, 8, 10, 14]
  

Esto muestra un recorrido en orden. Se pueden escribir funciones recursivas similares para recorridos preorden y postorden. También son posibles enfoques iterativos utilizando pilas.

Aprovechando las Bibliotecas de Python para Estructuras de Árbol

Para árboles más complejos o funcionalidades avanzadas, las bibliotecas de Python pueden ser beneficiosas. networkx, aunque principalmente una biblioteca de grafos, puede representar árboles de manera efectiva:

import networkx as nx

tree = nx.DiGraph()
tree.add_node(8)
tree.add_edge(8, 3)
tree.add_edge(8, 10)
tree.add_edge(3, 1)
tree.add_edge(3, 6)
tree.add_edge(10, 14)

for node in nx.dfs_preorder_nodes(tree, source=8):
    print(node) # Ejemplo: Recorrido de búsqueda en profundidad
  

networkx ofrece algoritmos para recorrido, búsqueda de la ruta más corta y otras operaciones útiles. Bibliotecas como anytree están específicamente diseñadas para estructuras de árbol y proporcionan funcionalidades especializadas. La elección de la implementación, personalizada o basada en bibliotecas, depende de la complejidad y los requisitos específicos de su proyecto.