Arbol

Árbole
s

Acerca de arboles






Los árboles representan las estructuras
de datos no lineales y dinámicas mas
importantes en computación
Dinámicas porque la estructura puede
cambiar durante la ejecución del
programa
No lineales, puesto que a cada
elemento del árbol puede seguirle
varios elementos

Estructuras estáticas y
dinámicas
Estructuras estáticas

Estructurasdinámicas

Arreglos

Listas

Registros

Árboles

Conjuntos

Estructuras lineales y no
lineales
Estructuras lineales
Arreglos
Registros
Conjuntos
Pilas
Colas
Listas

Estructuras no
lineales
Árboles

Árbol
Es una estructura jerárquica aplicada
sobre una colección de elementos u
objetos llamados nodos, uno de los
cuales es conocido como raíz. Además
se creanrelaciones o parentesco entre
nodos dando lugar a términos como:
padre, hijo, hermano, antecesor,
sucesor, ancestro, etc.

Definición formal de Árbol
Es una estructura homogénea que
es la concatenación de un
elemento junto con un número
finito de árboles disjuntos,
llamados subárboles. Una forma
particular de árbol es la
estructura vacía.

Aplicaciones de
Árboles






Representar formulas matemáticas
Organizar adecuadamente información
Registrar la historia de un campeonato
de tenis
Construir un árbol genealógico
Análisis de circuitos eléctricos
Enumerar los capítulos y secciones de
un libro

Representacion de
arboles


Diagramas de Venn

G

D

A

B

C
E

F

E

Anidacion de
paréntesis
(A(B(D(I,E,F(J,K)),C(G,H(L))))

Notacióndecimal DEWEY

1.A, 1.1.B, 1.1.1.D, 1.1.1.1.I,
1.1.2.E,1.1.3.F

Notacion
indentada
A
B
D
I
E
J
G
L

CARACTERISTICAS Y
PROPIEDADES DE LOS
ÁRBOLES









TODO ARBOL QUE NO ES VACIO, TIENE UN UNICO NODO RAIZ.
UN NODO X ES DESCENDIENTE DE UN NODO Y, SI EL NODO X
ESTA APUNTADO POR EL NODO Y. EN ESTE CASO SE UTILIZA LA
EXPRESION X ES HIJO DE Y.
UN NODO X ESANTECESOR DIRECTO DE UN NODO Y, SI EL NODO
X APUNTA AL NODO Y. EN ESTE CASO SE UTILIZA LA EXPRESIÓN X
ES PADRE DE Y.
SE DICE QUE TODOS LOS NODOS QUE SON DESCENDIENTES
DIRECTOS DE UN MISMO NODO PADRE, SON HERMANOS.
TODO NODO QUE NO TIENE RAMIFICACIONES(HIJOS),SE CONOCE
COMO TERMINAL U HOJA.

Continuacion…










TODO NODO QUE NO ES RAIZ , NI TERMINAL U HOJA SE
CONOCE COMO“INTERIOR”.
GRADO.- ES EL NUMERO DE DESCENDIENTES DIRECTOS DE UN
DETERMINADO NODO.
GRADO DEL ARBOL.- ES EL MAXIMO GRADO DE TODOS LOS
NODOS DEL ARBOL.
NIVEL.- ES EL NUMERO DE ARCOS QUE DEBEN SER
RECORRIDOS PARA LLEGAR A UN DETERMINADO NODO. POR
DEFINICION LA RAIZ TIENE NIVEL 1.
ALTURA.- ES EL MAXIMO NUMERO DE NIVELES DE TODOS LOS
NODOS DEL ARBOL.

GRAFO
Ejemplo

Grafo
ejemplo
X

YGrafo
ejemplo
A

C

B

D

I

E

F

J

G

K

H

L

LONGITUD DE CAMINO
INTERNO


Es la suma de las longitudes de camino
de todos los nodos del arbol.
h

LCI   ni * i
I 1

I = representa el nivel del arbol, h altura y ni el numero de nodos
en el nivel
EJEMPLO:
LCI= 1*1 + 2*2 + 5*3 +4*4 = 36
LA LCIM=LCI/n n Numero de nodos en el arbol

LONGITUD DECAMINO
EXTERNO
ARBOL EXTENDIDO.- es aquel en el que el
número de hijos de cada nodo es igual
al grado del árbol. Si alguno de los
nodos no cumple la condición entonces
se debe incorporar al mismo nodos
especiales.

extendido
h 1

LCE   nei * i

A

I 2

C

B

D

I

E

F

G

J

K

H

L

LONGITUD DE CAMINO
EXTERNO


Se define como la suma de laslongitudes de camino de todos los
nodos especiales del arbol. Se calcula
por medio de:
h 1

LCE   nei * i
I 2

Ejercicio(10 puntos)
Dado el siguiente arbol
A

B

E

D

C

F

G

H

I

J

K

Calcular la longitud de camino interno y la
longitud de camino externo y la media de
cada uno de ellos

L

M

Árboles
binarios




Un árbol ordenado es aquel...