Monografias.com > Matemáticas
Descargar Imprimir Comentar Ver trabajos relacionados

Recorrido y busqueda en arboles




Enviado por Lizbeth



  1. Introducción
  2. Arboles
  3. Arboles binarios
  4. Características de los
    arboles
  5. Recorrido en arboles
  6. Búsqueda en arboles
  7. Referencias

1.
INTRODUCCION

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 arbol de definicion jerarquica
se utiliza para configurar una base de datos para los registros
de libros existentes en diversas bibliotecas.

En esta monografia se introducira los
siguientes temas: recorrido en arboles , busqueda en arboles : su
definicion , diferentes modos de recorrido y busqueda .Estos
temas forman parte del programa de la asignatura Matematica
Discreta, correspondiente al 3o an˜ o de la carrera
Ingenieria de Sistemas.

2.
ARBOLES

2.1. Conceptos previos:

Segun el libro Matematicas discretas de
Elias Micha en la pagina 80 nos dice:

[1] 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:

[2] Una grafica conectada sin ningun circuito recibe
el nombre de arbol , el define dos tipos de arboles : Arboles
raiz y Arboles binarios.

Segun el libro Matematicas Discretas
Richard JOHNSONBAUGH en la pagina 377 nos dice:

[4] Un arbol (libre) T , es una grafica simple que
satisface : si V y W son vertices en T , entonces existe un unico
camino simple de V a W.Un arbol con raiz es un arbol en el cual
un vertice particular se designa como la raiz.

En la imagen se ilustra un arbol
simple

Monografias.com

3. ARBOLES
BINARIOS

3.1. Concepto:

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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.

Monografias.com

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.

Monografias.com

Referencias

[1] MICHA Elias (1890), Matematicas
Discretas
(Segunda edicion). Mexico

[2] T. Parajan (2005) Matematicas
Discretas
. USA

[3] ESPINOZA ARMENTA, Ramon (2010)
Matematicas Discretas.Mexico

[4] JOHNSONBAUGH , Richard (2005)
Matematicas Discretas (Cuarta Edicion).
Mexico

AGRADECIMIENTO

Primero y antes que nada, dar gracias a
Dios, por estar conmigo en cada paso que doy, por fortalecer mi
corazon e iluminar mi mente y por haber puesto en mi camino a
aquellas personas que han sido mi soporte y compan˜ia
durante todo el periodo de estudio. Agradecer hoy y siempre a mi
familia por el esfuerzo realizado por ellos. El apoyo en mis
estudios, de ser asi no hubiese sido posible. A mis padres y
demas familiares ya que me brindan el apoyo, la alegria y me dan
la fortaleza necesaria para seguir adelante.

Un agradecimiento especial al Ingeniero
Elmer Coyla Idme, por la colaboracion, paciencia y apoyo
incondicional q me brinda dia a dia.

DEDICATORIA

La concepcion de este proyecto estadedicada
a mis padres, pilares fundamentales en mi vida.

Sin ellos, jamas hubiese podido conseguir
lo que hasta ahora logre. Su tenacidad y lucha insaciable han
hecho de ellos el gran ejemplo a seguir y destacar, no solo para
mi, sino para mis hermanos y familia en general.

A ellos este proyecto, que sin ellos, no
hubiese podido ser.

 

 

Autor:

Lizbeth Llanos Tintaya

Puno – Peru

2013

UNIVERSIDAD NACIONAL DEL
ALTIPLANO

FACULTAD DE INGENIERA MECANICA ELECTRICA,
ELECTRONICA Y SISTEMAS ESCUELA PROFESIONAL DE INGENIERIA DE
SISTEMAS

Monografias.com

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter