Tipos de recorridos de un Árbol

Para ver cómo es el recorrido en un árbol, tomamos como ejemplo el recorrido en un árbol binario.

Un árbol binario es un tipo de árbol en que cada vértice máximo puede tener dos hijos; su nodo raíz está enlazado a dos subárboles binarios disjuntos denominados subárbol izquierdo y subárbol derecho. Los árboles binarios no son vacíos ya que como mínimo tienen el nodo raíz. (8)





Propiedades de un árbol binario



(6)


Recorridos en un árbol binario

Un recorrido en un árbol binario es una operación que consiste en visitar todos sus vértices o nodos, de tal manera que cada vértice se visite una sola vez.
Se distinguen tres tipos de recorrido: INORDEN, POSORDEN Y PREORDEN.
En cada recorrido se tiene en cuenta la posición de la raíz (de ahí su nombre) y que siempre se debe ejecutar primero el hijo izquierdo y luego el derecho.

• Recorrido INORDEN. Este recorrido se realiza así: primero recorre el subárbol izquierdo, segundo visita la raíz y por último, va al subárbol derecho. En síntesis:

hijo izquierdo — raíz — hijo derecho

• Recorrido PREORDEN. Este recorrido se realiza así: primero visita la raíz; segundo recorre el subárbol izquierdo y por último va a subárbol derecho. En síntesis:

raíz — hijo izquierdo — hijo derecho

• Recorrido POSORDEN. Primero recorre el subárbol izquierdo; segundo, recorre el subárbol derecho y por último, visita la raíz. En síntesis: 

hijo izquierdo– hijo derecho — raíz (7)

Capítulo 12: TEORIA DE ARBOLES BINARIOS - Matemáticas Discretas