Pseudocodigo inorden, preorden, postorden. Arboles binarios

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 😉

11 comments
  1. Bitacoras.com
    septiembre 23, 2009 at 11:07 pm

    Información Bitacoras.com…

    Valora en Bitacoras.com: 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 …..

    Reply
  2. Punksolid
    Punksolid
    septiembre 24, 2009 at 1:05 am

    a shingao, que no eso son tipos de busquedas asi como A*, Primero en profundidad y etc? esos nombres no me los sabia, de todas formas se ve bien

    Reply
  3. Yared
    Yared • Post Author •
    septiembre 24, 2009 at 7:45 am

    «a shingao, que no eso son tipos de busquedas asi como A*, Primero en profundidad y etc? esos nombres no me los sabia, de todas formas se ve bien»

    Los que tu mencionas son metodos de busquedas agilizados para encontrar elementos mas rapido, este tipo de recorridos son sistemáticos, no aplican ningun tipo de complejidad ni «inteligencia» para recorrer el árbol y buscar el elemento, su objetivo es únicamente recorrer el árbol ordenadamente.

    Reply
  4. magq
    magq
    noviembre 12, 2009 at 8:07 am

    muy bue pos me hs hayudado bastante gracis

    Reply
    • godie
      godie
      noviembre 30, 2009 at 6:14 pm

      si te gustaria que publicaramos sobre algo mas, solo dinos y nosotros lo investigamos y lo publicamos 😀

      Reply
  5. yared_usuario
    yared_usuario • Post Author •
    noviembre 12, 2009 at 12:06 pm

    «muy bue pos me hs hayudado bastante gracis»

    Es bueno saber que a alguien le sirve el montón de pavadas que publicamos diario. Gracias por el comentario.

    Reply
  6. controlador
    controlador
    diciembre 6, 2009 at 11:11 am

    ok me sirvio de mucho la explicacion de arboles pero aora quisiera que me ayudaran con pilas pero con recursividad.se los agradeceria un buien y ay algo que les pueda ayudar con mucho gusto.

    Reply
  7. duvansof
    duvansof
    mayo 7, 2010 at 10:59 am

    excelente ayuda….

    Reply
  8. Carlos Rojas
    Carlos Rojas
    agosto 1, 2011 at 11:45 am

    Muy buen post, bien explicado y super bien, Ayuda aquien no saben, yo lo vi y me deja mas claro aun

    Reply
  9. ale
    ale
    marzo 2, 2012 at 11:42 am

    como se haria un recorrido en postorden sin usar recursividad? Muchas gracias por su ayuda 🙂

    Reply
Responder a YaredCancel

Your email address will not be published. Required fields are marked *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.