arbolesbinarios

Á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 a lasecuencia 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

A

E
G
D

H

F
I

J

K

Árbol por medio de
diagramas de Venn

L

B

D

I

C

E

F

J

G

K

Árbol mediante grafo.

H

L

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

* NODO indica un elemento, o ítem, de información.
* Todo árbol que noes 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 tiene ramificaciones (hijos), seconoce 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íz tiene 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

Ejemplo

A es padre de B
B y C son hermanos

A

I,E,J,K,G,L son hojas

B, D, F, C, H son;
nodos interiores

B

C

El grado de nodo A es 2
Nivel del nodo A
es 1 (def)
Nivel B es 2

D

E

F

G

H

Altura del árbol 4
I

J

K

L

LONGITUD DE CAMINO INTERNO Y
EXTERNO.


Se define la longitud decamino 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

D

I

C

E

F

J

G

K

H

L

LONGITUD DE CAMINO INTERNO.


La longitud de camino interno es la suma de las
longitudes de camino de todos los nodos del árbol.
Es importante porque 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

A

h

LCI = Σni * i
i=1
B

D

I

C

E

F

J

G

K

H

L

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

MEDIA DE LA LONGITUD DE
CAMINOINTERNO (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 anterior es:


LCIM = 36 / 12 = 3

LONGITUD DE CAMINO EXTERNO.





Primero definiremos los conceptos de:
Árbol extendido es aquel en...

Leer documento completo

Regístrate para leer el documento completo.