No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Recorrido de 谩rboles

30/40
Recursos

Al momento de representar un 谩rbol debemos elegir el orden en el cual vamos a recorrer dicho 谩rbol. Dependiendo de qu茅 orden se elija ser谩 la forma en que se va a representar el 谩rbol.

Existen tres formas de recorrer un 谩rbol:

鈥 Pre orden: se inicia leyendo el nodo ra铆z, luego se pasa al hijo izquierdo y por ultimo al derecho.
鈥 In orden: inicia leyendo el hijo izquierdo, luego la ra铆z y por 煤ltimo el hijo derecho.
鈥 Pos orden: comienza por el hijo izquierdo para posteriormente ir al hijo derecho y por 煤ltimo al nodo ra铆z.

Aportes 38

Preguntas 7

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

Tambi茅n hay otra forma que es por nivel o tambi茅n llamada level oreder, la menciono porque es muy importante, les dejo un ejemplo, aunque cabe mencionar que este recorrido requiere de una estructura en espec铆fico que es una cola.

Soy el 煤nico que ve los videos en 1.5x?? jajaja

Esto lo vimos en b煤squeda binaria con el profesor David Aroesti pero en c贸digo.

Mis apuntes para esta clase se reducen a este pantallazo.

RECORRIDO DE 脕RBOLES
El recorrido de 谩rboles se refiere al proceso de visitar de una manera sistem谩tica, exactamente una vez, cada nodo en una estructura de datos de 谩rbol (examinando y/o actualizando los datos en los nodos). Tales recorridos est谩n clasificados por el orden en el cual son visitados los nodos.

Formas de recorrer un 谩rbol:

Preorden: (ra铆z, izquierdo, derecho). Para recorrer un 谩rbol binario no vac铆o en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de ra铆z:

  1. Visitar la ra铆z

  2. Atravesar el sub-谩rbol izquierdo

  3. Atravesar el sub-谩rbol derecho

Inorden: (izquierdo, ra铆z, derecho). Para recorrer un 谩rbol binario no vac铆o en inorden (sim茅trico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

  1. Atravesar el sub-谩rbol izquierdo

  2. Visitar la ra铆z

  3. Atravesar el sub-谩rbol derecho

Postorden: (izquierdo, derecho, ra铆z). Para recorrer un 谩rbol binario no vac铆o en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

  1. Atravesar el sub-谩rbol izquierdo

  2. Atravesar el sub-谩rbol derecho

  3. Visitar la ra铆z

Recorrido de 谩rboles: para representar un 谩rbol de forma correcta se debe tener y especificar un orden.

  • pre-orden: se inicia desde el v茅rtice padre, sigue el hijo izquierdo y por 煤ltimo el hijo derecho.
  • in-orden: inicia leyendo el hijo izquierdo, despu茅s el padre y por 煤ltimo el hijo derecho
  • pos-orden: la lectura se inicia con el hijo izquierdo, despu茅s el hijo derecho y por 煤ltimo el padre.

Resultado: Es un c贸digo que lo podemos convertir a c贸digo m谩quina y usarlo en la ejecuci贸n de un algoritmo.

Siempre he tenido duda. Why? Por qu茅 esa y no otras, y que significa el resultado? Qu茅 me dice?

Conceptos b谩sicos
La representaci贸n del 谩rbol depende del orden del recorrido del mismo.
El recorrido del 谩rbol permite pasar de la representaci贸n de grafo a una de c贸digo.
Con esta representaci贸n podemos llegar de forma m谩s optima al dato de inter茅s.
.
Existen tres formas de recorrer un 谩rbol:
Pre orden
Forma: raiz- izq - der
Algoritmo:
Paso 1: El primer nodo en ser agregado ser谩 el nodo ra铆z, despu茅s pasamos al nodo hijo izquierdo.
Paso 2: Si posee nodos hijos, pasa ser nodo ra铆z, ser谩 agregado y pasamos al nodo hijo izquierdo. Repetimos paso 2 hasta llegar a un nodo terminal.
Paso 3: Si el nodo no tiene nodos hijos, ser谩 anotado como nodo izquierdo y pasamos al nodo derecho. Si no es terminal regresamos al paso 2, si lo es continuamos.
Paso 4: lo agregamos como nodo derecho. Si estamos en la rama del nodo hijo izquierdo de la ra铆z del 谩rbol nos movemos a la rama del nodo hijo derecho y repetimos paso 2. Si ya estamos en dicha rama se termina el algoritmo.
.
In orden
Forma: izq - raiz - der
Paso 1: Estamos en un nodo ra铆z y nos dirigimos a su nodo hijo izquierdo.
Paso 2: Si no es terminal pasa ser ra铆z, no es anotado y repetimos paso 1. Si es terminal vamos al paso 3.
Paso 3: el nodo izquierdo terminal es anotado y tambi茅n anotamos su nodo ra铆z
Paso 4: pasamos al nodo derecho y si no es terminal repetimos paso 1. En caso contrario es anotado como derecho.
Paso 5: Si nos encontramos en la rama de nodo izquierdo hijo, anotamos la ra铆z principal y nos movemos a la rama de nodo derecho hijo. Repetimos paso 1
.
Post orden
Forma: izq - der- raiz
Paso 1: Estamos en un nodo ra铆z y nos dirigimos a su nodo hijo izquierdo.
Paso 2: Si no es terminal pasa ser ra铆z, no es anotado y repetimos paso 1. Si es terminal vamos al paso 3.
Paso 3: el nodo izquierdo terminal es anotado y nos vamos al nodo derecho. Si el nodo no es terminal ser谩 nodo ra铆z y vamos al paso 1. En caso contrario lo anotamos como derecho y luego anotamos el nodo ra铆z de ese derecho.
Paso 4: Si nos encontramos en la rama de nodo izquierdo hijo, pasamos a la rama de hijo derecho y pasa a ser llamado nodo ra铆z y repetimos paso 1.

驴C贸mo se realiza el proceso inverso, es decir c贸mo se decodifica estas expresiones? Por lo que veo existen una variedad de 谩rboles distintos que cumplen una codificaci贸n

Recorrido de 谩rboles:
Son una manera de trasladar el 谩rbol a una estructura de datos (codificaci贸n). Puede realizarse de distintas maneras (el ejemplo representa el mismo 谩rbol en cada tipo de reocrrido):

  • Pre orden (raiz izq der): El primer nodo ser谩 la ra铆z principal, seguido por la representaci贸n del sub谩rbol derecho y el subarbol irquierdo (recursivamente). ejemplo:
    A B D E G H F I
  • In orden (izq raiz der)
    El primer nodo representa la hoja extrema a la izquierda continuamos con la raiz que identifica este sub谩rbol y el sub谩rbol izquierdo de la ra铆z, esto recursivamente. Ejemplo:
    B B G E H A C I F
  • Pos orden (izq der raiz)
    El primer nodo representa la hoja extrema a la izquierda continuamos con el sub谩rbol derecho a la hoja y continuamos con la ra铆z que define este sub谩rbol continuamos recursivamente. Ejemplo:
    D G H E B I F C A

Grafo representado:

Excelente.

preorden primero se lee la raiz-luego el nodo izq luego el derecho
in orden izq- raiz-der
pos orden izq-der-raiz
conclusi贸n personal se mostro un tipo de algoritmo

Conclusi贸n personal: para cada tipo de recorrido en cada movimiento haces otro ciclo del mismo tipo de recorrido hasta que hallas llegado al m谩ximo de cada paso de cada tipo de recorrido.
I mean, si es in orden pues te vas a izquierda, y luego ciclo again para ir a otra izquierda y asi sucesivamente hasta llegar al 煤ltimo izquierdo. una vez ah铆 ya puedes pasar y buscar la ra铆z y justo cuando vayas a buscar el derecho pues haces loop again para ver si ese derecho tiene izquierdas, y si tiene pues pones el izquierdo y tu derecho se vuelve raiz y luego ya pones su otro hijo derecho鈥
no creo me haya dado a entender bien pero you got it.

驴Es v谩lido decir que en el recorrido pos orden, la ra铆z del 谩rbol general siempre ser谩 el 煤ltimo nodo en ser recorrido?

Buen d铆a comunidad.
Estos temas ya los hab铆a visto programando en C++ en el canal de youtube: Programaci贸n ATS; dicho sea de paso, tiene de manera gratuita su curso de C++ y tiene otra versi贸n en Udemy, pero vamos, el gratuito esta super completo.
Les dejo la liga a partir de las clases donde empieza el tema de los 谩rboles.
(https://www.youtube.com/watch?v=k2kx7hupEy4&list=PLWtYZ2ejMVJlUu1rEHLC0i_oibctkl0Vh&index=112)

Pre orden: Raiz-Izq-Der. Empezamos siempre por arriba, osea la ra铆z principal de todo mi sistema luego buscamos el hijo a la izquierda si este hijo es una ra铆z, la anotamos (Debido que Pre Orden los prioriza), y anotamos el hijo izquierdo, si este tiene m谩s hijos lo anotamos y buscamos el hijo de la izquierda y as铆, cu谩ndo encontremos un hijo a la izquierda que no tenga m谩s hijos, entonces luego pasamos para la derecha subiendo.

Cual es la ventaja de una sobre la otra??

驴Y esto en un caso real como en que se puede aplicar?驴Oh que ventajas tiene hacer y saber esto?

recorrido arbol PRE RAIZ-IZ-DH IN IZ-RAIZ-DH POS IZ-DH-RAIZ

In Orden: Izq-Ra矛z-Der, priorizamos la izquierda, luego la ra矛z y luego la derecha. Si un v猫rtice es hijo y a la vez ra矛z, priorizamos su izquierda y as矛 sucesivamente. Pos Orden: Izq - Der - Ra矛z. Con el que hacemos prioridad primero en la izquierda, luego en la derecha y por 霉ltimo en la ra矛z.

Hay varias formas con las que podemos recorrer los 谩rboles, y tambi茅n la forma en c贸mo lo pueden hacer nuestras compus. Pre Orden, In Orden, Pos Orden. Las tres formas m谩s utilizadas en la inform谩tica.

El recorrido nos permite pasar los 谩rboles, de un grafo a una parte literal, puede ser c贸digo si queremos.

Todo nuestro sistema puede cambiar, dependiendo de qu茅 parte del 谩rbol tome.

  • Existen tres formas de hacer recorridos de 谩rboles:
    1. Pre orden. Primero lees la ra铆z, despu茅s te vas al nodo izquierda y despu茅s al derecho.
    2. In orden. Primero lees la izquierda, despu茅s la ra铆z, y luego la derecha.
    3. Pos orden. Primero lees la izquierda, luego la derecha, y finalmente la ra铆z.

Cada recorrido de 谩rbol tiene su propia l贸gica:
Preorden: Empezar de arriba a abajo.
In orden: Empezar de en medio, luego arriba y luego abajo.
Posorde: Empezar de abajo a arriba.

De esta forma pude entender como resolver cada uno.

Muy buena la explicaci贸n, me ayudo a entender este tema que lo hab铆a visto en la universidad y que no lo hab铆a podido entender del todo.

Recorrido Post Orden: Izq - Der - Ra铆z. El desgloce es a partir del extremo, continuo en cada sub谩rbol y desglozo (de izq a der para destacar la ra铆z)

Recorrido por Pre - Orden: Izq - Ra铆z - Der (desglozando el 谩rbol para cada ra铆z)

Recuerden:

El Nodo I es Hijo Izquierdo del Nodo F Ra铆z.

Y:

El Nodo F es Hijo Derecho del Nodo C Ra铆z.

Es medio confuso, pero pueden hacer una pregunta trampa relacionada para confundir.

Excelente explicaci贸n.

QU茅 bacano, hay que prestar mucha atenci贸n.

Hay que estar muy atento.

Informaci贸n valiosa.

En base a nuestros intereses, buscamos el nodo terminal que tenga la direccion que me interesa, hasta encontrar todos los nodos termianesl en el orden que tenemos preestablecido.