Download Apoyo Tema 1 - Freddy Melgar Algarañaz

ESTRUCTURA DE DATOS II
Ing. Freddy Melgar Algarañaz

Las listas enlazadas son estructuras lineales
◦ Son flexibles pero son secuenciales, un elemento
detrás de otro

Los árboles
◦ Junto con los grafos son estructuras de datos no
lineales
◦ Superan las desventajas de las listas
◦ Sus elementos se pueden recorrer de distintas formas,
no necesariamente uno detrás de otro

Son muy útiles para la búsqueda y
recuperación de información
A es Padre
B y C hijos de A:
hermanos
B es Padre
D, E, F hijos de B

A
Estructura que organiza sus elementos
formando jerarquías: PADRES E HIJOS

Los elementos de un árbol se llaman nodos

Si un nodo B tiene un enlace con un nodo F,

B es el padre y F es el hijo

Los hijos de un mismo padre se llaman: hermanos
B
D

Todos los nodos tienen al menos un padre, menos la raíz: A

Si no tienen hijos o algún sucesor se llaman hoja: D, E, F y C

Un subárbol de un árbol

Es cualquier nodo del árbol junto con todos sus
descendientes
C
E
F
B
D
E
F

Valores:
◦ Conjunto de elementos, donde SOLO se conoce el nodo raíz
◦ Un nodo puede almacenar contenido y estar enlazado con
 Sus árboles hijos (pueden ser dos o varios)

Operaciones: Dependen del tipo de árbol, pero en general
tenemos:
◦
◦
◦
◦
Vaciar o inicializar el Arbol
Eliminar un árbol
Saber si un árbol esta vacío
Recorrer un árbol
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.
5

Mediante diagramas de Venn
a
b
c
d
e
f
a


Mediante círculos y flechas
Mediante paréntesis anidados:
( a ( b (e,f), c, d ) )
b
e
c
d
f
6
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
izquierdo y subárbol derecho.
+
A
^
B
3.5
/
C
D
7
Á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
8



Camino: Secuencia de nodos conectados dentro de un
árbol
Longitud de camino entre 2 nodos: es el numero de
nodos menos 1 en un camino, o también: es el número
de arcos, enlaces o nexos que hay entre ellos.
Altura del árbol: es el nivel mas alto del árbol.
◦ Un árbol con un solo nodo tiene altura 1

Nivel de un árbol
◦ Es el numero de nodos entre la raíz y el nodo mas profundo
del árbol, la altura de un árbol entonces


Grado de un nodo: El número máximo de hijos del nodo
Grado de un árbol: El máximo grado de sus nodos
Árboles
¿Qué es un árbol?

Un árbol es una estructura de datos formada por nodos los
cuales están conectados por aristas.
aristas
A
nodos
B
D
C
E
F
G
H
I
Árboles
Conceptos Básicos
• Un árbol puede estar vacío; es decir no contener ningún nodo.
• Hablaremos entonces del Árbol Vacío.
• Raíz: es el nodo que está al tope del árbol. Un árbol solo tiene una raíz.
Raiz
A
B
D
C
E
F
G
H
I
Árboles
Conceptos Básicos
• Camino: es la secuencia de nodos que hay que visitar para llegar de un
nodo a otro de un árbol.
Ejemplo: B-A-C-F es el camino entre B y F.
A
B
D
C
E
F
G
H
I
Árboles
Conceptos Básicos
• Un conjunto de nodos y aristas se define como un árbol si y solo si existe
un único camino desde la raiz hasta cada uno de sus nodos.
A
B
Esto no es un arbol,
porque existe mas de
un camino desde la
raiz para llegar a
algunos nodos
D
C
E
F
G
H
I
Árboles
Conceptos Básicos
• Padre: En un árbol toda rama va de un nodo n1 a un nodo n2, se dice que
n1 es padre de n2.
Ejemplo: C es padre de E y de F, D es padre de G, de H y de I.
• Hijo: todo nodo puede tener mas de una arista que lo lleva a otro nodo por
debajo de él. Estos nodos que se encuentran por debajo de un nodo dado se
llaman hijos. Ejemplo: E es hijo de C, B es hijo de A, H es hijo de D
A
B
Hijos
Padres
D
C
E
F
G
H
I
Árboles
Conceptos Básicos
• Hojas: son aquellos nodos que no tienen hijos. En un arbol solo puede
haber una raíz pero pueden haber muchas hojas. Ejemplo: B,E,F,G,H,I son
hojas.
• Subárbol: Cualquier nodo se puede considerar como la raíz de un
subárbol.
A
B
Hojas
Subárbol
D
C
E
F
G
H
I
Árboles
Conceptos Básicos
• Visitar: se dice que un nodo es visitado cuando el control del programa se
detiene en él para hacer alguna operación tal como acceder a su data,
imprimir su data, modificar su data. Cuando solamente se pasa por sobre un
nodo no se considera una visita al mismo.
• Recorrer .... Un árbol significa visitar todos sus nodos en un orden
específico.
Ejemplo: B-A-C-E-F-D-G-H-I
A
B
D
C
E
F
G
H
I
Árboles
Conceptos Básicos
• Nivel: el nivel de un nodo es el numero de generaciones que hay desde la
raíz hasta él.
El nivel de la raíz es cero.
• Profundidad o altura = Nivel: es la longitud del camino mas largo desde la
raíz hasta una hoja.
La profundidad de este árbol es 2. La raíz tiene profundidad 0.
A
B
Nivel 0
D Nivel 1
C
E
F
G
H
Nivel
I 2






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 de un 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.
20





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 la longitud
del camino desde la raíz hasta ese nodo.
El nivel puede definirse como 0 para la raíz y
nivel (predecesor)+1 para los demás nodos.
21



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). El número de
las que entran siempre es uno.
Grado de un árbol, es el mayor grado que
puede hallarse en sus nodos.
22
Raíz
hijo
Padre
Hermano
hoja
Subárbol
Nivel de profundidad = 7
Grado de un nodo = 3
Grado del árbol = 3
23
24