← Estructuras de datos desde cero · Lección 18/32

Recorridos en profundidad

1/8

Tres órdenes, una sola idea

Recorrer un árbol en profundidad (DFS, *depth-first search*) es bajar por una rama hasta el fondo antes de pasar a la siguiente. Con recursión, en cada nodo hay tres cosas que hacer: visitar el nodo, recorrer su izquierda y recorrer su derecha. Según cuándo visitas el nodo, sale un orden distinto:

Preorden: nodo, izquierda, derecha. Primero el jefe, luego los subordinados.
Inorden: izquierda, nodo, derecha.
Postorden: izquierda, derecha, nodo. Primero los hijos, al final el padre.

leccion.js

1class NodoArbol {
2  constructor(valor, izq = null, der = null) {
3    this.valor = valor;
4    this.izq = izq;
5    this.der = der;
6  }
7}
8
9function arbol(niveles) {
10  if (!niveles.length || niveles[0] === null) return null;
11  const raiz = new NodoArbol(niveles[0]);
12  const cola = [raiz];
13  let i = 1;
14  while (i < niveles.length) {
15    const nodo = cola.shift();
16    if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
17    i++;
18    if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
19    i++;
20  }
21  return raiz;
22}
23
24function preorden(n, r = []) {
25  if (!n) return r;
26  r.push(n.valor); preorden(n.izq, r); preorden(n.der, r);
27  return r;
28}
29function inorden(n, r = []) {
30  if (!n) return r;
31  inorden(n.izq, r); r.push(n.valor); inorden(n.der, r);
32  return r;
33}
34function postorden(n, r = []) {
35  if (!n) return r;
36  postorden(n.izq, r); postorden(n.der, r); r.push(n.valor);
37  return r;
38}
39
40const raiz = arbol([8, 3, 10, 1, 6, null, 14]);
41console.log("preorden: ", preorden(raiz));
42console.log("inorden:  ", inorden(raiz));
43console.log("postorden:", postorden(raiz));

class NodoArbol {
  constructor(valor, izq = null, der = null) {
    this.valor = valor;
    this.izq = izq;
    this.der = der;
  }
}

const raiz = arbol([8, 3, 10, 1, 6, null, 14]);
console.log("preorden: ", preorden(raiz));
console.log("inorden:  ", inorden(raiz));
console.log("postorden:", postorden(raiz));

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

El preorden empieza con la raíz (8) y el postorden termina con ella.
El inorden sale ordenado: 1, 3, 6, 8, 10, 14. No es casualidad: en este árbol todo lo de la izquierda de cada nodo es menor y todo lo de la derecha, mayor. Eso es un árbol de búsqueda, la siguiente unidad.
Las tres funciones son iguales salvo por dónde va el push.

Toda la lección en una página

Tres órdenes, una sola idea

Preorden: nodo, izquierda, derecha. Primero el jefe, luego los subordinados.
Inorden: izquierda, nodo, derecha.
Postorden: izquierda, derecha, nodo. Primero los hijos, al final el padre.

1class NodoArbol {
2  constructor(valor, izq = null, der = null) {
3    this.valor = valor;
4    this.izq = izq;
5    this.der = der;
6  }
7}
8
9function arbol(niveles) {
10  if (!niveles.length || niveles[0] === null) return null;
11  const raiz = new NodoArbol(niveles[0]);
12  const cola = [raiz];
13  let i = 1;
14  while (i < niveles.length) {
15    const nodo = cola.shift();
16    if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
17    i++;
18    if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
19    i++;
20  }
21  return raiz;
22}
23
24function preorden(n, r = []) {
25  if (!n) return r;
26  r.push(n.valor); preorden(n.izq, r); preorden(n.der, r);
27  return r;
28}
29function inorden(n, r = []) {
30  if (!n) return r;
31  inorden(n.izq, r); r.push(n.valor); inorden(n.der, r);
32  return r;
33}
34function postorden(n, r = []) {
35  if (!n) return r;
36  postorden(n.izq, r); postorden(n.der, r); r.push(n.valor);
37  return r;
38}
39
40const raiz = arbol([8, 3, 10, 1, 6, null, 14]);
41console.log("preorden: ", preorden(raiz));
42console.log("inorden:  ", inorden(raiz));
43console.log("postorden:", postorden(raiz));

El preorden empieza con la raíz (8) y el postorden termina con ella.
El inorden sale ordenado: 1, 3, 6, 8, 10, 14. No es casualidad: en este árbol todo lo de la izquierda de cada nodo es menor y todo lo de la derecha, mayor. Eso es un árbol de búsqueda, la siguiente unidad.
Las tres funciones son iguales salvo por dónde va el push.

La altura en una línea

Muchos problemas de árboles se resuelven con la misma forma: «pregúntale a tu izquierda, pregúntale a tu derecha y combina». La altura (o profundidad máxima) de un árbol es 1 más la mayor altura de sus dos subárboles; la de un árbol vacío es 0.

Es postorden: el nodo contesta después de oír a sus hijos. Es el reto «Maximum Depth of Binary Tree».

1class NodoArbol {
2  constructor(valor, izq = null, der = null) {
3    this.valor = valor;
4    this.izq = izq;
5    this.der = der;
6  }
7}
8
9function arbol(niveles) {
10  if (!niveles.length || niveles[0] === null) return null;
11  const raiz = new NodoArbol(niveles[0]);
12  const cola = [raiz];
13  let i = 1;
14  while (i < niveles.length) {
15    const nodo = cola.shift();
16    if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
17    i++;
18    if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
19    i++;
20  }
21  return raiz;
22}
23
24function altura(nodo) {
25  if (nodo === null) return 0;
26  return 1 + Math.max(altura(nodo.izq), altura(nodo.der));
27}
28
29console.log(altura(arbol([8, 3, 10, 1, 6, null, 14])));
30console.log(altura(arbol([1, 2, null, 3, null, 4])));   // una vara hacia la izquierda
31console.log(altura(arbol([])));

3 para el árbol de siempre; 4 para la vara (cuatro nodos, uno por nivel), y 0 para el vacío.

El espejo y el ancestro común

Invertir un árbol (hacerlo espejo) es intercambiar los dos hijos de cada nodo. Con recursión: invierte la izquierda, invierte la derecha y cámbialas de lado. El inorden del espejo sale exactamente al revés.

El ancestro común más bajo de dos nodos es el nodo más profundo que tiene a los dos debajo. La misma forma: si el nodo es uno de los dos, contesta él; si no, pregunta a sus dos lados. Si los dos lados encontraron algo, los nodos están separados y el ancestro es él.

1class NodoArbol {
2  constructor(valor, izq = null, der = null) {
3    this.valor = valor;
4    this.izq = izq;
5    this.der = der;
6  }
7}
8
9function arbol(niveles) {
10  if (!niveles.length || niveles[0] === null) return null;
11  const raiz = new NodoArbol(niveles[0]);
12  const cola = [raiz];
13  let i = 1;
14  while (i < niveles.length) {
15    const nodo = cola.shift();
16    if (niveles[i] != null) { nodo.izq = new NodoArbol(niveles[i]); cola.push(nodo.izq); }
17    i++;
18    if (i < niveles.length && niveles[i] != null) { nodo.der = new NodoArbol(niveles[i]); cola.push(nodo.der); }
19    i++;
20  }
21  return raiz;
22}
23
24function inorden(n, r = []) {
25  if (n) { inorden(n.izq, r); r.push(n.valor); inorden(n.der, r); }
26  return r;
27}
28
29function invertir(nodo) {
30  if (nodo === null) return null;
31  const izq = invertir(nodo.izq);
32  const der = invertir(nodo.der);
33  nodo.izq = der;
34  nodo.der = izq;
35  return nodo;
36}
37
38function ancestro(nodo, p, q) {
39  if (nodo === null || nodo.valor === p || nodo.valor === q) return nodo;
40  const izq = ancestro(nodo.izq, p, q);
41  const der = ancestro(nodo.der, p, q);
42  if (izq && der) return nodo;      // uno a cada lado: soy yo
43  return izq ?? der;                // los dos del mismo lado
44}
45
46const raiz = arbol([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]);
47console.log("ancestro de 5 y 1:", ancestro(raiz, 5, 1).valor);
48console.log("ancestro de 7 y 4:", ancestro(raiz, 7, 4).valor);
49console.log("ancestro de 5 y 4:", ancestro(raiz, 5, 4).valor);
50
51console.log("antes: ", inorden(raiz));
52invertir(raiz);
53console.log("espejo:", inorden(raiz));

El 5 y el 1 están a cada lado de la raíz: su ancestro es el 3. El 7 y el 4 cuelgan del 2.
Para el 5 y el 4 sale el 5: un nodo cuenta como ancestro de sí mismo, y el 4 está debajo de él.
El inorden del espejo es el de antes, leído de atrás para adelante.

Practica con un reto en vídeo

Para leer más

Recorrido de árboles (Wikipedia) ↗