RECORRIDO DE ARBOLES BINARIOS
Los arboles corresponden a una de las subclases de grafos de uso mas amplio, particularmente en computacion. Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. Los arboles forman parte de los no dirigidos. Sirven para organizar y relacionar datos en una base de datos, por ejemplo. Esto permite realizar operaciones de manera eficiente. Por ejemplo, un árbol de definición jerárquica se utiliza para configurar una base de datos para los registros de libros existentes en diversas bibliotecas.
En esta monografia se introducirá los siguientes temas: recorrido en arboles , búsqueda en arboles : su definicion , diferentes modos de recorrido y búsqueda .Estos temas forman parte del programa de la asignatura Matematica Discreta, correspondiente al 3o an˜ o de la carrera Ingenieria de Sistemas.
ARBOLES
Conceptos previos:
Según el libro Matematicas discretas de Elias Micha en la pagina 80 nos dice:
Un arbol es un grafo conexo que no contiene circuitos. en la actualidad los arboles son las estructuras mas utiles de las matematicas discretas y constituyen una herramienta invaluable
... ya que muchas de las clasificaciones y busquedas que realizan las computadoras pueden ser modeladas .
Segun el libro Estructura de datos de T. Parajan nos dice:
Una grafica conectada sin ningun circuito recibe el nombre de arbol , el define dos tipos de arboles : Arboles raiz y Arboles binarios.
Un arbol (libre) T , es una grafica simple que satisface : si V y W son vértices en T , entonces existe un unico camino simple de V a W.Un arbol con raiz es un árbol en el cual un vértice particular se designa como la raiz.
En la imagen se ilustra un árbol simple
ARBOLES BINARIOS
Segun el libro Estructura de datos de T. Parajan nos dice:
[2] Si todo vertice interno de todo arbol raiz tiene exactamente a lo mas 2 hijos , el arbol se denomina arbol binario completo o arbol binario.
Existen cuatro tipos de arbol binario:
3.1.1. A. B. Distinto:
Estructuras diferentes.
3.1.2. A. B. Similares:
Estructuras identicas, pero la informacion en sus nodos es diferente.
3.1.3. A. B. Equivalentes:
Son similares cuyos nodos contienen la misma informacion.
3.1.4. A. B. Completos:
Son aquellos en el que todos sus nodos tienen dos hijos , excepto los del ultimo nivel.
En la imagen se ilustra un arbol binario
4. Caracteristicas de los arboles:
En el libro de Elias Micha pag 84 nos dice que[1]
1.- En cualquier arbol dos vertices estan unidos por una unica trayectoria
2.- Todas las aristas no tiene direccion.
3.-Un arbol con n vertices tiene exactamente n-1 aristas.
4.-Cualquier grafica sin circuitos con n vertices y (n-1) aristas es un arbol.
5. Recorrido en Arboles
Segun el libro de T. Parajan nos dice que:
[2]El recorrido de un arbol es el proceso para recorrer (desplazarse a lo largo) un arbol de ma- nera sistematica a fin de que cada vertice se visite y procese exactamente una vez .Hay tres metodos para recorrer un arbol binario a saber recorridos de preorden , de inorden y de posorden.
Segun el libro de JOHNSONBAUGH Richard pag. 415 nos dice que :
[4]La busqueda a lo ancho y la busqueda a profundidad proporcionan formas de recorrer un arbol , es decir de recorrerlo de manera sistematica de modo que cada vertice sea visitado exactamente una vez.
5.1. Recorrido preorden :
Para recorrer un arbol binario no vacio en preorden, hay que realizar las siguientes opera- ciones recursivamente en cada nodo, comenzando con el nodo de raiz:
1.Visite la raiz
2.Atraviese el sub-arbol izquierdo
3.Atraviese el sub-arbol derecho
Preorden: ABDGEHICFJK
5.2. Recorrido inorden :
Para recorrer un arbol binario no vacio en inorden (simetrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
1.Atraviese el sub-arbol izquierdo
2.Visite la raiz
3.Atraviese el sub-arbol derecho
Inorden: GDBHEIACJKF
5.3. Recorrido posorden :
Para recorrer un arbol binario no vacio en postorden, hay que realizar las siguientes opera- ciones recursivamente en cada nodo:
1.Atraviese el sub-arbol izquierdo
2.Atraviese el sub-arbol derecho
3.Visite la raiz
Postorden: GDHIEBKJFCA
6. Busqueda en Arboles
Esto implica examinar cada parte del arbol hasta que el vertice o la arista deseada sea encon- trada.Podriamos profundizar moviendonos a un vertice siempre que sea posible o podriamos des plegarnos comprobando todos los vertices en un nivel antes de pasar al siguiente.
6.1. Busqueda en profundidad:
La idea basica de la busqueda en profundidad es penetrar tan profundamente como sea po- sible antes de desplegarse a otros vertices .Esto se consigue al tomar el nuevo vertice adyacente al ultimo de los posibles vertices anteriores.
6.2. Busqueda en anchura:
La idea basica de la busqueda en anchura es desplegarse a tantos vertices como sea posible antes de penetrar en profundidad dentro de un arbol.Esto significa que visitaremos todos los vertices adyacentes a uno dado antes de cambiar de nivel.
preorden
22,15,3,8,40,45,13,20,30,1,7,34,48,53,9,23,12,51,4,10
inorden
22,15,3,1,8,7,4,13,9,12,10,20,40,30,23,34,45,48,53,51
postorden
1,4,7,10,12,9,13,8,3,20,15,23,34,30,51,53,48,45
PILA SEMÁNTICA DE UN ANALIZADOR SINTÁCTICO
Introducción
Aqui les mostraremos un poco de lo que es la definicion de los siguientes conceptos en cuanto analisis semantico y los subtemas que veremos en la primera unidad de lenguajes y automatas 2
el objetivo de esta unidad es definir, diseñar, construir y programarlas fases de el analizador lexico y sintactico de un traductoro compilador.
Analisis Semantico
¿Que es un analisis semantico?
bueno se refiere a los aspectos del significado, sentido o interpretacion de el mismo de un determinado elemento, simbolo, palabra, expresion o representacion formal
determina el tipo de resulados intermedios y que si los argumentos que tiene un operador pertenece al conjunto de los operadores posibles.
revisa si el significado de lo que se va leyendo es valido.
el resultado de la fase de analisis semantico viene siendo lo que se conoce como "arbol semantico"
Arbol De Expresiones o Arbol Semántico
Es una estructura jerarquica en la cual se registran las operaciones que realiza el programa fuente, en cada una de las ramas de el arbol se registra el valor o significado que este debe tener y el analisis analiza cual de los valores registrado en las ramas es aplicable
ACCIONES SEMÁNTICAS
Dependiendo del tipo de sentencias, las acciones semánticas pueden agruparse en: Sentencias de Declaración: Completar la sección de tipos de la Tabla de
Símbolos.
Sentencias “ejecutables”: Realizar comprobaciones de tipos entre los operandos
implicados.
Funciones y procedimientos: Comprobar el número, orden y tipo de los
parámetros actuales en cada llamada a una función o procedimiento.
Identificación de variables: Comprobar si un identificador ha sido declarado
antes de utilizarlo.
Etiquetas: Comprobar si hay etiquetas repetidas y validación.
Constantes: Comprobar que no se utilicen en la parte izquierda de una asignación.
Conversiones y equivalencias de tipo: Verificación.
Sobrecarga de operadores y funciones: Detectar y solventar.
Comprobación de tipo en expresiones
E à literal {E.tipo = char}
E à num {E.tipo = entero}
E à id {E.tipo = Consultar_TS(id.entrada)}
E à id [E1] {id.tipo = Consultar_TS(id.entrada)}
Pila semantica en un analizador sintactico
Como podemos entender un analizador sintactico ascendente utiliza durante el análisis una pila. En esta va guardando datos que le permiten ir haciendo las operaciones de reducción que necesita.
Para incorporar acciones semánticas como lo es construir el árbol sintáctico, es necesario incorporar a la pila del analizador sintactico ascendente otra columna que guarde los atributos de los símbolos que se van analizando.
Para incorporar acciones semánticas como lo es construir el árbol sintáctico, es necesario incorporar a la pila del analizador sintactico ascendente otra columna que guarde los atributos de los símbolos que se van analizando.
Generacion de tablas de simbolos y de direcciones
También se la llama tabla de nombres o tabla de identificadores y tiene dos funciones
principales:
- Efectuar chequeos semánticos.
- Generación de código.
Permanece sólo en tiempo de compilación, no de ejecución, excepto en aquellos casos en
que se compila con opciones de depuración.
La tabla almacena la información que en cada momento se necesita sobre las variables del
programa, información tal como: nombre, tipo, dirección de localización, tamaño, etc.
Manejo de errores semánticos
Los errores semánticos son más sutiles. Un error semántico se produce cuando la sintaxis del código es correcta, pero la semántica o significado no es el que se pretendía. La construcción obedece las reglas del lenguaje, y por ello el compilador o intérprete no detectan los errores semánticos. Los compiladores e intérpretes sólo se ocupan de la estructura del código que se escribe, y no de su significado. Un error semántico puede hacer que el programa termine de forma anormal, con o sin un mensaje de error.
CÓDIGOS DE LOS RECORRIDOS DE LOS ÁRBOLES BINARIOS(PREORDEN, INORDEN Y POSTORDEN)
