Estructuras de datos - Árbol
Un árbol (Tree) es una estructura de datos no lineal típica, compuesta por nodos y aristas que conectan nodos, utilizada para representar la relación jerárquica de "uno a muchos" entre elementos.
Terminología básica del árbol
Diagrama de la terminología del árbol
ANodo raíz
Profundidad 0
Profundidad 0
BProfundidad 1
CProfundidad 1
DNodo hoja
Profundidad 2
Profundidad 2
ENodo hoja
FNodo hoja
Nodo raízSin nodo padre, único
Nodo hijoSubordinado directo
Nodo hojaSin nodos hijos
ProfundidadNúmero de aristas desde la raíz hasta el nodo
AlturaNúmero de aristas desde el nodo hasta la hoja más profunda
Árbol binarioCada nodo tiene como máximo 2 hijos
Para entender la estructura de árbol, primero hay que dominar varios términos básicos:
| Término | Significado |
|---|---|
| Nodo raíz (Root) | Nodo inicial del árbol, no tiene nodo padre |
| Nodo hijo (Child) | Nodo de la siguiente nivel directamente conectado a un nodo |
| Nodo padre (Parent) | Nodo del nivel anterior directamente conectado a un nodo |
| Nodo hoja (Leaf) | Nodo sin hijos, es decir, el extremo del árbol |
| Profundidad (Depth) | Número de aristas desde el nodo raíz hasta el nodo; la profundidad de la raíz es 0 |
| Altura (Height) | Número de aristas desde el nodo hasta el nodo hoja más profundo |
Recorrido del árbol binario
Cuatro formas de recorrido del árbol binario — usando el mismo árbol como ejemplo
1
2
3
4
5
Preorden (raíz → izquierda → derecha)
1 2 4 5 3Inorden (izquierda → raíz → derecha)
4 2 5 1 3Postorden (izquierda → derecha → raíz)
4 5 2 3 1Por niveles (capa por capa)
1 2 3 4 5Las cuatro formas comunes de recorrido son las siguientes:
| Método de recorrido | Orden de visita | Aplicación típica |
|---|---|---|
| Recorrido en preorden | Raíz → izquierda → derecha | Copiar árbol, generación de expresiones prefijas |
| Recorrido en inorden | Izquierda → raíz → derecha | El BST genera secuencias ordenadas |
| Recorrido en postorden | Izquierda → derecha → raíz | Eliminar árbol, generación de expresiones posfijas |
| Recorrido por niveles | Capa por capa, de izquierda a derecha | BFS, impresión por niveles |
Ejemplo
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(int value) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}
/* Recorrido en preorden: raíz → izquierda → derecha */
void preOrder(struct TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data); /* Primero se visita la raíz */
preOrder(root->left); /* Luego se recorre el subárbol izquierdo */
preOrder(root->right); /* Por último se recorre el subárbol derecho */
}
/* Recorrido en inorden: izquierda → raíz → derecha */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left); /* Primero se recorre el subárbol izquierdo */
printf("%d ", root->data); /* Luego se visita la raíz */
inOrder(root->right); /* Por último se recorre el subárbol derecho */
}
/* Recorrido en postorden: izquierda → derecha → raíz */
void postOrder(struct TreeNode* root) {
if (root == NULL) return;
postOrder(root->left); /* Primero se recorre el subárbol izquierdo */
postOrder(root->right); /* Luego se recorre el subárbol derecho */
printf("%d ", root->data); /* Por último se visita la raíz */
}
int main() {
/* Construir el siguiente árbol binario:
1
/ \
2 3
/ \
4 5 */
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Preorden: "); preOrder(root); printf("\n"); /* 1 2 4 5 3 */
printf("Inorden: "); inOrder(root); printf("\n"); /* 4 2 5 1 3 */
printf("Postorden: "); postOrder(root); printf("\n"); /* 4 5 2 3 1 */
return 0;
}
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(int value) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}
/* Recorrido en preorden: raíz → izquierda → derecha */
void preOrder(struct TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data); /* Primero se visita la raíz */
preOrder(root->left); /* Luego se recorre el subárbol izquierdo */
preOrder(root->right); /* Por último se recorre el subárbol derecho */
}
/* Recorrido en inorden: izquierda → raíz → derecha */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left); /* Primero se recorre el subárbol izquierdo */
printf("%d ", root->data); /* Luego se visita la raíz */
inOrder(root->right); /* Por último se recorre el subárbol derecho */
}
/* Recorrido en postorden: izquierda → derecha → raíz */
void postOrder(struct TreeNode* root) {
if (root == NULL) return;
postOrder(root->left); /* Primero se recorre el subárbol izquierdo */
postOrder(root->right); /* Luego se recorre el subárbol derecho */
printf("%d ", root->data); /* Por último se visita la raíz */
}
int main() {
/* Construir el siguiente árbol binario:
1
/ \
2 3
/ \
4 5 */
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Preorden: "); preOrder(root); printf("\n"); /* 1 2 4 5 3 */
printf("Inorden: "); inOrder(root); printf("\n"); /* 4 2 5 1 3 */
printf("Postorden: "); postOrder(root); printf("\n"); /* 4 5 2 3 1 */
return 0;
}
Árbol binario de búsqueda (BST)
Árbol binario de búsqueda (BST) — izquierda menor, derecha mayor
50
30
70
20
40
60
80
Propiedades y operaciones del BST
Propiedad: todos los valores del subárbol izquierdo < raíz < todos los valores del subárbol derecho
Inserción/búsqueda: si es menor, ir al subárbol izquierdo; si es mayor, ir al subárbol derecho; O(log n) cuando está equilibrado
El recorrido en inorden genera una secuencia ascendente: 20 30 40 50 60 70 80
Nota: insertar en orden 1,2,3... degenera en una lista enlazada O(n); el árbol AVL puede solucionarlo
Árbol binario de búsqueda (BST)Requisito: para cada nodo, los valores de todos los nodos del subárbol izquierdo son menores que ese nodo, y los valores de todos los nodos del subárbol derecho son mayores que ese nodo.
Ejemplo
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
/* Inserción en BST: localizar recursivamente la posición adecuada según el valor
Complejidad temporal: O(h), donde h es la altura del árbol, O(log n) cuando está equilibrado */
struct TreeNode* insert(struct TreeNode* root, int value) {
if (root == NULL) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = node->right = NULL;
return node;
}
if (value < root->data) {
root->left = insert(root->left, value); /* Menor que la raíz, insertar en el subárbol izquierdo */
} else if (value > root->data) {
root->right = insert(root->right, value); /* Mayor que la raíz, insertar en el subárbol derecho */
}
return root; /* Si es igual, se ignora (el BST normalmente no almacena valores duplicados) */
}
/* Búsqueda en BST: comparar con el nodo actual y decidir si buscar a la izquierda o a la derecha */
struct TreeNode* search(struct TreeNode* root, int target) {
if (root == NULL || root->data == target) {
return root; /* Encontrar el objetivo o llegar a un nodo hoja */
}
if (target < root->data) {
return search(root->left, target); /* El objetivo es menor, buscar en el subárbol izquierdo */
}
return search(root->right, target); /* El objetivo es mayor, buscar en el subárbol derecho */
}
/* Recorrido en inorden (verificar el orden del BST) */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
int main() {
struct TreeNode* root = NULL;
int values[] = {50, 30, 70, 20, 40, 60, 80};
/* Insertar secuencialmente para construir el BST */
for (int i = 0; i < 7; i++) {
root = insert(root, values[i]);
}
printf("Recorrido en inorden del BST (ascendente): ");
inOrder(root); /* Salida: 20 30 40 50 60 70 80 */
printf("\n");
/* Prueba de búsqueda */
int target = 40;
struct TreeNode* found = search(root, target);
printf("%d %s\n", target, found ? "¡Encontrado!" : "No encontrado");
/* Salida: 40 ¡Encontrado! */
return 0;
}
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
/* Inserción en BST: localizar recursivamente la posición adecuada según el valor
Complejidad temporal: O(h), donde h es la altura del árbol, O(log n) cuando está equilibrado */
struct TreeNode* insert(struct TreeNode* root, int value) {
if (root == NULL) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = node->right = NULL;
return node;
}
if (value < root->data) {
root->left = insert(root->left, value); /* Menor que la raíz, insertar en el subárbol izquierdo */
} else if (value > root->data) {
root->right = insert(root->right, value); /* Mayor que la raíz, insertar en el subárbol derecho */
}
return root; /* Si es igual, se ignora (el BST normalmente no almacena valores duplicados) */
}
/* Búsqueda en BST: comparar con el nodo actual y decidir si buscar a la izquierda o a la derecha */
struct TreeNode* search(struct TreeNode* root, int target) {
if (root == NULL || root->data == target) {
return root; /* Encontrar el objetivo o llegar a un nodo hoja */
}
if (target < root->data) {
return search(root->left, target); /* El objetivo es menor, buscar en el subárbol izquierdo */
}
return search(root->right, target); /* El objetivo es mayor, buscar en el subárbol derecho */
}
/* Recorrido en inorden (verificar el orden del BST) */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
int main() {
struct TreeNode* root = NULL;
int values[] = {50, 30, 70, 20, 40, 60, 80};
/* Insertar secuencialmente para construir el BST */
for (int i = 0; i < 7; i++) {
root = insert(root, values[i]);
}
printf("Recorrido en inorden del BST (ascendente): ");
inOrder(root); /* Salida: 20 30 40 50 60 70 80 */
printf("\n");
/* Prueba de búsqueda */
int target = 40;
struct TreeNode* found = search(root, target);
printf("%d %s\n", target, found ? "¡Encontrado!" : "No encontrado");
/* Salida: 40 ¡Encontrado! */
return 0;
}
Otras extensionesEn condiciones ideales (el árbol se mantiene equilibrado), el BST puede alcanzar O(log n) en inserción, eliminación y búsqueda. Pero si los datos en sí están ordenados (como insertar 1, 2, 3, 4...), el BST degenera en una lista enlazada y la eficiencia cae a O(n). Para resolver este problema, en la informática se desarrollaronlos árboles AVLy otros árboles binarios de búsqueda autoequilibrados.