Pseudocodigo inorden, preorden, postorden. Arboles binarios

septiembre 23, 2009 at 11:07 pm

Hoy quería hablarles de un pack de juegos pero dado que no sirve megaipload (¬¬), cambiare esa sesion por una divertidisima clase de arboles binarios.

Igualmente este sera un post divertidísimo =D, bueno en realidad no, pero igual les sirve para la escuela.

Intoducción

Primero, vamos a ver los tres tipos de recorridos que pueden llevarse a cabo en los arboles binarios para visitar todos los nodos que en el existen. Si no entienden estos términos ven la siguiente imagen:

arbol2

Jaja, ya quedó claro?

Primero hay que definir recorrido de nodos de manera formal

Definición formal

Recorrido de nodos en un árbol binario: Visitar todos los nodos del árbol en forma sistemática de manera que solo sean visitados una sola vez.

Tipos de recorridos

Hay tres formas de hacerlo:

Recorrido preorden.- Hay que visitar los nodos en el siguiente orden:

recorrido preorden

Recorrido preorden

-Raíz
-Sub arbol izquierdo
-Sub árbol derecho

Recorrido inorden.-Hay que visitar los nodos en el siguiente orden:

recorrido inorden

recorrido inorden

-Sub arbol izquierdo
-Raíz
-Sub árbol derecho

Recorrido postorden.-Hay que visitar los nodos en el siguiente orden:

Recorrido postorden

Recorrido postorden

-Sub arbol izquierdo
-Sub árbol derecho
-Raíz

Tomando como ejemplo la imagen tendriamos despues de visitar los nodos del arbol los siguientes resultados:
Visita preorden  —> A B D E C F G
Visita inorden     —> D B E A F C G
Visita postorden —> D E B F G C A

Con esto dejo en sus manos el PSEUDOCODIGO para programar este algoritmo:

Pseudocodigo  preorden


preorden( nodo )

//donde nodo es un  registro de tipo puntero
//valor, nIzq y nDer son campos del registro nodo.
//valor = valor del nodo que se esta visitando
//nIzq y nDer= valor de tipo apuntador (sirven para no perder los nodos derecho e izquierdo y poder volver cuando se necesite)

si nodo <> NULO  entonces //(si nodo no es nulo/vacío)

visitar el nodo //nodo.info (obtenemos el valor del nodo )
preorden(nodo.izq) //llamamos de nuevo el método preorden mandando como parámetro el nodo izquierdo del nodo actual.
preorden(nodo.der) //llamamos de nuevo el metodo preorden mandando como parámetro el nodo derecho del nodo actual

fin

fin

Explicación visual del pseudocodigo

Por alguna razon, esta imagen me aclara mas la idea del pseudocodigo:

Mi explicacion grafica y chada del pseudocodigo

Mi explicacion grafica y chafa del pseudocodigo

Para realizar el pseudocodigo postorden e inorden pos namas cambia unas cosillas del anterior, si no sabes como hacerlo pues, pegate un tiro ¬¬, igual los dejo acá abajo para que no se awiten:

Pseudocodigo  inorden

inorden( nodo )

//donde nodo es un registro de tipo puntero
//valor, nIzq y nDer son campos del registro nodo.
//valor = valor del nodo que se esta visitando
//nIzq y nDer= valor de tipo apuntador (sirven para no perder los nodos derecho e izquierdo y poder volver cuando se necesite)

si nodo <> NULO  entonces //(si nodo no es nulo/vacío)

inorden(nodo.izq) //llamamos de nuevo el método inorden mandando como parámetro el nodo izquierdo del nodo actual.
visitar el nodo //nodo.info (obtenemos el valor del nodo )
inorden(nodo.der) //llamamos de nuevo el método inorden mandando como parámetro el nodo derecho del nodo actual

fin

fin

Pseudocodigo  postorden

postorden( nodo )

//donde nodo es un registro de tipo puntero
//valor, nIzq y nDer son campos del registro nodo.
//valor = valor del nodo que se esta visitando
//nIzq y nDer= valor de tipo apuntador (sirven para no perder los nodos derecho e izquierdo y poder volver cuando se necesite)

si nodo <> NULO  entonces //(si nodo no es nulo/vacío)

postorden(nodo.izq) //llamamos de nuevo el método postorden mandando como parámetro el nodo izquierdo del nodo actual.
postorden(nodo.der) //llamamos de nuevo el método postorden mandando como parámetro el nodo derecho del nodo actual
visitar el nodo //nodo.info (obtenemos el valor del nodo )

fin

fin

Espero y les sirva si no pos, que chafa soy. Cualquier duda o extra que quieran agregar, ya saben, existen los comentarios, ahí abajito, Agradezcan no sean weyes. Salep, estudien ;)