arboles


Ingeniería en Sistemas Computacionales

Génesis Angélica Rosas Mosqueda

Estructura de Datos


ARBOLES

Docente: Ing. Rafael de la Cruz Pérez


4-Noviembre-2013
INDICE
PORTADA………………………………………………………………………. 1
INDICE…………………………………………………………………………… 2
ARBOLES……………………………………………………………………….. 3
Declaraciones de tipo para manejar árboles en C
CLASIFICACION DE ARBOLES……………………………………………… 6Arbol binario
Arboles binarios completos
Conversión de árboles no binarios a binarios
OPERACIONES BASICAS DE LOS ARBOLES BINARIOS DE BUSQUEDA………………………………………………………………………. 9
Otras operaciones
Utilización de los arboles binarios de búsqueda
Aplicación arboles binarios de búsqueda
ARBOLES BALANCEADOS (AVL)…………………………………………….13
Operaciones básicas de los arboles AVL
Otras operacionesAplicación arboles AVL
QUE SON LOS ARBOLES B…………………………………………………… 17
Operaciones básicas de los arboles B
Otras operaciones
Utilización de los arboles B
Aplicación arboles B
QUE SON LOS GRAFOS………………………………………………………… 22
Operaciones básicas de los grafos
Otras operaciones
Utilización de grafos
Aplicación grafos
CONCLUSION Y BIBLIOGRAFIA……………………………………………….. 25
ARBOLES
Un árbol es una estructura nolineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

Definiremos varios conceptos. En relación con otros nodos:
Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol.
Nodo padre: nodo que contiene un puntero al nodo actual.
En cuanto a laposición dentro del árbol:
Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol.
Nodo hoja: nodo que no tiene hijos.
Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo númerode punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos.
Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo.
Un árbol en el que en cada nodo o bien todos oninguno de los hijos existe, se llama árbol completo.
Existen otros conceptos que definen las características del árbol, en relación a su tamaño:
Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
Grado: el número de hijosque tiene el elemento con más hijos dentro del árbol.
Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente.
Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemoshablar de altura de ramas.

Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios.
Frecuentemente, aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través del árbol, añadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, yno sólo hacia las hojas.
Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, si perdemos este nodo, perderemos el acceso a todo el árbol.
El nodo típico de un árbol difiere de los nodos que hemos visto hasta ahora para listas, aunque sólo en el número de nodos. Veamos un ejemplo de nodo para crear árboles de orden tres:
struct nodo {...