|
24/11/2009
Experto
|
Hola rsaul:
Te voy a explicar como se hacen los recorridos en preorden, inorden y postorden. En cualquiera de estos tres recorridos se recorren todos los nodos del árbol, lo único que cambia es su forma de listarlo que son las siguientes:
Tomando como ejemplo el siguiente árbol:
A
/ \
C E
\ / \
B F D
Un recorrido en preorden es el siguiente:
------------------------------
* Si el árbol está vacío, no se hace nada.
* Obtenemos el valor del nodo raiz del árbol.
* Recorremos en preorden el subarbol izquierdo del arbol.
* Recorremos en preorden el subarbol derecho del arbol.
paso a paso:
A,preorden(C),preorden(E)
A,C,preorden(B),preorden(E)
A,C,B,preorden(E)
A,C,B,E,preorden(F),preorden(D)
A,C,B,E,F,preorden(D)
A,C,B,E,F,D
Resultado de recorrer en preorden el arbol: A-C-B-E-F-D.
Un recorrido en Inorden es el siguiente:
------------------------------
* Si el árbol está vacío, no se hace nada.
* Recorremos en inorden el subarbol izquierdo del arbol.
* Obtenemos el valor del nodo raiz del árbol.
* Recorremos en inorden el subarbol derecho del arbol.
paso a paso:
inorden(C),A,inorden(E)
C,inorden(B),A,inorden(E)
C,B,A,inorden(E)
C,B,A,inorden(F),E,inorden(D)
C,B,A,F,E,inorden(D)
C,B,A,F,E,D
Resultado de recorrer en inorden el arbol: C-B-A-F-E-D.
Un recorrido en Postorden es el siguiente:
------------------------------
* Si el árbol está vacío, no se hace nada.
* Recorremos en postorden el subarbol izquierdo del arbol.
* Recorremos en postorden el subarbol derecho del arbol.
* Obtenemos el valor del nodo raiz del árbol.
paso a paso:
postorden(C),postorden(E),A
postorden(B),C,postorden(E),A
B,C,postorden(E),A
B,C,postorden(F),postorden(D),E,A
B,C,F,postorden(D),E,A
B,C,F,D,E,A
Resultado de recorrer en postorden el arbol: B-C-F-D-E-A.
Como habrás visto hemos recorrido todos los nodos, sólo que de forma distinta. Implementar este algoritmo es sencillo usando una técnica recursiva.
Espero haberte sido de ayuda.
Salu2.
|
