Existen varias operaciones que se pueden realizar en un árbol, por ejemplo, el recorrido, que comienza por el Nodo Raíz para continuar por las ramas o nodos internos hasta las nodos terminales.

Las operaciones básicas deben permitir agregar o eliminar nodos, realizar el recorrido, determinar su altura (o profundidad), el número de elementos y copiarlo; incluso, si el árbol contiene una expresión, podríamos evaluarla.

Las operaciones que vamos a implementar aquí son las siguientes:

insert()

Insertar un elemento en un árbol

delete()

Eliminar un elemento de un árbol

isEmpty()

Comprobar si un árbol está vacío

depth()

Calcular la altura (o profundidad) del árbol

leaves()

Determinar el número de nodos hoja

Todas estas operaciones se pueden realizar programáticamente recorriendo el árbol. Este recorrido es la operación básica que realizaremos sobre un árbol y será utilizada en muchas de estas funciones.

Implementación de un árbol binario

Vamos a implementar un aŕbol binario que guarde la expresión \(1\times\left(\left(3^4\right)+2\right)\) que en notación de lenguaje C se escribe así: 1 * ((3 ^ 4) + 2). Y si es posible, vamos a evaluarla.

/*
  author: Javier Sanchez Toledano
  date: 2021-10-09
  description: Representation of expression tree
*/

#include <stdio.h>
#include <stdlib.h>

// Node definition
struct node {
  char data;
  struct node *left;
  struct node *right;
};

typedef struct node Node;
typedef Node *BinaryTree;

// Initializa the tree with the root value
// Declaring the root node
BinaryTree *root = NULL;

A partir del nodo raíz vamos acceder a los demás nodos del árbol; dicho de otro modo, ahí empieza el recorrido de nuestro árbol.

Creación de un nodo

Para crear nuestro árbol debemos crear cada uno de los nodos y enlazarlos con el nodo Padre que le corresponda. Para crear un nodo en un árbol binario, vamos a reservar la memoria pra este nodo con malloc(), asignamos el dato al campo data, y apuntamos los nodos izquierdo y derecho a NULL.

BinaryTree createNode(char data) {
    BinaryTree newNode = (BinaryTree)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Creación del árbol

La función newTree() crea un árbol en el cual la raíz tiene como argumentos el árbol raíz, las hojas izquierda y derecha, así como el campo de datos.

void newTree(BinaryTree *root, BinaryTree leftLeaf, char data, BinaryTree rightLeaf) {
    *root = createNode(data);
    (*root)->left = leftLeaf;
    (*root)->right = rightLeaf;
}

Altura o profundidad de un árbol

Conocer la altura o profundidad de un árbol binario es necesario para varias operaciones cuando trabajamos con árboles. La función depth() determina la altura de un árbol binario, y solo tiene como parámetro un apuntador a la raíz del árbol.

Cuando hablamos de altura de un árbol, el caso más simple se presenta cuando el árbol está vacío, es decir root == NULL o bien !root, y su altura es 0. Si el árbol no está vacío, cada rama tiene su propia altura y se evalúa de forma independiente. En esta función, las variables depthL y depthR guardan la altura de las ramas izquierda y derecha, respectivamente.

Por último, llamamos a esta función de forma recursiva con apuntadores a cada rama como parámetros. La función devuelve la altura de la rama más alta más uno (por la propia raíz del árbol).

// Function tp calculate the depth of the tree
int depth(BinaryTree root) {
  if(!root) return 0;
  else {
    int depthL = depth(root->left);
    int depthR = depth(root->right);
    if(depthL > depthR) 
      return depthL + 1;
    else 
      return depthR + 1;   
  }
}

Número de hojas en un árbol binario

Habrá ocasiones en las que necesitemos recorrer las ramas de un árbol si orden. Se me ocurre, por ejemplo, conocer cuántas manzanas hay en una localidad, de cierta sección en cada municipio. El caso es que está función determina el número de hojas, es decir, el número de nodos que no tienen descendientes. Para determinar si un nodo es hoja, los apuntadores left y right deben apuntar a NULL, es decir !root->left.

// Function to count leaves
int leaves(BinaryTree root) {
  if(!root) return 0;
  else if(!root->left && !root->right) return 1;
  else return leaves(root->left) + leaves(root->right);
}

Eliminar los nodos de un árbol binario

La función delete() libera las ramas del árbol. Se recorre el árbol y se usa la función free(). Este recorrido se hace de modo que la memoria que se libera de un nodo se hace después de haber liberado la rama izquierda y derecha.

// Function to delete the tree
void deleteTree(BinaryTree root) {
  if(root) {
    deleteTree(root->left);
    deleteTree(root->right);
    printf("Nodo borrado: %d", root->data);
  }
}

Evaluar si un árbol está vacío

Esta función simplemente verifica si el nodo raíz tiene nodos.

// Function to check is a tree is empty
int isEmpty(BinaryTree root) {
  if(!root) return 1;
  else return 0;
}