Arboles Y Grafo

Conceptos básicos

Un árbol binario es una estructura recursiva, compuesta por un elemento, denominado la raíz, y por dos árboles binarios asociados, denominados subárbol derecho y subárbol izquierdo. El hecho de definir la estructura de datos en términos de sí misma es lo que hace que se denomine recursiva. El formalismo gráfico escogido para representar un árbol aparece en la figura 4.1. En él, se hace explícito que los dos subárboles tienen la misma composición estructural del árbol completo. el caso más sencillo de árbol binario es un árbol vacío, el cual no tiene elementos ni subárboles asociados. el símbolo escogido para representarlo es .

Otro formalismo posible para representar árboles binarios, cuando se quieren hacer explícitos todos los componentes de la estructura, utiliza un nombre para cada uno de los elementos del árbol y líneas para las relaciones de composición, como se muestra en la figura 4.2.

Un elemento e2 es hijo de un elemento e1, si e2 es la raíz de uno de los subárboles asociados con e1. En ese mismo caso, se dice que e1 es el padre de e2. Un elemento e2 es hermano de un elemento e3 si ambos tienen el mismo padre.

Un elemento de un árbol binario es una hoja si sus dos subárboles asociados son vacíos. En la figura 4.2, los elementos e4, e5, e6 y e7 son hojas. El formalismo gráfico para expresar que un árbol está compuesto solamente por una hoja aparece en la figura 4.3. Todo elemento de un árbol que no es una hoja se denomina un elemento no terminal o interior.

Tema 1.árbol binario

Características de un árbol

 nivel: es la distancia del nodo hasta la raíz

 su altura es la distancia máxima – 1

 al nodo, se les puede llamar de las sig. maneras

1. nodo padre: es aquel que apunta a otros nodos

2. nodo hijo: es el que deriva de otro nodo

3. nodo raíz : es el único que no tiene padre

 hojas: son todos aquellos que no tienen hijos

Definición

 el árbol binario es aquel en donde ningún nodo puede tener más de dos subárboles.

Características de un árbol binario

 no hay más de dos subárboles por nodo

 es recursivo

 estructuras de control de datos

 cada nodo puede tener 0, 1 o 2 hijos

 cada nodo puede ser la raíz de un subárbol

Clasificación

Árbol binario lleno

 es un árbol en el que cada nodo tiene 0 o 2 hijos.

Árbol perfecto

 es un árbol binario lleno en el que todas las hojas están en la misma profundidad(o altura)

Árbol completo

 un árbol binario completo es como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.

Implementación

 este tipo de árbol se puede implementar de manera estática y dinámica , en ambos casos cada nodo del árbol tendrá 3 valores

1. la información de un tipo base contenida en el nodo

2. un enlace al hijo izquierdo

3. un en lace al hijo derecho

Implementación dinámica.

La implementación dinámica de los árboles binarios es parecida a una lista doblemente ligada.

Estructura del nodo:

 un enlace al padre del nodo.

 la información contenida en el nodo.

 un enlace al hijo derecho.

 un enlace al hijo izquierdo.

 para este caso las referencias hacia el padre, el hijo izquierdo y el hijo derecho son apuntadores hacia objetos nodo, de modo que la estructura del árbol dinámico es más o menos:

Implementación estática.

 para implementar un árbol como un arreglo, es necesario declarar un nodo como un objeto. y este a su vez con un campo de información y dos de referencia.

 estos campos de referencia deben contener los índices de las celdas del arreglo en el cual se almacenan los hijos izquierdos y derechos.

Transformar un árbol general a binario

 los pasos para convertir un árbol general en un árbol binario son los siguientes:

1. deben enlazarse los hijos de cada nodo en forma horizontal (los hermanos).

2. deben enlazarse en forma vertical el nodo padre con el hijo que se encuentre más a la izquierda. además debe eliminarse el vínculo de ese padre con el resto de sus hijos.

3. debe rotarse el diagrama resultante, aproximadamente 45° hacia la izquierda, así se obtendrá el árbol binario correspondiente.

Tema 2. Recorridos en árbol

...