Tarea estructuras
Páginas: 5 (1095 palabras)
Publicado: 17 de febrero de 2012
INTRODUCCIÓN
Primeramente busque datos en páginas de Internet de las cuales tan solo obtuve información de unas de ellas que están especificadas en la bibliografía. De estas páginas Web obtuve muchos de los ejemplos. También he buscado libros, del cual obtuve información. Al principio no sabía mucho sobre el tema así que me ha sido muy útil este trabajo. De todas maneras no he recopilado todala información que hubiese querido del trabajo ya que no existe tanta información sobre el tema en Internet. La intención inicial era la de conocer acerca de los árboles binarios, recorridos inorden, preorden y postorden de expresiones y apuntadores en fila o cola circular, así como sus ejemplos, como se trabaja con ellos, etc. Creo que lo he conseguido en gran medida y que este trabajo me ha dadolas respuestas que esperaba como objetivo del trabajo
RECORRIDO EN ÁRBOLES BINARIOS
Una de las operaciones mas importantes a realizar en un árbol binario es el recorrido de los mismos, recorrer significa visitar los nodos del árbol en forma sistemática, de tal manera que todos los nodos del mismo sean visitados una sola vez.
Existen 3 formas diferentes de efectuar el recorrido y todasellas de naturaleza recursiva, estas son:
RECORRIDO PREORDEN: En el que se procesa el nodo y después se procesan recursivamente sus hijos.
RECORRIDO POSTORDEN: Donde el nodo dado se procesa después de haber procesado recursivamente a sus hijos.
RECORRIDO INORDEN: En este se procesa recursivamente el hijo izquierdo, luego se procesa el nodo actual y finalmente se procesa recursivamente elhijo derecho.
Hay un último recorrido que implementa a estos 3.
RECORRIDI POR NIVELES: Este recorrido procesa los nodos comenzando en la raíz y avanzando de forma descendente y de izquierda a derecha.
RECORRIDO PREORDEN
• VISITAR LA RAIZ
• RECORRER EL SUBARBOL IZQUIERDO
• RECORRER EL SUBARBOL DERECHO
Recorrido en preorden: consiste en visitar el nodo actual (visitar puedeser simplemente mostrar la clave del nodo por pantalla), y después visitar el subárbol izquierdo y una vez visitado, visitar el subárbol derecho. Es un proceso recursivo por naturaleza.
[pic]
PREORDEN: A-B-D-E-C-F-G
[pic]
RECORRIDO POSTORDEN
En este caso se trata primero el subárbol
izquierdo, después el derecho y por último
el nodo actual. Enel árbol de la figura el
recorrido en postorden sería: 2, 5, 11, 6,
7, 4, 9, 5 y 2.
RECORRIDO INORDEN
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un AB este recorrido daría los valores de clave ordenados de menor a mayor. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4 y 9.Comparemos Otros Recorridos:
[pic]
Pre Orden (RID) 18, 12, 5, 9, 28, 20, 35
En Orden (IRD) 5, 9, 12, 18, 20, 28, 35
Post Orden (IDR) 9, 5, 12, 20, 35, 28, 18
[pic]
El recorrido en Pre Orden del árbol es el siguiente: 15, 6, 4, 10, 20, 17, 22
Recorrido En Orden(IRD)
El recorrido en En Orden del árbol es el siguiente: 4, 6, 10, 15, 17, 20, 22
RecorridoPost Orden(IDR)
El recorrido en Post Orden del árbol es el siguiente: 4, 10, 6, 17, 22, 20, 15
FILAS O COLAS CIRCULARES
Primeramente quiero dar una breve introducción de lo que son las colas, para luego entrar en el tema de lleno.
Una cola es una estructura de almacenamiento, donde la podemos considerar como una lista de elementos, en la que éstos van a ser insertados por un extremo yserán extraídos por otro.
Las colas son estructuras de tipo FIFO (first-in, first-out) (primero en entrar, primero en salir), ya que el primer elemento en entrar a la cola será el primero en salir de ella.
El nombre mas común de ésta estructura de datos es “cola” aunque yo la preferiría llamar “fila” por razones obvias.
Esta estructura de datos funciona como una fila de turnos, al primero que...
Primeramente busque datos en páginas de Internet de las cuales tan solo obtuve información de unas de ellas que están especificadas en la bibliografía. De estas páginas Web obtuve muchos de los ejemplos. También he buscado libros, del cual obtuve información. Al principio no sabía mucho sobre el tema así que me ha sido muy útil este trabajo. De todas maneras no he recopilado todala información que hubiese querido del trabajo ya que no existe tanta información sobre el tema en Internet. La intención inicial era la de conocer acerca de los árboles binarios, recorridos inorden, preorden y postorden de expresiones y apuntadores en fila o cola circular, así como sus ejemplos, como se trabaja con ellos, etc. Creo que lo he conseguido en gran medida y que este trabajo me ha dadolas respuestas que esperaba como objetivo del trabajo
RECORRIDO EN ÁRBOLES BINARIOS
Una de las operaciones mas importantes a realizar en un árbol binario es el recorrido de los mismos, recorrer significa visitar los nodos del árbol en forma sistemática, de tal manera que todos los nodos del mismo sean visitados una sola vez.
Existen 3 formas diferentes de efectuar el recorrido y todasellas de naturaleza recursiva, estas son:
RECORRIDO PREORDEN: En el que se procesa el nodo y después se procesan recursivamente sus hijos.
RECORRIDO POSTORDEN: Donde el nodo dado se procesa después de haber procesado recursivamente a sus hijos.
RECORRIDO INORDEN: En este se procesa recursivamente el hijo izquierdo, luego se procesa el nodo actual y finalmente se procesa recursivamente elhijo derecho.
Hay un último recorrido que implementa a estos 3.
RECORRIDI POR NIVELES: Este recorrido procesa los nodos comenzando en la raíz y avanzando de forma descendente y de izquierda a derecha.
RECORRIDO PREORDEN
• VISITAR LA RAIZ
• RECORRER EL SUBARBOL IZQUIERDO
• RECORRER EL SUBARBOL DERECHO
Recorrido en preorden: consiste en visitar el nodo actual (visitar puedeser simplemente mostrar la clave del nodo por pantalla), y después visitar el subárbol izquierdo y una vez visitado, visitar el subárbol derecho. Es un proceso recursivo por naturaleza.
[pic]
PREORDEN: A-B-D-E-C-F-G
[pic]
RECORRIDO POSTORDEN
En este caso se trata primero el subárbol
izquierdo, después el derecho y por último
el nodo actual. Enel árbol de la figura el
recorrido en postorden sería: 2, 5, 11, 6,
7, 4, 9, 5 y 2.
RECORRIDO INORDEN
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un AB este recorrido daría los valores de clave ordenados de menor a mayor. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4 y 9.Comparemos Otros Recorridos:
[pic]
Pre Orden (RID) 18, 12, 5, 9, 28, 20, 35
En Orden (IRD) 5, 9, 12, 18, 20, 28, 35
Post Orden (IDR) 9, 5, 12, 20, 35, 28, 18
[pic]
El recorrido en Pre Orden del árbol es el siguiente: 15, 6, 4, 10, 20, 17, 22
Recorrido En Orden(IRD)
El recorrido en En Orden del árbol es el siguiente: 4, 6, 10, 15, 17, 20, 22
RecorridoPost Orden(IDR)
El recorrido en Post Orden del árbol es el siguiente: 4, 10, 6, 17, 22, 20, 15
FILAS O COLAS CIRCULARES
Primeramente quiero dar una breve introducción de lo que son las colas, para luego entrar en el tema de lleno.
Una cola es una estructura de almacenamiento, donde la podemos considerar como una lista de elementos, en la que éstos van a ser insertados por un extremo yserán extraídos por otro.
Las colas son estructuras de tipo FIFO (first-in, first-out) (primero en entrar, primero en salir), ya que el primer elemento en entrar a la cola será el primero en salir de ella.
El nombre mas común de ésta estructura de datos es “cola” aunque yo la preferiría llamar “fila” por razones obvias.
Esta estructura de datos funciona como una fila de turnos, al primero que...
Leer documento completo
Regístrate para leer el documento completo.