← Estructuras de datos desde cero · Lección 19/32
Recorrido por niveles
Piso por piso, con una cola
El recorrido en profundidad se va hasta el fondo de una rama. El recorrido por niveles (BFS, *breadth-first search*, búsqueda en anchura) hace lo contrario: primero la raíz, luego todos sus hijos, luego todos los nietos.
No sale con recursión sino con una cola: se mete la raíz; mientras la cola no esté vacía, se saca el de enfrente, se visita y se forman sus hijos al final. Como la cola es primero en entrar, primero en salir, los de un piso siempre salen antes que los del siguiente.
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
El orden es 3, 9, 20, 15, 7: piso por piso, de izquierda a derecha. Mira la cola después de visitar el 20: sus hijos, 15 y 7, se formaron al final y salen en las dos vueltas siguientes.
Toda la lección en una página
Piso por piso, con una cola
El recorrido en profundidad se va hasta el fondo de una rama. El recorrido por niveles (BFS, *breadth-first search*, búsqueda en anchura) hace lo contrario: primero la raíz, luego todos sus hijos, luego todos los nietos.
No sale con recursión sino con una cola: se mete la raíz; mientras la cola no esté vacía, se saca el de enfrente, se visita y se forman sus hijos al final. Como la cola es primero en entrar, primero en salir, los de un piso siempre salen antes que los del siguiente.
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 porAnchura(raiz) {
if (raiz === null) return;
const cola = [raiz];
while (cola.length > 0) {
const nodo = cola.shift(); // sale el de enfrente
if (nodo.izq) cola.push(nodo.izq); // sus hijos, al final
if (nodo.der) cola.push(nodo.der);
console.log("visito", nodo.valor, "| la cola queda:", cola.map((n) => n.valor));
}
}
porAnchura(arbol([3, 9, 20, null, null, 15, 7]));
El orden es 3, 9, 20, 15, 7: piso por piso, de izquierda a derecha. Mira la cola después de visitar el 20: sus hijos, 15 y 7, se formaron al final y salen en las dos vueltas siguientes.
Cada nivel en su arreglo
A veces no basta el orden: se quiere saber dónde termina cada piso. El truco es mirar cuántos hay en la cola al empezar una vuelta: ésos son exactamente los del nivel actual. Se sacan esos tam, se juntan en un arreglo, y los hijos que se formaron mientras tanto son el nivel siguiente.
Así sale [[3], [9, 20], [15, 7]], que es el reto «Binary Tree Level Order Traversal».
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 niveles(raiz) {
const r = [];
if (raiz === null) return r;
const cola = [raiz];
while (cola.length > 0) {
const tam = cola.length; // los de este nivel
const nivel = [];
for (let i = 0; i < tam; i++) {
const nodo = cola.shift();
nivel.push(nodo.valor);
if (nodo.izq) cola.push(nodo.izq);
if (nodo.der) cola.push(nodo.der);
}
r.push(nivel);
}
return r;
}
console.log(niveles(arbol([3, 9, 20, null, null, 15, 7])));
console.log(niveles(arbol([8, 3, 10, 1, 6, null, 14])));
Un arreglo por piso. El número de arreglos es la altura del árbol, y el más largo te dice cuál es el piso más ancho.
Lo que se ve desde la derecha
Con los niveles separados salen problemas que con profundidad serían enredosos. Si te paras a la derecha del árbol, de cada piso sólo ves el último nodo: la «vista derecha» es el último de cada nivel.
Una nota de costo: shift() en un arreglo es O(n), porque recorre todo para cerrar el hueco (lo viste en la unidad de colas). Para árboles chicos da igual; para millones de nodos, usa la cola con índice de enfrente.
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 vistaDerecha(raiz) {
const r = [];
const cola = raiz ? [raiz] : [];
let frente = 0; // en vez de shift(): un índice
while (frente < cola.length) {
const fin = cola.length; // el nivel va de frente a fin
for (let i = frente; i < fin; i++) {
const nodo = cola[i];
if (i === fin - 1) r.push(nodo.valor); // el último del piso
if (nodo.izq) cola.push(nodo.izq);
if (nodo.der) cola.push(nodo.der);
}
frente = fin;
}
return r;
}
console.log(vistaDerecha(arbol([1, 2, 3, null, 5, null, 4])));
console.log(vistaDerecha(arbol([1, 2, 3, 4])));
- Primer árbol: 1, 3 y 4, los de la orilla derecha.
- Segundo: 1, 3 y 4, aunque el 4 cuelga del lado izquierdo: en su piso no hay nadie más a su derecha que lo tape.