← Estructuras de datos desde cero · Lección 17/32
Árboles binarios
Un árbol, de cabeza
Una lista enlazada es una fila de nodos donde cada uno apunta al siguiente. En un árbol, cada nodo puede apuntar a varios. En un árbol binario, a dos como máximo: su hijo izquierdo y su hijo derecho.
El vocabulario, con el dibujo:
- La raíz es el nodo de arriba, el único sin padre: el 8.
- Los hijos del 3 son el 1 y el 6; el 3 es su padre.
- Las hojas son los nodos sin hijos: 1, 6 y 14.
- La profundidad de un nodo es cuántos pasos hay desde la raíz: el 8 está a 0, el 6 a 2.
- La altura del árbol es cuántos niveles tiene: éste tiene 3.
Se dibujan con la raíz arriba, al revés de los árboles de verdad. Y están en todas partes: las carpetas de tu computadora, el HTML de una página, el índice de una base de datos.
Toda la lección en una página
Un árbol, de cabeza
Una lista enlazada es una fila de nodos donde cada uno apunta al siguiente. En un árbol, cada nodo puede apuntar a varios. En un árbol binario, a dos como máximo: su hijo izquierdo y su hijo derecho.
El vocabulario, con el dibujo:
- La raíz es el nodo de arriba, el único sin padre: el 8.
- Los hijos del 3 son el 1 y el 6; el 3 es su padre.
- Las hojas son los nodos sin hijos: 1, 6 y 14.
- La profundidad de un nodo es cuántos pasos hay desde la raíz: el 8 está a 0, el 6 a 2.
- La altura del árbol es cuántos niveles tiene: éste tiene 3.
Se dibujan con la raíz arriba, al revés de los árboles de verdad. Y están en todas partes: las carpetas de tu computadora, el HTML de una página, el índice de una base de datos.
Un nodo con dos punteros
En código, un nodo es un objeto con su valor y dos referencias, izq y der, que valen null cuando no hay hijo. Igual que en la unidad de valores y referencias: el nodo no contiene a sus hijos, apunta a ellos.
Abajo se arma a mano el árbol del dibujo, de adentro hacia afuera.
class NodoArbol {
constructor(valor, izq = null, der = null) {
this.valor = valor;
this.izq = izq;
this.der = der;
}
}
const raiz = new NodoArbol(8,
new NodoArbol(3, new NodoArbol(1), new NodoArbol(6)),
new NodoArbol(10, null, new NodoArbol(14)),
);
console.log(raiz.valor);
console.log(raiz.izq.valor, raiz.der.valor);
console.log(raiz.izq.der.valor);
console.log(raiz.der.izq);
console.log(raiz.izq);
- La raíz es 8 y sus hijos 3 y 10.
raiz.izq.deres «el hijo derecho del hijo izquierdo»: el 6.- El 10 no tiene hijo izquierdo:
null. - El último renglón enseña el nodo 3 completo, con sus dos hijos adentro.
Armarlo por niveles
Escribir árboles grandes a mano cansa. La convención de LeetCode (y la de los retos en vídeo) es escribirlos por niveles, de izquierda a derecha, con null donde falta un hijo: el árbol del dibujo es [8, 3, 10, 1, 6, null, 14].
La función arbol de abajo hace la conversión; la vas a ver al principio de los demás programas de la unidad. Y para recorrerlo, la herramienta natural es la recursión: un árbol es un nodo con dos árboles más chicos colgando. Contar nodos es «yo, más los de mi izquierda, más los de mi derecha».
class NodoArbol {
constructor(valor, izq = null, der = null) {
this.valor = valor;
this.izq = izq;
this.der = der;
}
}
function arbol(niveles) {
if (!niveles.length || niveles[0] === null) return null;
const raiz = new NodoArbol(niveles[0]);
const cola = [raiz];
let i = 1;
while (i < niveles.length) {
const nodo = cola.shift();
if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
i++;
if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
i++;
}
return raiz;
}
function contar(nodo) {
if (nodo === null) return 0; // árbol vacío
return 1 + contar(nodo.izq) + contar(nodo.der);
}
// De lado: la raíz a la izquierda y los hijos derechos arriba
function dibujar(nodo, sangria = "") {
if (nodo === null) return;
dibujar(nodo.der, sangria + " ");
console.log(sangria + nodo.valor);
dibujar(nodo.izq, sangria + " ");
}
const raiz = arbol([8, 3, 10, 1, 6, null, 14]);
console.log("nodos:", contar(raiz));
dibujar(raiz);
- Seis nodos: los
nullno cuentan. - El dibujo sale acostado: gira la cabeza a la izquierda y es el mismo árbol de la primera tarjeta, con el 8 como raíz.
Profundidad de cada nodo
Para saber a qué profundidad está cada nodo, se baja por el árbol pasando un número: la raíz recibe 0 y cada hijo recibe uno más que su padre. La altura del árbol es la profundidad más grande, más uno.
Observa que la recursión visita primero toda la rama izquierda y luego la derecha: eso es un recorrido en profundidad, el tema de la siguiente lección.
class NodoArbol {
constructor(valor, izq = null, der = null) {
this.valor = valor;
this.izq = izq;
this.der = der;
}
}
function arbol(niveles) {
if (!niveles.length || niveles[0] === null) return null;
const raiz = new NodoArbol(niveles[0]);
const cola = [raiz];
let i = 1;
while (i < niveles.length) {
const nodo = cola.shift();
if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
i++;
if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
i++;
}
return raiz;
}
let maxima = 0;
function profundidades(nodo, p) {
if (nodo === null) return;
console.log(" ".repeat(p) + nodo.valor + " está a profundidad " + p + (nodo.izq || nodo.der ? "" : " (hoja)"));
maxima = Math.max(maxima, p);
profundidades(nodo.izq, p + 1);
profundidades(nodo.der, p + 1);
}
profundidades(arbol([8, 3, 10, 1, 6, null, 14]), 0);
console.log("altura:", maxima + 1);
Las tres hojas (1, 6 y 14) están a profundidad 2, así que la altura es 3. El orden en que salen (8, 3, 1, 6, 10, 14) baja por la izquierda antes de ir a la derecha.