Arboles

ARBOL
•Definición, Componentes, Representación en memoria

•Árbol Enraizado, Árbol Binario, Árbol Equilibrado, Árbol
de Huffman, Árbol del montículo
•Generación de un árbol de expresiónAritmética

Definición
 Un Árbol T(V, A) es un grafo conexo acíclico de estructura jerárquica.

Donde:



V = {conjunto de nodos}
A = {conjunto de aristas}

T:

A

Si |V|=n
.¨.|A|=n-1
BC

E

D

F

Componentes
 Nodo Raíz: Del cual descienden todos los otros nodos.
 Nodo Padre: Del cual descienden todos los hijos.
 Nodos Hijos o Hermanos: Son todos los nodos quetienen el











mismo padre.
Nodos Terminales o Hojas: Son los nodos que no tienen más
descendientes.
Nodos Internos: Todos los nodos que no son hojas.
Nodos Externos: Todoslos nodos que son hojas.
Grado de un Nodo: Número de descendientes directos.
Grado de un Árbol: Máximo grado de un nodo.
Longitud del Árbol:
Número de arcos que deben ser recorridos
desde la raízhasta ese nodo.
Profundidad: Es la longitud entre la raíz y ese nodo.
Altura: Es la longitud entre ese nodo y las hojas.

Ejemplo
Nivel

0

A

B

E

F

C

G

H

M

I

N

1D

J

K

L

2
3

Árbol Enraizado
Cuando todos los nodos tienen al menos 1 descendiente

Nivel

0

A

|A|=13
|V|=12
B

C

Nodos internos:
[A,B,D,F,J]
E

Nodosterminales (Hojas):
K
[C,E,G,H,K,L]

F

G

L

1

D

H

I

J

M

2

3

Árbol Enraizado: Representación en memoria
Raíz

Padre-Raíz
A

B

C

D

Árbol Binario
 Esbinario cuando todos los nodos tienen a lo más 2

descendientes.
 Tiene una estructura bien definida
N

I

Padre raíz

D

subizquierdo subderecho

N(nodos)= 2n+1 – 1
n = nivel

ÁrbolBinario: Representacion en
memoria
Lista Nodos
IZQ INFO DER
IZQ INFO DER

Nodo Çabecera
Nodos: Peso (w)

A

B

D

C

E

Árbol Extendido de1 Árbol Binario

B

D

0

A

A...