Recorrido de árboles

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?

https://photos.app.goo.gl/gwetqmAGgKvUtwXo8

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.