Introducción

Un árbol binario es una estructura de datos jerárquica en la que cada nodo tiene como máximo dos hijos, denominados hijo izquierdo e hijo derecho. Los árboles binarios son fundamentales en la informática y se utilizan en una variedad de aplicaciones, desde la representación de expresiones matemáticas hasta la implementación de estructuras de datos más complejas como los árboles binarios de búsqueda y los árboles AVL.

Conceptos Clave

Definición de Árbol Binario

Nodo: Elemento que contiene un valor o dato y referencias a sus nodos hijos.
Raíz: Nodo superior del árbol.
Hijo: Nodo descendiente de otro nodo.
Padre: Nodo que tiene uno o más nodos hijos.
Hoja: Nodo que no tiene hijos.
Subárbol: Árbol formado por un nodo y todos sus descendientes.

Propiedades de los Árboles Binarios

Altura del Árbol: Longitud del camino más largo desde la raíz hasta una hoja.
Profundidad de un Nodo: Longitud del camino desde la raíz hasta ese nodo.
Nivel de un Nodo: Profundidad del nodo más uno.
Número de Nodos: Total de nodos en el árbol.

Representación de Árboles Binarios

Los árboles binarios pueden representarse de varias maneras, siendo las más comunes:

Representación con Punteros: Cada nodo tiene punteros a sus hijos izquierdo y derecho.
Representación con Arreglos: Los nodos se almacenan en un arreglo, donde el nodo en la posición i tiene a sus hijos en las posiciones 2i+1 (hijo izquierdo) y 2i+2 (hijo derecho).

Ejemplo de Representación con Punteros

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izquierdo = None
        self.derecho = None

class ArbolBinario:
    def __init__(self):
        self.raiz = None

    def insertar(self, valor):
        if self.raiz is None:
            self.raiz = Nodo(valor)
        else:
            self._insertar_recursivo(valor, self.raiz)

    def _insertar_recursivo(self, valor, nodo_actual):
        if valor < nodo_actual.valor:
            if nodo_actual.izquierdo is None:
                nodo_actual.izquierdo = Nodo(valor)
            else:
                self._insertar_recursivo(valor, nodo_actual.izquierdo)
        else:
            if nodo_actual.derecho is None:
                nodo_actual.derecho = Nodo(valor)
            else:
                self._insertar_recursivo(valor, nodo_actual.derecho)

# Ejemplo de uso
arbol = ArbolBinario()
arbol.insertar(10)
arbol.insertar(5)
arbol.insertar(15)

Ejemplo de Representación con Arreglos

class ArbolBinarioArreglo:
    def __init__(self):
        self.arreglo = []

    def insertar(self, valor):
        self.arreglo.append(valor)

    def obtener_hijo_izquierdo(self, indice):
        hijo_izquierdo_indice = 2 * indice + 1
        if hijo_izquierdo_indice < len(self.arreglo):
            return self.arreglo[hijo_izquierdo_indice]
        return None

    def obtener_hijo_derecho(self, indice):
        hijo_derecho_indice = 2 * indice + 2
        if hijo_derecho_indice < len(self.arreglo):
            return self.arreglo[hijo_derecho_indice]
        return None

# Ejemplo de uso
arbol = ArbolBinarioArreglo()
arbol.insertar(10)
arbol.insertar(5)
arbol.insertar(15)

Tipos de Recorridos en Árboles Binarios

Recorrido en Preorden (Preorder)

Visita la raíz, luego el subárbol izquierdo y finalmente el subárbol derecho.

def preorden(nodo):
    if nodo:
        print(nodo.valor, end=' ')
        preorden(nodo.izquierdo)
        preorden(nodo.derecho)

# Ejemplo de uso
preorden(arbol.raiz)

Recorrido en Inorden (Inorder)

Visita el subárbol izquierdo, luego la raíz y finalmente el subárbol derecho.

