¿Qué es un árbol de expresiones?

Un árbol de expresiones es una estructura de datos binaria que se utiliza para representar y evaluar operaciones matemáticas y lógicas.

Un árbol de expresiones tiene dos características principales:

1.- Es un árbol binario

Es una estructura compuesta por nodos (elementos o piezas de datos). A diferencia de una estructura lineal, un árbol se organiza de forma jerárquica, lo que significa que cada nodo está por encima o por debajo de otro.

De cada nodo pueden derivarse hasta dos nodos hijos.

Si quieres aprender más sobre árboles binarios, visita el post “Árbol Binario: Qué es, Usos, Tipos y Cómo Crear Uno con JavaScript/TypeScript”.

2.- Evalúa operaciones matemáticas y lógicas

Los árboles de expresión se utilizan principalmente en:

• Calculadoras
• Hojas de cálculo (como Excel)
• Compiladores
• Lenguajes de programación

Permiten representar operaciones como sumas, restas, multiplicaciones y divisiones de forma estructurada.

¿Cómo se forma un árbol de expresiones?

Un árbol está formado por dos tipos principales de nodos:

1. Nodos hoja: Son los nodos que se encuentran al final del árbol. No tienen hijos y normalmente representan valores numéricos.
2. Nodos internos: son los nodos que tienen al menos un hijo. En un árbol de expresiones, estos nodos representan operadores matemáticos como +, -, * o /.

¿Cómo se resuelve un árbol de expresiones?

Los árboles de expresión se evalúan de abajo hacia arriba. Esto ocurre porque la estructura del árbol respeta la precedencia de los operadores:

• Los operadores más profundos se ejecutan primero
• La operación del nodo raíz es la última en ejecutarse

Ejemplo sencillo:

Resolvamos la expresión: (2 + 1) * 3

Primero resolvemos la operación más profunda:

2 + 1 = 3

Este resultado se convierte en un nodo que luego se multiplica por 3.

Finalmente:

3 * 3 = 9

Así es como un árbol de expresiones nos permite evaluar operaciones en el orden correcto.

👉 En resumen: Un árbol de expresiones se resuelve de abajo hacia arriba, evaluando primero las operaciones más internas hasta llegar al resultado final.

¿Cómo crear un árbol de expresiones con código?

Para crear un árbol de expresiones, podemos usar una clase que represente un nodo del árbol.

class ArbolBinario {
  valor: number | "suma" | "resta" | "multiplicacion"
  izquierda: ArbolBinario | null
  derecha: ArbolBinario | null

  constructor(valor: number | "suma" | "resta" | "multiplicacion") {
    this.valor = valor
    this.izquierda = null
    this.derecha = null
  }
}

Esta clase contiene tres propiedades:

• valor: puede ser un número o un operador
• izquierda: referencia al hijo izquierdo
• derecha: referencia al hijo derecho

Para entender mejor cómo crear un árbol binario desde cero, puedes visitar el artículo mencionado anteriormente.

¿Cómo resolvemos un árbol de expresiones recursivamente?

Primero entendamos ¿Qué es una función recursiva? y ¿Por qué la recursión es natural en los árboles?

Una función recursiva es aquella que se llama a sí misma hasta alcanzar un caso base que detiene la ejecución.

Por ejemplo, imagina que queremos contar desde 3 hasta 0 e imprimir cada número en la consola. Nuestro caso base es llegar a 0; cuando eso ocurra, la función debe detenerse. La función recibe un número y le resta 1 en cada llamada. Con la recursión, la función se llama a sí misma hasta alcanzar ese caso base.

const contar = (numero: number): void => {
  if (numero === 0) return; // caso base (detiene la función)
  console.log(numero)
  contar(numero - 1); // la función se llama a sí misma
};
contar(3);

La recursión es especialmente útil para trabajar con árboles porque cada nodo de un árbol puede verse como un árbol más pequeño.

Piensa en un árbol real 🌳. Si observas una rama grande, notarás que esa rama se parece al árbol completo: también tiene ramas más pequeñas que se dividen una y otra vez.

Lo mismo ocurre en un árbol de datos. Cada nodo tiene:

• un valor
• un subárbol izquierdo
• un subárbol derecho

Resolver el árbol completo es simplemente repetir el mismo proceso en cada uno de sus subárboles.

Ahora si podemos resolver nuestro árbol de expresión

Paso 1 — Crear la función con Typescript

La función recibe un nodo y debe regresar un número.

const evaluarArbolDeExpresion = (nodo: ArbolBinario | null): number => {}

Paso 2 — Definir los casos base

Queremos detener la recursión cuando:

✅ El nodo es null. Aqui regresamos 0 por simplicidad, pero usar throw new Error puede ser una mejor practica.

✅ El nodo contiene un número (es un nodo hoja) por lo tanto es el último nodo y queremos utilizar el valor para hacer la operación matemática indicada.

const evaluarArbolDeExpresion = (nodo: ArbolBinario | null): number => {
    if (!nodo) return 0

    if (typeof nodo.valor === "number") {
      return nodo.valor
    }
}

Paso 3 — Evaluar los subárboles

Ahora evaluamos los hijos:

const valorIzquierda = evaluarArbolDeExpresion(nodo.izquierda)
const valorDerecha = evaluarArbolDeExpresion(nodo.derecha)

El valorIzquierdo y el valorDerecho son el resultado de llamar recrusivamente evaluarArbolDeExpresion

Paso 4 — Aplicar la operación

Utilizamos un "switch statement" que suma, resta o multiplica dependiendo del valor del nodo.

const evaluarArbolDeExpresion = (nodo: ArbolBinario | null): number => {
    if (!nodo) return 0
    
    if (typeof nodo.valor === "number") {
      return nodo.valor
    }
    
    const valorIzquierda = evaluarArbolDeExpresion(nodo.izquierda)
    const valorDerecha = evaluarArbolDeExpresion(nodo.derecha)
    
    switch (nodo.valor) {
      case "suma":
         return valorIzquierda + valorDerecha
      case "resta":
         return valorIzquierda - valorDerecha
      case "multiplicacion":
         return valorIzquierda * valorDerecha
    }
    
    return 0

}

Ahora tenemos una función capaz de evaluar un árbol completo.

Te recomiendo agarrar una hoja y lapiz y tratar de resolver un árbol sencillo siguiendo la función.