trabajo

Fundamentos de Programación II

Tema 4. Estructuras no lineales
de datos: árboles

Luís Rodríguez Baena (luis.rodriguez@upsam.net)
Universidad Pontificia de Salamanca (campus Madrid)
Escuela Superior de Ingeniería y Arquitectura

Estructuras de datos no lineales
En una estructura lineal, cada elemento sólo puede ir
enlazado al siguiente o al anterior.
A las estructuras de datos nolineales se les llama
también estructuras de datos multienlazadas.
● Cada elemento puede estar enlazado a cualquier otro
componentes.

Se trata de estructuras de datos en las que cada
elemento puede tener varios sucesores y/o varios
predecesores.
● Árboles.
● Grafos.

Universidad Pontificia de Salamanca (Campus Madrid)
Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura,2012

2

Estructuras de datos no lineales (II)
Árboles.
● Cada elemento sólo puede estar enlazado con su predecesor y
sus sucesores.
Puede tener varios sucesores.

Grafos.
● Cada elemento puede estar enlazado a cualquier otro.
A
B

A

C

E

D

B
E

I

J

F

G

H

K

Universidad Pontificia de Salamanca (Campus Madrid)
Luis Rodríguez Baena, Escuela Superior deIngeniería y Arquitectura, 2012

D

C

3

Árboles
Estructura no lineal jerárquica en la que cada
elemento tiene un único antecesor y puede tener
varios sucesores.
●

Existe un único camino entre el primer nodo de la
estructura y cualquier otro nodo.

Se utilizan para representar todo tipo de
jerarquías: árbol genealógico, taxonomías,
diagramas de organización, etc.
Eninformática se utilizan para aplicaciones
algorítmicas (ordenación, búsqueda), compilación
(árboles sintácticos, árboles de expresiones), etc.
Formalmente, un árbol A es un conjunto finito de
elementos con 0 o más nodos de forma que:
● Se trata de una estructura vacía.
● Si tiene componentes, los nodos restantes se
dividen en uno o más conjuntos disjuntos cada uno
de los cuales es a su vez unárbol. A estos nodos se
les llama subárboles del raíz.
● Se trata de una estructura recursiva.

Universidad Pontificia de Salamanca (Campus Madrid)
Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

4

Terminología
Nodo: los vértices o elementos de un árbol.
Enlace/arco/arista: Conexión entre dos nodos
consecutivos.
Los nodos pueden ser:
● Nodo raíz: nodo superiorde la jerarquía.
● Nodo terminal u hoja: nodo que no contienen ningún subárbol.
● Nodos interiores: nodos con uno o más subárboles; nodos que no
son hojas.
● Descendientes o hijos: cada uno de los subárboles de un nodo.
● Ascendiente, antecesor o padre: nodo de jerarquía superior a
uno dado.
● Nodos hermanos: nodos del mismo padre.

Bosque: colección de árboles.

Universidad Pontificiade Salamanca (Campus Madrid)
Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

5

Terminología (II)
Camino: enlace entre dos nodos.
● No existe un camino entre todos los
nodos.

Rama: camino que termina en una
hoja.
Grado de un nodo: número de
subárboles que tiene.
Nivel de un nodo o longitud del
camino: número de arcos o enlaces
que hay desde el nodoraíz hasta un
nodo dado.
Altura o profundidad de un árbol:
número máximo de nodos de una
rama; el nivel más alto de un árbol
más uno.
Peso de un árbol: número de nodos
terminales.

Universidad Pontificia de Salamanca (Campus Madrid)
Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

A

B

C

E

I

J

Nivel 0

F

K

D

G

Nivel 1
H

Nivel 2Nivel 3

Altura del árbol = 4
Peso del árbol = 7

6

Árboles binarios
Un árbol general sería un árbol en el que cada nodo puede tener un
número ilimitado de subárboles.
Un árbol binario sería un conjunto de 0 o más nodos en el cual existe
un nodo raíz y cada uno de los nodos, incluido el raíz podrán tener 0, 1
o dos subárboles:
● Subárbol izquierdo y subárbol derecho.
● Cada...