Arboles

Árboles
1

Definición
Un árbol dirigido es una estructura:
 Jerárquica porque los componentes están a
distinto nivel.
 Organizada porque importa la forma en que
esté dispuesto el contenido.
 Dinámica porque su forma, tamaño y
contenido pueden variar durante la ejecución.
Un árbol puede ser:
 vacío,
 Una raíz + subárboles.
2

Representación de un Árbol.
 Mediante diagramasde Venn
a
b

c

d

e
f
a

b

 Mediante círculos y flechas
e

c

d

f

 Mediante paréntesis anidados:

( a ( b (e,f), c, d ) )
3

Conceptos Básicos
 Si hay un camino de A hasta B, se dice que A es






antecesor de B, y que B es sucesor de A.
Padre es el antecesor inmediato de un nodo
Hijo, cualquiera de sus desc}ientes inmediatos.
Descendiente deun nodo, es cualquier sucesor de
dicho nodo.
Hermano de un nodo, es otro nodo con el mismo
padre.
Generación, es un conjunto de nodos con la misma
profundidad.
4

Conceptos Básicos (cont.)
 Raíz es el nodo que no tiene ningún predecesor (sin






padre).
Hoja es el nodo que no tiene sucesores (sin hijos)
(Terminal). Los que tienen predecesor y sucesor se
llaman nodosinteriores.
Rama es cualquier camino del árbol.
Bosque es un conjunto de árboles desconectados.
Nivel o profundidad de un nodo, es la longitud del
camino desde la raíz hasta ese nodo.
El nivel puede de}irse como 0 para la raíz y nivel
(predecesor)+1 para los demás nodos.
5

Conceptos Básicos (cont.)
 Los nodos de la misma generación tienen el

mismo nivel.
 Grado de un nodo, es elnúmero de flechas
que salen de ese nodo (hijos). El número de
las que entran siempre es uno.
 Grado de un árbol, es el mayor grado que
puede hallarse en sus nodos.
 Longitud del camino entre 2 nodos: es el
número de arcos que hay entre ellos.
6

Conceptos Básicos (cont.)
Raíz
hijo
Padre
Hermano

hoja

Subárbol

Nivel de profundidad = 7
Grado de un nodo = 3
Grado del árbol = 37

Tipos de árboles
Un árbol ordenado: Es aquel en el que las
ramas de los nodos están ordenadas.
 Los de grado 2 se llaman árboles binarios.
 Cada árbol binario tiene un subárbol
izquierda y subárbol derecha.
+

A

^
/

B
C

3.5
D

8

Tipos de árboles (cont.)
Árboles de expresión
 Representan un orden de ejecución

*

+

+

*
A

+
B

E

*
C

(A* B)+ C * D + E

-

D

7

12

9

(7 + 12) * (-9)  -171

9

Tipos de árboles (cont.)
 Árboles similares: Los que tienen la misma

estructura (forma)

a

1
2
3

b

5

6

4

8

7

9

c

e
d

f
h

g

i

 Árboles Equivalentes: Son los árboles similares y

sus nodos contienen la misma información.
 Árboles n-ario: Es un árbol ordenado cuyos nodostiene N subárboles, y donde cualquier número de
subárboles puede ser árboles vacíos

10

Tipos de árboles (cont.)
Árbol binario completo:
 Es un árbol en el que todos sus nodos, excepto
los del ultimo nivel, tienen dos hijos.

 Número de nodos en un árbol binario completo
= 2h –1 (en el ejemplo h = 4,  15) esto nos

ayuda a calcular el nivel de árbol necesario
para almacenarlos datos de una aplicación.

11

Árboles Binarios de
Búsqueda (ABB)
Udem OT 2005

12

Árboles Binarios de Búsqueda
 Un árbol es un ABB si

éste es binario y sus
nodos son subárboles
de búsqueda binarios y
contienen información
ordenada de tal que
todos los elementos a
la izquierda de la raíz
son menores a la raíz y
todos lo elementos a la
derecha de la raíz son
mayores ala raíz.
13

Características de un ABB
 Todos los nodos a la izquierda son menores

al padre.
 Todos los nodos a la derecha son mayores al
padre.
 Y solo pueden tener 2 hijos a lo mucho.
50
90

40
26
8

45
34

42

110

85
68

88

100

110
105

95

14

102

Conversión de un árbol general en un
árbol binario
 Los hermanos se enlazan en forma...