CENTRO UNIVERSITARIO UAEM
ATLACOMULCO
LICENCIATURA EN
INGENIERÍA EN COMPUTACIÓN
NOMBRE DEL DOCENTE:
INGENIERO. HÉCTOR
CABALLERO HERNÁNDEZ
NOMBRE MATERIA:
AUTÓMATAS Y LENGUAJES FORMALES
NOMBRE
DE LA ALUMNA:
HEIVILINA PÉREZ
ARIAS
GRUPO:
ICO-19
TURNO:
MATÚTINO
TRABAJO A ENTREGAR:
ARBOL
BINARIO Y SUS RECORRIDOS
FECHA DE ENTREGA:
MAYO DE 2015.
Definición:
Un Árbol Binario es un conjunto de
finito de Elementos, de nombre Nodos de forma que:
El Árbol Binario es Vació si no tiene
ningún elemento en el.
El Árbol Binario contiene un Nodo Raíz
y los dos que parten de él, llamados Nodo Izquierdo y Nodo Derecho.
Los Árboles tiene 3 Recorridos
Diferentes los cuales son:
Pre-Orden
In-Orden
Post-Orden
Pre-Orden
Definición:
El Recorrido “Pre-Orden” lo recorre de
la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido
en la Raíz, después viaje a través del Nodo Izquierdo y después a través del
Nodo Derecho.
Detalle:
Temp toma el Valor de la Raíz y compara
si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y
terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y
viajara a través de los Arreglos Izq y Der para determinar que valor meter en
la Pila y en Temp para de esta manera imprimir el siguiente Elemento
correspondiente.
Algoritmo:
PreOrd(Arbol, Der, Izq, Pila, Raiz)
Temp → Raiz
Top →
Pila[Top] → Nulo
Si Raiz = Nulo
Imprimir “Árbol Vació…” y Salir
Repetir mientras Temp ≠ Nulo
Imprimir Arbol[Temp]
Si Der[Temp] ≠ Nulo
Top → Top + 1
Pila[Top] → Der[Temp]
Si Izq[Temp] ≠ Nulo
Temp → Izq[Temp]
Si no:
Temp → Pila[Top];
Top → Top - 1
Fin del ciclo
Salir
Diagrama:
Corrida:
In-Orden
Definición:
El Recorrido “In-Orden” lo recorre de
la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido
en el Nodo Izquierdo después la Raíz y finalmente viaja a través del Nodo
Derecho.
Detalle:
Temp toma el Valor de la Raíz y compara
si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y
terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y
viajara a través de los Arreglos Izq y Der para determinar que valor meter en
la Pila y en Temp para de esta manera imprimir el siguiente Elemento
correspondiente.
Algoritmo:
PreOrd(Arbol, Der, Izq, Pila, Raiz)
Temp → Raiz
Top →
Pila[Top] → Nulo
Si Raiz = Nulo
Imprmir “Arbol Vacio…” y Salir
Etiqueta:
Mientras Temp ≠ Nulo
Top → Top + 1
Pila[Top] → Temp
Temp → Izq[Temp]
Fin del ciclo
Temp → Pila[Top]
Top → Top - 1
Mientras Temp ≠ Nulo
Imprimir Arbol[Temp]
Si Der[Temp] ≠ Nulo
Temp → Der[Temp]
Ir a Etiqueta
Temp → Pila[Top]
Top → Top - 1
Fin del ciclo
Salir
Diagrama:
Corrida:
In-Orden
Definición:
El Recorrido “In-Orden” lo recorre de
la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido
en el Nodo Izquierdo después el Nodo Derecho y finalmente viaja a través de la
Raiz.
Detalle:
Temp toma el Valor de la Raíz y compara
si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y
terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y
viajara a través de los Arreglos Izq y Der para determinar que valor meter en
la Pila y en Temp para de esta manera imprimir el siguiente Elemento
correspondiente.
Algoritmo:
PostOrd(Arbol, Der, Izq, Pila, Raiz)
Temp → Raiz
Top →
Pila[Top] → Nulo
Si Raiz = Nulo
Imprimir “Arbol Vacio…” y Salir
Etiqueta:
Mientras Temp ≠ Nulo
Top → Top + 1
Pila[Top] → Temp
Si Der[Temp] ≠ Nulo
Top → Top + 1
Pila[Top] → - (Der[Temp])
Temp → Izq[Temp]
Temp → Pila[Top]
Top → Top - 1
Fin del ciclo
Mientras Temp ≥ 0
Imprimir Arbol[Temp]
Si Arbol[Temp] = Info[Raiz]
Salir
Temp → Pila[Top]
Top → Top - 1
Fin del ciclo
Si Temp < 0
Temp = -(Temp)
Ir a Etiqueta
Salir
Diagrama:
Corrida:
Búsqueda
Definición:
La Búsqueda es Similar a todas los
Métodos anteriores de Búsqueda, simplemente efectúa un recorrido comparando el
Elemento que deseas encontrar contra cada uno de los Elementos en los Arreglos.
Detalle:
El Algoritmo de Búsqueda compara el
Elemento a buscar con cada uno de los datos de nuestro Árbol, compara si el
Elemento con el Nodo Raíz, si no se encuentra en la Raíz… compara Elemento contra
la Raíz para empezar a viajar por el Árbol respectivamente, usa un método
similar al anterior hasta encontrar el Elemento. De otra forma la búsqueda es
fallida.
Algoritmo:
Busqueda(Arbol, Der, Izq, Pila, Raiz,
Elem)
Si Raiz = Nulo
Imprimir “Arbol Vacio”
Pos → Nulo
Pad → Nulo
Regresar Pos y Pad
Salir
Si Elem = Arbol[Raiz]
Imprimir “Elemento Encontrado”
Pos → Raiz
Pad → Nulo
Regresar Pos y Pad
Salir
Si Elem < Arbol[Raiz]
Temp → Izq[Raiz]
Temp2 → Raiz
Si no:
Temp → Der[Raiz]
Temp2 → Raiz
Mientras Temp ≠ Nulo
Si Elem = Arbol[Temp]
Imprimir “Elemento Encontrado…”
Pos → Temp
Pad → Temp2
Regresar Pos y Pad
Salir
Si Elem < Arbol[Temp]
Temp2 → Temp
Temp → Izq[Temp]
Si no:
Temp2 → Temp
Temp → Der[Temp]
Fin del ciclo
Imprimir “Elemento no Encontrado…”
Pos → Nulo
Pad → Temp2
Regresar Pos y Pad
Salir
No hay comentarios:
Publicar un comentario