Arboles en programación

Solo disponible en BuenasTareas
  • Páginas : 12 (2957 palabras )
  • Descarga(s) : 0
  • Publicado : 16 de noviembre de 2011
Leer documento completo
Vista previa del texto
ÁRBOLES
CAPÍTULO 6

ÁRBOLES




Desde el punto de vista conceptual, un árbol es un objeto que comienza con una raíz (root) y se extiende en varias ramificaciones o líneas (edges), cada una de las cuales puede extenderse en ramificaciones hasta terminar, finalmente en una hoja. Los árboles representan las estructuras no-lineales y dinámicas de datos más importantes en computación.Dinámicas, puesto que la estructura árbol puede cambiar durante la ejecución de un programa. Nolineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.

Propiedades


    

En la ciencia de la computación definimos un árbol como un conjunto de nodos y líneas. Un nodo es un elemento de información que reside en el árbol. Una línea es un par de nodos ordenados , y ala secuencia de líneas se le denomina ruta (path). Además, los árboles tienen las siguientes propiedades: Tienen un nodo al que se le llama raíz del árbol. Todos los nodos, excepto la raíz, tienen una sola línea de entrada (el nodo raíz no tiene ninguna). Existe una ruta única del nodo raíz a todos los demás nodos del árbol. Si hay una ruta , entonces a „b‟ se le denomina „hijo‟ de „a‟ y es el nodoraíz de un subárbol.

Gráficamente puede representarse una estructura árbol de diferentes maneras y todas ellas equivalentes:
A
C B D I F J K L B C E G H A

Árbol por medio de diagramas de Venn

D

E

F

G

H

I

J

K

L

Árbol mediante grafo.

CARACTERÍSTICAS Y PROPIEDADES DE LOS ÁRBOLES.
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

* NODO indica un elemento, o ítem, deinformación. * Todo árbol que no es vacío, tiene un único nodo raíz. * Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. X es hijo de Y. * Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. X es padre de Y. *Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos. * Todo nodo que no tieneramificaciones (hijos), se conoce con el nombre de terminal u hoja. * Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior. * Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol. * Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición, la raíztiene nivel 1. *Altura del árbol es el máximo número de niveles de todos los nodos del árbol.

A es la raíz del árbol B es hijo de A
A es padre de B B y C son hermanos I,E,J,K,G,L son hojas

Ejemplo
A

B, D, F, C, H son; nodos interiores El grado de nodo A es 2 Nivel del nodo A es 1 (def) Nivel B es 2
Altura del árbol 4
I

B

C

D

E

F

G

H

J

K

L

LONGITUD DECAMINO INTERNO Y EXTERNO.


Se define la longitud de camino X como el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, sus descendientes directos longitud de camino 2 y así sucesivamente.
A

B

C

D

E

F

G

H

I

J

K

L

LONGITUD DE CAMINO INTERNO.


La longitud de camino internoes la suma de las longitudes de camino de todos los nodos del árbol. Es importante por que permite conocer los caminos que tiene el árbol. Puede calcularse por medio de la siguiente fórmula:
h

LCI = Σni * i
i=1



donde „i‟ representa el nivel del árbol, „h‟ su altura y „ni‟ el número de nodos en el nivel „i‟.

Ejemplo
B

A

h

LCI = Σni * i
i=1
C

D

E

F

G

H

IJ

K

L

La LCI del árbol anterior es: LCI= 1*1 + 2*2 + 5*3 + 4*4 = 36 h=4

MEDIA DE LA LONGITUD DE CAMINO INTERNO (LCIM)


 



Se calcula dividiendo la LCI entre el número de nodos del árbol (n). LCIM = LCI / n Y significa el número de arcos que deben ser recorridos en promedio para llegar, partiendo de la raíz, a un nodo cualquiera del árbol. La LCIM del árbol...
tracking img