RECORRIDO DE UN ÁRBOL

Recorridos

Se puede hacer un recorrido de un árbol en profundidad o en anchura.

Los recorridos en anchura son por niveles, se realiza horizontalmente desde la raíz a todos los hijos antes de pasar a la descendencia de alguno de los hijos.

El coste de recorrer el ABB es O(n), ya que se necesitan visitar todos los vértices.

El recorrido en profundidad lleva al camino desde la raíz hacia el descendiente más lejano del primer hijo y luego continúa con el siguiente hijo. Como recorridos en profundidad tenemos inorden, preorden y postorden. Una propiedad de los ABB es que al hacer un recorrido en profundidad inorden obtenemos los elementos ordenados de forma ascendente. (WIKIPEDIA, 2014)

Ejemplo árbol binario de búsqueda

Resultado de hacer el recorrido en:

Inorden = [6, 9, 13, 14, 15, 17, 20, 26, 64, 72].

Preorden = [15, 9, 6, 14, 13, 20, 17, 64, 26, 72].

Postorden =[6, 13, 14, 9, 17, 26, 72, 64, 20, 15].

BIBLIOGRAFIA: 

WIKIPEDIA. (21 de 05 de 2014). Árbol binario de búsqueda . Recuperado el 21 de 05 de 2014, de BUSQUEDA: http://es.wikipedia.org/wiki/%C3%81rbol_binario_de_b%C3%BAsqueda#B.C3.BAsqueda