def inorden(nodo):
    if nodo:
        inorden(nodo.izquierdo)
        print(nodo.valor, end=' ')
        inorden(nodo.derecho)

# Ejemplo de uso
inorden(arbol.raiz)

Recorrido en Postorden (Postorder)

Visita el subárbol izquierdo, luego el subárbol derecho y finalmente la raíz.

def postorden(nodo):
    if nodo:
        postorden(nodo.izquierdo)
        postorden(nodo.derecho)
        print(nodo.valor, end=' ')

# Ejemplo de uso
postorden(arbol.raiz)

Ejercicio Práctico

Ejercicio 1: Implementar un Árbol Binario y Realizar Recorridos

Implementa una clase ArbolBinario con métodos para insertar nodos y realizar recorridos en preorden, inorden y postorden.
Inserta los siguientes valores en el árbol: 10, 5, 15, 3, 7, 12, 18.
Realiza y muestra los recorridos en preorden, inorden y postorden.

Solución

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izquierdo = None
        self.derecho = None

class ArbolBinario:
    def __init__(self):
        self.raiz = None

    def insertar(self, valor):
        if self.raiz is None:
            self.raiz = Nodo(valor)
        else:
            self._insertar_recursivo(valor, self.raiz)

    def _insertar_recursivo(self, valor, nodo_actual):
        if valor < nodo_actual.valor:
            if nodo_actual.izquierdo is None:
                nodo_actual.izquierdo = Nodo(valor)
            else:
                self._insertar_recursivo(valor, nodo_actual.izquierdo)
        else:
            if nodo_actual.derecho is None:
                nodo_actual.derecho = Nodo(valor)
            else:
                self._insertar_recursivo(valor, nodo_actual.derecho)

    def preorden(self, nodo):
        if nodo:
            print(nodo.valor, end=' ')
            self.preorden(nodo.izquierdo)
            self.preorden(nodo.derecho)

    def inorden(self, nodo):
        if nodo:
            self.inorden(nodo.izquierdo)
            print(nodo.valor, end=' ')
            self.inorden(nodo.derecho)

    def postorden(self, nodo):
        if nodo:
            self.postorden(nodo.izquierdo)
            self.postorden(nodo.derecho)
            print(nodo.valor, end=' ')

# Ejemplo de uso
arbol = ArbolBinario()
valores = [10, 5, 15, 3, 7, 12, 18]
for valor in valores:
    arbol.insertar(valor)

print("Recorrido en Preorden:")
arbol.preorden(arbol.raiz)
print("\nRecorrido en Inorden:")
arbol.inorden(arbol.raiz)
print("\nRecorrido en Postorden:")
arbol.postorden(arbol.raiz)

Conclusión

En esta sección, hemos aprendido sobre los árboles binarios, sus propiedades y cómo representarlos tanto con punteros como con arreglos. También hemos explorado los diferentes tipos de recorridos en árboles binarios y hemos implementado un ejercicio práctico para reforzar estos conceptos. En la siguiente sección, profundizaremos en los árboles binarios de búsqueda, una variante específica de los árboles binarios que permite realizar búsquedas eficientes.

Árboles Binarios

Introducción

Conceptos Clave

Definición de Árbol Binario

Propiedades de los Árboles Binarios

Representación de Árboles Binarios

Ejemplo de Representación con Punteros

Ejemplo de Representación con Arreglos

Tipos de Recorridos en Árboles Binarios

Recorrido en Preorden (Preorder)

Recorrido en Inorden (Inorder)

Recorrido en Postorden (Postorder)

Ejercicio Práctico

Ejercicio 1: Implementar un Árbol Binario y Realizar Recorridos

Solución

Conclusión

Curso de Estructuras de Datos

Módulo 1: Introducción a las Estructuras de Datos

Módulo 2: Listas

Módulo 3: Pilas

Módulo 4: Colas

Módulo 5: Árboles

Módulo 6: Grafos

Módulo 7: Conclusiones y Recursos Adicionales