Árboles: Lo que debes saber para tu próxima entrevista
Qué es un árbol
Es una estructura de datos compuesta de nodos -hojas-.
Qué es un árbol binario
En la práctica, es común que al hablar de árboles hagamos referencia a un árbol binario, al ser uno de los más usados y conocidos.
Un árbol binario es, simplemente, un árbol donde cada nodo tiene como máximo 2 hijos.
Qué es un árbol de búsqueda binaria
Se trata de un tipo de árbol binario bastante popular por la facilidad que brinda para buscar elementos. Cumple con la siguiente condición.
Para cada nodo en el árbol, todos los descendientes a la izquierda son menores y todos los descendientes a la derecha son mayores
Otros tipos de árboles binarios
Formas de recorrer un árbol
Tomando el siguiente como ejemplo:
A
/ \
B C
/ \ \
D E F
Recomendado por LinkedIn
Pre-order
Primero visitamos el nodo raíz, luego recorremos el subárbol izquierdo, y finalmente recorremos el subárbol derecho.
El recorrido pre-order sería: A, B, D, E, C, F.
In-order
Primero recorremos el subárbol izquierdo, visitamos el nodo raíz, y finalmente recorremos el subárbol derecho.
El recorrido in-order sería: D, B, E, A, C, F.
Post-order
Primero recorremos el subárbol izquierdo, luego el subárbol derecho, y finalmente visitamos el nodo raíz.
El recorrido post-order sería: D, E, B, F, C, A.
Ejercicios para practicar
El contenido de este post se obtuvo de los libros:
Si te gusto este post, asegúrate de suscribirte para enterarte de nuevas publicaciones. ✌🏼