Estrcutura De Datos Trabajo Final

INSTITUTO TECNOLOGICO DE VILLAHERMOSA

MATERIA
ESTRUCTURA DE DATOS

PROFESOR
JOSE INES MENDEZ GAMAS

TRABAJO
UNIDAD 5 ESTRUCTURAS NO LINEALES ESTÁTICAS Y DINAMICAS
UNIDAD 6 ORDENACION INTERNA
UNIDAD 7 ORDENACION EXTERNA
UNIDAD 8 METODOS DE BUSQUEDA

ALUMNA
RODRIGUEZ AGUILAR ELIDA

INDICE

UNIDAD 5
ESTRUCTURAS NO LINEALES ESTATICAS Y DINAMICAS

5.1 CONCEPTODE ARBOLES
EJEMPLO
5.1.1 CLASIFICACION DE LOS ARBOLES
EJEMPLO
5.2 OPERACIONES BASICAS SOBRE ARBOLES BINARIOS
5.2.1 CREACIÓN
5.2.2 INSERCIÓN
5.2.3 ELIMINACIÓN
5.2.4 RECORRIDOS SISTEMATICOS
5.2.5 BALANCEO

UNIDAD 6
ORDENACION INETRNA

6.1ALGORITMOS DE ORDENAMIENTO POR INTERCAMBIO
6.1.1 BURBUJA
6.1.2 QUICKSORT
6.1.3 SHELLSORT
6.2ALGORITMOS DE ORDENAMIENTO PORDISTRIBUCIÓN
6.2.1 RADIX

UNIDAD 7
ORDENACIÓN EXTERNA

7.1 ALGORITMOS DE ORDENACION EXTERNA
7.1.1 INTERCALACIÓN DIRECTA
7.1.2 MEZCLA NATURAL

UNIDAD 8
METODOS DE BUSQUEDA

8.1 ALGORITMOS DE ORDENACION EXTERNA
8.1.1 SECUENCIAL
8.1.2 BINARIA
8.1.3 HASH
8.2 BUSQUEDA EXTERNA
8.2.1 SECUENCIAL
8.2.2 BINARIA
8.2.3 HASH

UNIDAD 5
ESTRUCTURAS NO LINEALES ESTATICAS Y DINAMICAS
5.1CONCEPTO DE ARBOLES

Las Listas Ligadas por lo general proporcionan mayor flexibilidad que los arreglos, pero son estructuras lineales y es difícil utilizarlas para organizar una representación jerárquica de los objetos. Aun cuando las pilas y colas reflejan cierta jerarquía, están limitadas a una sola dimensión. Para superar esta limitación, creamos un tipo de datos nuevos llamado árbol que secompone de nodos y arcos. A diferencia de los arboles naturales, estos árboles se representan de arriba abajo con la raíz en la parte superior de las hojas (nodos terminales) en la parte inferior. La raíz es un nodo que no tiene padre; sólo puede tener nodos hijos. La hojas, por otro lado, no tiene hijos, o en vez de ello, sus hijos son nulos. Un árbol puede definirse de manera recursiva como sigue:1. Una estructura vacía es un árbol vacío.
2. Si t1,…, tk son árboles disjuntos, entonces la estructura cuya raíz tiene como sus hijos a las raíces de t1,…, tk también es un árbol.
3. Solo las estructuras generadas pro las reglas 1 y 2 son árboles.

La definición de un árbol no impone ninguna condición sobre el número de hijos de un nodo dado. Este número puede variar de 0 a cualquierentero. En los arboles jerárquicos, esta es una propiedad bienvenida.

Ejemplo

5.1.1 CLASIFICACION DE LOS ARBOLES

Árbol Binario Distinto
Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.
Ejemplo

Árbol Binario Similar
Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.Ejemplo

Árbol Binario Equivalente
Son aquellos arboles que son similares y que además los nodos contienen la misma información.
Ejemplo

Árbol Binario Completo
Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.
5.2 OPERACIONES BASICAS SOBRE ARBOLES BINARIOS
Definición de Árbol Binario

Un árbolbinario es un árbol cuyos nodos tienen dos hijos (posiblemente vacíos), y cada hijo se designa ya sea como hijo izquierdo o como hijo derecho.
Ejemplo de Árbol Binario

5.2.1 CREACIÓN

Se deben crear nodos donde cada uno de ellos tenga 3 campos estructurados de la siguiente forma:
* El campo info: que almacenar  los datos del nodo N.
* El campo izq: que tendrá la localización delhijo izquierdo del nodo N.
* El campo der: que tendrá la localización del hijo derecho  del nodo N.
Además necesitamos una variable llamada raíz que nos permita acceder a la estructura desde ella como el nodo principal.

5.2.2 INSERCIÓN

Para insertar un nodo nuevo con al llave el, debe buscarse un nodo del árbol con un punto muerto y el nodo nuevo tiene que adjuntarse al mismo. Un nodo de...