¿Qué son los recorridos en árboles binarios?
Un recorrido en árboles binarios es una manera de pasar por todos los nodos siguiendo una metodología concreta. Por ejemplo, dado el siguiente árbol:
Un posible recorrido seria: 1 – 2 – 3 – 4 – 5 – 6. Lo que haríamos en este caso sería ir del nivel más alto al más bajo y, en cada nivel, seguir los nodos de izquierda a derecha.
¿Cuáles son los métodos de recorrido en árboles binarios?
Los tipos de recorrido se clasifican según el orden en el que se visita la raíz, el hijo izquierdo y el hijo derecho. Tenemos tres posibilidades:
- Preorden: raíz -> hijo izquierdo -> hijo derecho
- Inorden: hijo izquierdo -> raíz -> hijo derecho
- Postorden: hijo izquierdo -> hijo derecho -> raíz
Aunque así cueste entenderlo, ahora te enseñaré un truco para no equivocarte nunca en los tres recorridos.
Recorrido en preorden
Como hemos dicho anteriormente, en el recorrido en preorden de un árbol binario se visita la raíz, después el hijo izquierdo y finalmente el hijo derecho. Veamos como lo hacemos en este ejemplo.
Primero de todo, colocaremos una marca a la izquierda de cada nodo.
Lo único que tenemos que hacer es rodear el árbol con una línea desde la raíz (nodo 1). A medida que nos vamos encontrando marcas, iremos encontrando el siguiente nodo en preorden.
PREORDEN: 1-2-4-5-3-6
Recorrido en inorden
En el recorrido en inorden se visita primero el hijo izquierdo, después la raíz y, finalmente, el hijo derecho. Para recorrer el siguiente árbol haremos uso de la metodología explicada, no obstante, ahora colocaremos las marcas debajo de cada nodo.
Igual que hemos hecho anteriormente, empezamos a rodear el árbol desde la raíz con una línea. A medida que nos encontramos las marcas, descubrimos cuál es el siguiente nodo en inorden.
INORDEN: 4-2-5-1-3-6
Recorrido en postorden
En el recorrido en postorden se visita primero el hijo izquierdo, después el hijo derecho y, finalmente, la raíz. Para ello colocaremos marcas a la derecha de cada nodo. Veamos el ejemplo:
Rodeamos el árbol y a medida que nos encontramos las marcas encontramos el siguiente nodo en postorden.
POSTORDEN: 4-5-2-6-3-1
Recorrido por niveles o por amplitud
Para realizar este recorrido, debemos situarnos en el nivel más alto del árbol y visitar los nodos del nivel de izquierda a derecha. Cuando acabemos, bajaremos al siguiente nivel hasta que no haya más.
Veamos un ejemplo:
POR NIVELES: 1-2-3-4-5-6
Entradas relacionadas