Arboles

UNIDAD V

Árboles
1

Definiciones
El árbol es una estructura fundamental en la computación. Casi
todos los sistemas operativos almacenan los ficheros en árboles o en
estructuras de aspectos arbóreo.
Es una estructura que organiza sus elementos, denominados nodos,
formando jerarquías. 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.
2

Dentro de la ciencia de la computación, los árboles tienen muchas
aplicaciones como por ejemplo:
 Organizar tablas de símbolos en compiladores.
 Representar tablas de decisión.
 Asignar bloques de memoria de tamaño variable.
Ficheros de sistemas operativos (estructuras de aspectos arbóreo). ∙
 Método de ordenación.
 Método de búsqueda.
 Solucionar juegos.
 Probar teoremas.
 Procesamiento de textos.
3

Representación de un Árbol.
 Mediante diagramas de Venn
a
b

c

d

e
f

 Mediante círculos y flechas (grafos)

a

b

c

 Mediante paréntesis anidados:

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

f

d

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






5

y que B es sucesor de A. Todos los caminos de un árbol deben de
ser de arriba hacia abajo.
Padre es el antecesor inmediato de un nodo
Hijo, cualquiera de sus descendientes inmediatos.
Descendiente de un nodo, es cualquier sucesor de dicho nodo.
Hermano de un nodo, es otronodo que desciende del mismo
padre.

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 nodos interiores.
 Rama es cualquier camino del árbol.
 Bosque es un conjunto de árboles desconectados.
 Nivel o profundidad de un nodo, es lalongitud del camino desde
la raíz hasta ese nodo.
El nivel puede decirse como 0 para la raíz y nivel (predecesor)+1
para los demás nodos.

6

Conceptos Básicos (cont.)
 Los nodos de la misma generación tienen el mismo nivel.
 Grado de un nodo, es el número de flechas que salen de ese

nodo (hijos).
 Grado de un árbol, es el mayor grado que puede hallarse en
sus nodos.
 Longitud delcamino entre 2 nodos: es el número de arcos
que hay entre ellos.
 Nodo no terminal es aquel que posee por lo menos un
descendiente.

7

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

Hermano

hoja
8

Subárbol

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

Tipos de árboles
Arbol ordenado: Se define como un árbol en el que los
subárboles de cada nodoforman un conjunto ordenado.
 Cada árbol binario tiene un subárbol izquierda y subárbol
derecha.
A

B

D

C

E

H

9

G

F

I

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

*

+

+

*
A

+
B

(A* B) + C * D + E

10

E

*
C

-

D

7

12

9

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

Tipos de árboles (cont.)
 Árbolessimilares: Los que tienen la misma estructura (forma) sin

importar el contenido del arbol.

a
1

2
3

b

5

c

6

4

e
d

7

h
8

g

|f

i

9

 Árboles Equivalentes: Son los árboles que tienen la misma estructura

y sus nodos contienen la misma información.

 Árboles n-ario: Es un árbol ordenado cuyos nodos tiene N subárboles,

y donde cualquier número desubárboles puede ser árboles vacíos

11

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 almacenar los datos de una aplicación.

12

Árbol binario....