1
Download Transformacion en arboles binarios
Document related concepts
Transcript
Transformación en Árboles Binarios
Estructura de Datos
Transformación en árboles binarios
•
•
•
Un conjunto de árboles, un bosque, se puede transformar en un árbol si se le coloca un
nodo raíz, del cual penden los diferentes árboles.
De igual forma, mediante el procedimiento denominado “transformación natural” se puede
convertir en un árbol binario.
o Sea un bosque B = { A1, A2, A3, A4, …, An }
o Donde A1 es un árbol que puede o no ser binario
Un bosque se puede transformar en un árbol binario mediante el siguiente procedimiento:
o Si N = 0 número de árboles, el árbol binario equivalente está vacío.
o Si N < > 0
La raíz del árbol binario es la raíz de A1
El enlace izquierdo, está conformado por los sub-árboles A11, A12, A13, …,
A1m
El enlace derecho, está conformado por los árboles A2, A3, A4, …, An
Forma de recorrer bosques
•
•
Los bosques se recorren de modo similar a los árboles, para ello se aplica la
transformación natural y se tiene en cuenta la propiedad recursiva de la estructura de
árbol.
Recorrido en Pre-Orden
o Visitar la raíz.
o Recorrer los sub-árboles del primer árbol (en pre-orden).
o Recorrer el resto de los árboles (en pre-orden).
o Ejemplo:
A B C D E F X Y Z Q M N L
ISC Gregorio García Estrada
Transformación en Árboles Binarios
Estructura de Datos
•
•
A (B C (D E F) X (Y (Z Q) M (M L)))
Recorrido en In-Orden
o Recorrer los sub-árboles del primer árbol (en in-orden)
o Visitar la raíz del primer árbol.
o Recorrer los demás árboles (en in-orden)
o Ejemplo:
B D E F C A Z Q Y N L M X
(B ((D E F) C) A) ((Z Q) Y (N L) M) X
Recorrido en Post-Orden
o Recorrer los sub-árboles del primer árbol (en post-orden)
o Recorrer los demás árboles (en post-orden)
o Visitar la raíz
o Ejemplo:
F E D C B Q Z L N M Y X A
ISC Gregorio García Estrada
