Estructuras ArbolesBinarios

Árbol: definición
™Árbol (del latín arbor –oris):
ƒ Planta perenne, de tronco leñoso y elevado, que se
ramifica a cierta altura del suelo.
ƒ (otras, ver Real Academia Española…)

Árboles binarios
Franco Guidi Polanco
Escuela de Ingeniería Industrial
Pontificia Universidad Católica de Valparaíso, Chile
fguidi@ucv.cl

Actualización: 13 de mayo de 2005
Franco Guidi Polanco

Árbol: definición(cont.)

Árbol: definición (cont.)

™Árbol:
ƒ Grafo conexo, no orientado y acíclico.

™Árbol:
ƒ Una estructura de datos accesada desde un nodo raíz.
Cada nodo es ya sea una hoja o un nodo interno. Un
nodo interno tiene uno o más nodos hijos, y se le llama
padre de sus nodos hijos.

C
E

A

2

ƒ Un árbol es, ya sea:
• un conjunto vacío, o
• una raíz con cero
o más árboles

B
D
H

Franco Guidi Polanco3

Franco Guidi Polanco

4

Hojas y nodos internos

Representación de un árbol

™Una hoja es cualquier nodo que tiene sus hijos
vacíos.
™Un nodo interno es cualquier nodo con al menos
un hijo no vacío.

subárbol

b

a
b
e

f

h
5

c

h

d
j

i
l

e

j

i

subárbol

m

k

subárbol

Franco Guidi Polanco

6

Nodos padres e hijos
™Las raíces de los subárboles de un árbol son hijos
de la raíz delárbol.
™Existe un arco desde cada nodo a cada uno de sus
hijos, y se dice que este nodo es padre de sus
hijos.

a

g

d

subárbol

Representación de un árbol (cont.)

f

h

l

Franco Guidi Polanco

b

g

f
g

Hojas

c

Nodos internos

c

d

raíz

a

e
k

m

subárbol de nodo e

subárboles de
nodo b
subárboles de
nodo c
Franco Guidi Polanco

7

Franco Guidi Polanco

8

Ruta y largo de una rutaAncestros y descendientes

™Si n1, n2,... nk es una secuencia de nodos en un
árbol, de modo que ni es padre de ni + 1, para
1<=i<=k, entonces esta secuencia se llama ruta
desde n1 a nk.
™El largo de esta ruta es k.

a

n1

b

c

d

™Si existe una ruta desde un nodo A a un nodo B,
entonces A es ancestro de B y B es
descendiente de A.
™Luego, todos los nodos de un árbol son
descendientes de la raíz delárbol, mientras que la
raíz es el ancestro de todos los nodos.

n2

e

f
g

n3

h

Franco Guidi Polanco

9

Altura

Franco Guidi Polanco

10

Niveles

™La altura de un nodo M de un árbol corresponde
al número de nodos en la ruta desde la raíz hasta
M.
™La altura de un árbol corresponde a la altura del
nodo más profundo.

™Todos los nodos de altura d están en el nivel d en
el árbol.
™La raíz está enel nivel 1, y su altura es 1.

a

Nivel 1

a
b

Altura del
nodo=2

c

Nivel 3

Altura del árbol=4

d

e

f
Nivel 4

g
Franco Guidi Polanco

b

Nivel 2

d

c
e

f
g

h

h
11

Franco Guidi Polanco

12

Árboles binarios

Representación de un árbol binario (I)

™Un A.B. está constituido por un conjunto finito de
elementos llamados nodos.

raíz
subárbol izquierdo

a

™Un árbol binario:

b

ƒ no tienenodos (está vacío); o
ƒ tiene un nodo llamado raíz, junto con otros dos árboles
binarios llamados subárboles derecho e izquierdo
de la raíz.

d

subárbol derecho

c
e

f
g

h

Nota: Una parte importante del material presentado en esta sección
fue elaborado por Marcelo Silva F.
Franco Guidi Polanco

13

Representación de un árbol binario (II)

Franco Guidi Polanco

14

Igualdad de árbolesbinarios
™Para ser iguales, dos árboles deben tener tanto la
misma estructura, como el mismo contenido.

raíz

a
subárbol derecho

b
d
subárbol izquierdo

c
e

f
g

a

h
b

Franco Guidi Polanco

15

Franco Guidi Polanco

≠

a
b

16

Árboles binarios llenos

Árboles binarios completos

™Un árbol binario lleno es aquel en que cada nodo
es un nodo interno con dos hijos no vacíos, o una
hoja.

a
b
d

™Unárbol binario completo tiene una forma
restringida, que se obtiene al ser llenado de
izquierda a derecha. En un A.B. Completo de
altura d, todos los niveles, excepto posiblemente el
nivel d están completamente llenos.

a
c

e

b
f

g
No es A.B. lleno

c
e

h

a
f

g

b

Es un A.B. completo
pero no es un A.B. lleno

h

d

c
e

f

Es A.B. lleno

Franco Guidi Polanco

17

Franco Guidi Polanco

18...