Reconstrucción de un árbol binario
Si un árbol binario no tiene elementos repetidos, es posible reconstruirlo a partir de sus
recorridos.
A partir de los conceptos de raíz, subárbol izquierdo y derecho, se van identificando las raíces
de los subárboles.
Se tienen los siguientes recorridos :
preorden : raiz , izquierdo , derecho
inorden : izquierdo , raiz
, derecho
Se tiene que los recorridos de un árbol binario (no necesariamente ordenado) son :
preorden : 60 - 30 - 10 - 50 - 55 - 80
inorden : 10 - 30 - 50 - 55 - 60 - 80
|
Según el recorrido preorden podemos identificar que el elemento 60 es raíz de un subárbol.
Por lo tanto si nos fijamos en el recorrido inorden,vemos que :
subárbol izquierdo : 10 - 30 - 50 -55
subárbol derecho : 80
|
|
Luego, se dividen los recorridos de los distintos subárboles. Como en este caso existe sólo
un subárbol izquierdo , se tiene :
preorden : 30 - 10 - 50 - 55
inorden : 10 - 30 - 50 - 55
Observando los recorridos se concluye que :
subárbol izquierdo : 10
subárbol derecho : 50 - 55
|
|
Finalmente los recorridos del último subárbol son los siguientes
preorden : 50 - 55
inorden : 50 - 55
obteniéndose :
subárbol izquierdo : vacío
subárbol derecho : 55
|
Otra forma de reconstruir un árbol es a partir de los recorridos
postorden : izquierdo , derecho , raíz
inorden : izquierdo , raíz , derecho
Ejemplo
Primero se identifica la raíz en el recorrido postorden y luego los dos
subárboles en el recorrido inorden.
postorden : 60 - 30 - 80 - 70 - 40 - 20
inorden : 30 - 60 - 20 - 80 - 70 - 40
raíz : 20
subárbol izquierdo : 30 - 60
subárbol derecho : 80 - 70 - 40
|
postorden : 80 - 70 - 40
inorden : 80 - 70 - 40
|
- - - - -
|
postorden : 60 - 30
inorden : 30 - 60
|
:
:
