Arboles binarios
Enviado por Carlos Garcia Aguilar • 10 de Junio de 2021 • Apuntes • 1.030 Palabras (5 Páginas) • 161 Visitas
[pic 1][pic 2]
[pic 3][pic 4]
Contenido
Introducción 1
Recorrido en arboles binarios 2
Recorrido en INORDEN 2
Ejemplo: 1 2
Algoritmo1: 3
Recorrido en PREORDEN 3
Ejemplo2: 3
Algoritmo2: 4
Recorrido en Post-orden: 4
Ejemplo3: 4
Algoritmo3: 5
Ejemplos de recorridos en INORDER, PREORDER y POSTORDER 5
Introducción
De forma general, se puede decir que los árboles pueden ser utilizados para la construcción de árboles genealógicos, en el aspecto con la informática, se tienen grandes aplicaciones para la creación de directorios (carpetas) en los discos de las computadoras, para mostrar las relaciones lógicas entre los registros de una base de datos (colección de registros controlados por una computadora) y las búsquedas en los compiladores de los lenguajes de programación (árboles binarios).
Recorrido en arboles binarios
Un recorrido en un árbol binario es una operación que consiste en visitar todos sus vértices o nodos, de tal manera que cada vértice se visite una sola vez.
Se distinguen tres tipos de recorrido: INORDEN, POSORDEN Y PREORDEN. En cada recorrido se tiene en cuenta la posición de la raíz (de ahí su nombre) y que siempre se debe ejecutar primero el hijo izquierdo y luego el derecho.
Recorrido en INORDEN
Para recorrer un árbol binario no vacío en In-orden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo, Se recorre en in-orden el primer sub-árbol, luego se recorre la raíz y al final se recorre en in-orden los demás sub-árboles.
1.- Atraviese el sub-árbol izquierdo.
2.- Visite la raíz.
3- Atraviese el sub-árbol derecho.
Ejemplo: 1
[pic 5]
In-order: (G, D, B, H, E, I, A, C, J, K, F)
Algoritmo1:
Este algoritmo realiza un recorrido inorden de un árbol binario ya creado. Nodo es una variable de tipo puntero al nodo
Inicio
Si nodo ≠ NIL[pic 6]
Entonces
Regresar a Inorden (nodo^.IZQ)
Escribir nodo^.Info
Regresar a Inorden con (nodo^. DER)
...