Recorridos de Árboles: Preorden, Inorden y Posorden

Clase 30 de 40 • Curso de Matemáticas Discretas

Contenido del curso

Introducción al curso

1
Matemáticas Discretas: Lógica, Conjuntos y Teoría de Gráficas
01:29 min

Lógica

Teoría de conjuntos

Teoría de grafos

Árboles

Algoritmos

Conclusiones

40
Repaso Final de Matemáticas Discretas: Lógica, Conjuntos y Algoritmos
01:08 min

Tomar examen

Resumen

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.

Comentarios

David Enrique Molina Rodríguez

student•

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.

Raul Romero

student•

Gracias por compartir este aporte @David 😄.

Percival Ernesto Amezola Rivera

student•

Interesante el tema de colas. Gracias por el aporte

Luis Fernando Úbeda Camacho

student•

Apuntes de clase

Es importante tener un orden y una estructura clara de los datos, el recorrido de los árboles nos va a permitir llegar de la manera mas optima al dato que nos interesa.

Tres formas de recorrer un árbol

Pre orden: primero leemos la raíz, después el nodo izquierdo y por ultimo el nodo derecho.
raiz- izq - der
In orden: primero leemos el nodo izquierdo, después la raíz y por ultimo el nodo derecho.
izq - raiz - der
Pos orden: primero nodo izquierdo, después nodo derecho y por ultimo nodo raíz.
izq - der- raiz

**Explicación del algoritmo de recorrido **

Pre orden

Siempre es la misma secuencia, el primero nodo sera nuestro nodo raíz, despues pasaremos al siguiente nodo raíz hasta llegar al nodo terminal que no tenga mas nodos raíz, en ese caso anotaremos el nodo izquierdo terminal y pasaremos al nodo derecho.
Recorremos el árbol hasta llegar a la raíz terminal para poder anotar sus nodos izquierdo y derecho terminales también.

In orden

Para entender bien el proceso de recorrido in orden, lo que hacemos realmente es recorrer el árbol binario hasta llegar al nodo izquierdo terminal, ese sera nuestro primero nodo, despue anotaremos la raíz de donde salio ese nodo izquierdo terminal
Depués pasaremos al nodo derecho y si es un nodo raíz lo recorreremos hasta hallar el nodo izquierdo terminal y de nuevo apuntaremos la raíz de donde salio y pasaremos al nodo derecho hasta hallar el nodo derecho terminal
-Cuando consigamos recorrer todo el lado izquierdo del árbol podremos anotar su nodo raíz principal que fue de donde salieron todos los nodos del lado izquierdo
Pasaremos a proceder al lado derecho del árbol haciendo los mismos proceso.

Pos orden

La idea es la misma que los anteriores, recorremos el árbol hasta llegar al nodo terminal que nos interesa en este caso el nodo terminal izquierdo,
El siguiente paso es pasar al nodo derecho pero como no es el nodo derecho terminal volvemos a realizar el proceso, y volveremos anotar otro nodo izquierdo terminal, así hasta dar con el nodo derecho terminal.
Una vez hallamos tanto el nodo izquierdo y derecho terminal anotaremos la raíz de donde salieren.

Conclusión personal

Lo que he comprendido del algoritmo es que recorremos la secuencia hasta hallar el nodo terminal que deseamos ya se raiz, izq, o der y lo repetimos de manera iterativa hasta que no queden mas nodos que recorrer.

Sergio Orduz

teacher•

esta clase en particular es muy importante en programación @luifer088

Sergio Orduz

teacher•

Esta clase en particular es muy importante en programación ya que es la forma como los programas pueden reconocer nuestros árboles 😄

Luis Xavier Perez Miramontes

student•

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

Hernan David Cuy

student•

1.75x

Daniel Alejandro Cumaco Robayo

student•

Christian Sanclemente

student•

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

Juan Fernando Ramirez Montes

student•

Todos estos conceptos se conectan, y la programación se encuentra estrechamente conectada con las matemáticas.

Luis Mojica

teacher•

Mis apuntes para esta clase se reducen a este pantallazo.

!Imgur

Sara Yaneth Contreras Elías

student•

++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:

Visitar la raíz
Atravesar el sub-árbol izquierdo
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:

Atravesar el sub-árbol izquierdo
Visitar la raíz
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:

Atravesar el sub-árbol izquierdo
Atravesar el sub-árbol derecho
Visitar la raíz

Percival Ernesto Amezola Rivera

student•

Percival Ernesto Amezola Rivera

student•

El código es recursivo y está orientado a objetos. Estos son atributos del objeto nodo

nodo.valor
nodo.izquierdo
nodo.derecho

Percival Ernesto Amezola Rivera

student•

**retorna ** significa que sale de la función cuando el valor del nodo está vacío, o sea cuando ha llegado a un nodo que no tiene hijos

Wilson Fernando Antury Torres

student•

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.

Percival Ernesto Amezola Rivera

student•

Josué Eduardo Apén Bal

student•

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

Roberto Arturo

student•

No te dicen nada porque su propósito no es describir algo. Es para elegir la metodología que definirá un proceso. Por eso una vez establecida no se puede cambiar.

Manuel Jose Parra Malagon

student•

En el ejercicio segun la logica del recorrido para "In order" deberia ser:

DBGEH-A-IFC

(izq-raiz-der)

en la "der" debe ir desde lo más extremo de la derecha hacia el centro ¿?

Kevin J. Zea Alvarado

student•

La derecha se considera como el último elemento que se añadiría.

Juan Pablo Rodriguez Pedraos

student•

También pensé que el resultado sería ese, pero aqui importa mucho si está ubicado a la izquierda o a la derecha. En ese orden de ideas, cuando llega a A tiene que ir a C el cual es un subarbol pero sólo tiene un rama derecha, así que, siguiendo el parametro que mencionas (izq-raiz-der) imprime raiz y luego lo de la derecha por eso queda CIF y no IFC.

Max Andy Diaz Neyra

student•

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.

Josue Noha Valdivia

student•

¿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

Pold Anampa Saravia

student•

es correcto, una forma de reconstruir un arbol tal cual es que te indiquen el nivel del nodo

Josue Noha Valdivia

student•

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:

LUIS EDUARDO SALAMANCA GARCIA

student•

Excelente.

Wilson Jerez

student•

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

EDWIN ANTONIO CAN PINTO

student•

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.

Miguel Angel Reyes Moreno

student•

¿Es válido decir que en el recorrido pos orden, la raíz del árbol general siempre será el último nodo en ser recorrido?

Alberto Cházaro Romero

student•

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)

Miguel Andres Rendon Reyes

student•

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.

Recorridos de Árboles: Preorden, Inorden y Posorden

Introducción al curso

Matemáticas Discretas: Lógica, Conjuntos y Teoría de Gráficas

Lógica

Lógica Proposicional: Conceptos y Aplicaciones Básicas

Tablas de verdad y conectores lógicos: conjunción, disyunción y más

Construcción de Tablas de Verdad para Proposiciones Compuestas

Construcción de Tablas de Verdad para Proposiciones Lógicas

Tablas de Verdad y Análisis de Proposiciones Lógicas

Circuitos Lógicos: Representación y Función en Electrónica

Circuitos Lógicos para Proposiciones Compuestas

Tablas y Circuitos Lógicos: Ejercicios Prácticos

Teoría de conjuntos

Conjuntos: Definición, Pertenencia y Representación Matemática

Conjuntos: Nulo, Unitario y Universal y Operaciones Básicas

Representación Gráfica de Operaciones entre Conjuntos

Propiedades de los Conjuntos: Leyes de De Morgan y Representación Gráfica

Representación gráfica de las leyes de De Morgan

Operaciones y Propiedades de Conjuntos: Ejercicio Práctico Resuelto

Operaciones Básicas con Conjuntos y Problemas de Conjuntos

Teoría de grafos

Teoría de Gráficas: Conceptos y Aplicaciones Prácticas

Grado de Vértices y Conexiones en Gráficas Simples

Caminos y ciclos eulerianos en grafos: teoría y aplicación

Caminos y Ciclos Hamiltonianos en Grafos

Construcción de Matrices de Adyacencia para Representar Grafos

Representación de Grafos con Matriz de Incidencia

Matrices de Adyacencia en Grafos Dirigidos

Análisis de Caminos y Ciclos Eulerianos en Grafos

Árboles

Árboles y Tipos de Árboles en Matemáticas Discretas

Estructuras de Árboles en Programación y Jerarquías de Datos

Conceptos Básicos de Estructuras de Árboles en Informática

Árbol de Expansión Mínima: Conexión Óptima de Nodos

Tipos de Árboles Binarios y sus Características