Árbol binario
Última actualización
Un árbol binario es una jerarquía donde cada nodo tiene como máximo dos hijos, llamados hijo izquierdo e hijo derecho. El nodo superior es la raíz, los nodos sin hijos son hojas, y el número de aristas desde la raíz hasta la hoja más profunda es la altura del árbol. A diferencia de un árbol binario de búsqueda, un árbol binario simple no tiene regla de orden: es solo la forma. Pulsa reproducir arriba para ver cómo un árbol se llena nivel por nivel y luego se recorre en orden (izquierda, nodo, derecha).
Los árboles binarios sustentan muchas estructuras: árboles binarios de búsqueda, montículos, árboles de expresiones y más. Los recorridos visitan cada nodo en un orden definido: en orden, en preorden y en postorden son los tres recorridos en profundidad, cada uno útil para tareas distintas.
Terminología
| Término | Significado |
|---|---|
| Raíz | El nodo superior, sin padre |
| Hoja | Un nodo sin hijos |
| Altura | El camino más largo de raíz a hoja (en aristas) |
| Profundidad | Distancia de un nodo respecto a la raíz |
| Completo | Todos los niveles llenos salvo quizá el último, llenado de izquierda a derecha |
Los tres recorridos en profundidad
| Recorrido | Orden | Uso común |
|---|---|---|
| En orden | Izquierda, nodo, derecha | Salida ordenada de un BST |
| Preorden | Nodo, izquierda, derecha | Copiar / serializar un árbol |
| Postorden | Izquierda, derecha, nodo | Eliminar / evaluar un árbol |
Ejemplo resuelto
Recorrido en orden del árbol construido a partir de [4, 2, 6, 1, 3, 5] (llenado nivel por nivel):
| Paso | En el nodo | Acción |
|---|---|---|
| 1 | 4 | Se recurre al subárbol izquierdo de 4 antes de visitarlo |
| 2 | 2 | Se recurre al subárbol izquierdo de 2 antes de visitarlo |
| 3 | 1 | Hoja, sin hijo izquierdo: se visita 1, salida [1] |
| 4 | 2 | Izquierda terminada: se visita 2, salida [1, 2], luego se recurre a la derecha |
| 5 | 3 | Hoja: se visita 3, salida [1, 2, 3] |
| 6 | 4 | Subárbol izquierdo terminado: se visita 4, salida [1, 2, 3, 4], luego se recurre a la derecha |
| 7 | 5 | Hijo izquierdo de 6, una hoja: se visita 5, salida [1, 2, 3, 4, 5] |
| 8 | 6 | Izquierda terminada, sin hijo derecho: se visita 6, salida [1, 2, 3, 4, 5, 6] |
Cuándo usar un árbol binario
| Úsalo cuando | Evítalo cuando |
|---|---|
| Necesitas modelar datos intrínsecamente jerárquicos (sistemas de archivos, árboles de expresiones, DOM) | Los datos son planos y bastaría con una lista o un arreglo: un árbol solo añade sobrecarga |
| Quieres operaciones ordenadas y puedes mantenerlo equilibrado (un BST o un árbol autoequilibrado) | Necesitas búsqueda por clave en O(1) promedio: una tabla hash supera a cualquier árbol |
| Necesitas procesar datos estructurados en orden, preorden o postorden | Los nodos se insertan en orden ascendente en un BST no equilibrado: degenera en una lista O(n) |
| Importan las consultas por rango o la iteración ordenada, que las tablas hash no ofrecen | La memoria es escasa: cada nodo carga dos punteros a hijos además de los datos |
Código de Binary Tree
Una implementación limpia y ejecutable de Binary Tree en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Binary Tree en Python
Python
1from collections import deque2
3
4class Node:5 def __init__(self, value):6 self.value = value7 self.left = None8 self.right = None9
10
11def insert(root, value):12 # Level-order insert: fill the first empty child slot found13 if root is None:14 return Node(value)15 queue = deque([root])16 while queue:17 node = queue.popleft()18 if node.left is None:19 node.left = Node(value)20 return root21 queue.append(node.left)22 if node.right is None:23 node.right = Node(value)24 return root25 queue.append(node.right)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36 root = insert(root, value)37
38print("Root: ", root.value)39print("Inorder:", inorder(root))Código de Binary Tree en JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinaryTree {10 constructor() {11 this.root = null;12 }13
14 // Insert at the first free spot, top to bottom (level order)15 insert(value) {16 const node = new Node(value);17 if (!this.root) {18 this.root = node;19 return;20 }21 const queue = [this.root];22 while (queue.length > 0) {23 const current = queue.shift();24 if (!current.left) {25 current.left = node;26 return;27 }28 if (!current.right) {29 current.right = node;30 return;31 }32 queue.push(current.left, current.right);33 }34 }35
36 inorder(node = this.root, out = []) {37 if (!node) return out;38 this.inorder(node.left, out);39 out.push(node.value);40 this.inorder(node.right, out);41 return out;42 }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));Código de Binary Tree en Java
Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5 static class Node {6 int value;7 Node left, right;8 Node(int value) { this.value = value; }9 }10
11 static Node root;12
13 // Insert at the first free slot in level order (keeps the tree complete)14 static void insert(int value) {15 Node node = new Node(value);16 if (root == null) { root = node; return; }17 Queue<Node> queue = new ArrayDeque<>();18 queue.add(root);19 while (!queue.isEmpty()) {20 Node cur = queue.poll();21 if (cur.left == null) { cur.left = node; return; }22 if (cur.right == null) { cur.right = node; return; }23 queue.add(cur.left);24 queue.add(cur.right);25 }26 }27
28 // Inorder: left subtree, node, right subtree29 static void inorder(Node node, StringBuilder sb) {30 if (node == null) return;31 inorder(node.left, sb);32 sb.append(node.value).append(" ");33 inorder(node.right, sb);34 }35
36 public static void main(String[] args) {37 for (int v = 1; v <= 7; v++) insert(v);38 StringBuilder sb = new StringBuilder();39 inorder(root, sb);40 System.out.println("Root: " + root.value);41 System.out.println("Inorder: " + sb.toString().trim());42 }43}Código de Binary Tree en C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else root->right = insert(root->right, value);14 return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19 if (node == nullptr) return;20 inorder(node->left);21 std::cout << node->value << " ";22 inorder(node->right);23}24
25int countNodes(const Node* node) {26 if (node == nullptr) return 0;27 return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31 Node* root = nullptr;32 for (int value : {8, 3, 10, 1, 6, 14, 4}) {33 root = insert(root, value);34 }35 std::cout << "In-order: ";36 inorder(root);37 std::cout << "\n";38 std::cout << "Node count: " << countNodes(root) << "\n";39 return 0;40}Código de Binary Tree en C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* left;7 struct Node* right;8} Node;9
10Node* newNode(int value) {11 Node* n = malloc(sizeof(Node));12 n->value = value;13 n->left = n->right = NULL;14 return n;15}16
17Node* insert(Node* root, int value) {18 if (root == NULL) return newNode(value);19 if (value < root->value) root->left = insert(root->left, value);20 else root->right = insert(root->right, value);21 return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26 if (node == NULL) return;27 inorder(node->left);28 printf("%d ", node->value);29 inorder(node->right);30}31
32int countNodes(const Node* node) {33 if (node == NULL) return 0;34 return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38 int values[] = {8, 3, 10, 1, 6, 14, 4};39 Node* root = NULL;40 for (int i = 0; i < 7; i++) root = insert(root, values[i]);41 printf("In-order: ");42 inorder(root);43 printf("\n");44 printf("Node count: %d\n", countNodes(root));45 return 0;46}Preguntas frecuentes sobre árboles binarios
¿Cuál es la diferencia entre un árbol binario y un árbol binario de búsqueda?
Un árbol binario simplemente limita cada nodo a un máximo de dos hijos, sin orden alguno. Un árbol binario de búsqueda añade la regla de que todo en el subárbol izquierdo es menor y todo en el subárbol derecho es mayor, que es lo que hace rápida la búsqueda.
¿Qué es un recorrido en orden?
El recorrido en orden visita el subárbol izquierdo, luego el nodo y luego el subárbol derecho, de forma recursiva. Para un árbol binario de búsqueda esto produce los valores en orden ascendente, por lo que es el recorrido más común para demostrar.
¿Qué es un árbol binario completo?
Un árbol binario completo tiene todos los niveles totalmente llenos salvo quizá el último, que se llena de izquierda a derecha. Esta forma permite almacenar el árbol de forma compacta en un arreglo (sin necesidad de punteros a hijos), que es como se implementan los montículos binarios.
¿Cuándo debería usar un árbol binario en lugar de un arreglo o una tabla hash?
Recurre a un árbol cuando tus datos son naturalmente jerárquicos o cuando necesitas operaciones ordenadas como consultas por rango e iteración ordenada, algo que las tablas hash no ofrecen. Si solo necesitas búsqueda rápida por clave sin orden, el acceso promedio
O(1) de una tabla hash supera a un árbol, y para datos planos un arreglo es más simple y aprovecha mejor la caché.¿Cuál es la diferencia entre la altura y la profundidad de un árbol binario?
La profundidad se mide desde la raíz hacia abajo hasta un nodo concreto: el número de aristas del camino desde la raíz hasta ese nodo. La altura se mide desde un nodo hacia abajo hasta su hoja más profunda, por lo que la altura de todo el árbol es la profundidad de su nodo más profundo. Un árbol de un solo nodo tiene altura
0, y su único nodo también tiene profundidad 0.¿Por qué un árbol binario no equilibrado rinde tan mal?
Buscar, insertar y eliminar en un árbol binario de búsqueda cuestan
O(h), donde h es la altura. Cuando las claves se insertan en orden ascendente el árbol se convierte en una línea recta, por lo que h crece hasta n y cada operación degenera a O(n), nada mejor que una lista enlazada. Los árboles autoequilibrados como AVL o rojo-negro mantienen la altura en O(log n) para evitarlo.Recursos relacionados
Más visualizaciones
