Download Árboles - Beatriz Beltrán Martínez

Árboles
Estructuras de Datos
MC Beatriz Beltrán Martínez
Primavera 2016
Primavera 2016
FCC-BUAP
• Aparecen estructuras de tipo árbol en:
• Sistemas Operativos: Sistema de ficheros (Árbol de
directorios).
• Compiladores, procesadores de textos, algoritmos de
búsqueda.
• Elementos:
• Nodos.
• Conexiones (dirigidas) entre pares de nodos.
• Un nodo particular: Raíz.
• Cada nodo (excepto raíz) está conectado al menos con
otro (padre). Relación padre-hijo.
MC Beatriz Beltrán Martínez
Introducción
99
Primavera 2016
FCC-BUAP
• Un único camino conduce de la raíz a cada nodo.
• Longitud del camino: Número de conexiones a
atravesar.
• Nodos sin hijos: Hojas (leaves).
• Árbol con N nodos  N-1 conexiones entre nodos.
• Profundidad de un nodo:
• Longitud del camino raíz  nodo.
• Altura de un nodo:
• Longitud del camino desde el nodo a su hoja más
profunda.
• Hermanos: Nodos con el mismo padre (siblings).
MC Beatriz Beltrán Martínez
Conceptos
100
Primavera 2016
FCC-BUAP
• El grado de un nodo es el número de flechas que salen
de ese nodo.
• El grado de un árbol es el mayor de los grados que
puede hallarse en el árbol.
• Un camino de un nodo n1 a otro nk, se define como la
secuencia de nodos n1, n2, ... nk tal que ni es padre de ni+1
para 1  i < k.
• Longitud del camino entre 2 nodos, es el número de
arcos que hay entre ellos.
MC Beatriz Beltrán Martínez
Conceptos
101
Primavera 2016
FCC-BUAP
• Relación antepasado (u) / descendiente (v):
• Si hay camino de u a v.
• Tamaño de un nodo:
• Número de descendientes (incluyendo al nodo).
• Árbol (definición recursiva):
• o es vacío,
• o consiste en una raíz y cero o más (sub)árboles no
vacíos A1..Ak conectados a la raíz.
MC Beatriz Beltrán Martínez
Conceptos
102
Primavera 2016
FCC-BUAP
1. Cada nodo contiene:
• Referencias a todos sus hijos.
• Datos almacenados en el nodo.
• Problema: Número de hijos desconocido.
2. Cada nodo:
• Lista con sus hijos.
• Referencia a los datos contenidos.
• Referencia a su nodo hermano.
• Representación "first child / next sibling“.
MC Beatriz Beltrán Martínez
Implementación
103
Primavera 2016
Implementación
null
MC Beatriz Beltrán Martínez
sigHermano
primerHijo
FCC-BUAP
nodoRaiz
null
null
null
null
null
null
null
null
null
104
Primavera 2016
FCC-BUAP
• Ningún nodo puede tener más de N hijos.
• El más utilizado: Binario, 2 hijos (left, right).
• Definición recursiva (Árbol binario):
• ... o es vacío.
• ... o tiene raíz, árbol derecho, árbol izquierdo.
• Implementación:
• Conocido el número de hijos. 2 referencias.
MC Beatriz Beltrán Martínez
Árbol N-ario
105
Primavera 2016
FCC-BUAP
• Árbol binario lleno (full binary tree).
• Todas las hojas tiene la misma profundidad.
• El resto de nodos (no terminales) tienen 2 hijos.
• Árbol binario completo (complete binary tree).
• Cada nivel (excepto el más profundo) debe contener
todos sus posibles nodos.
• En el nivel más profundo, los nodos están lo más a la
izquierda que sea posible.
MC Beatriz Beltrán Martínez
Árboles Binarios
106
Evaluación de la expresión:
Evaluación
de
los
subárboles
(recursivamente).
Aplicación del operador
a los valores obtenidos.
6 + ((7 - 3) * 5)
+
6
*
-
7
Primavera 2016
FCC-BUAP
• Un nodo terminal representa un operando.
• El resto de los nodos representan operadores (binarios).
MC Beatriz Beltrán Martínez
Expresiones
5
3
107
Primavera 2016
FCC-BUAP
• El tipo árbol se define recursivamente.
• Muchas rutinas para manejo de árboles se implementan
fácilmente de forma recursiva.
public class NodoBinario
{
Object dato;
dato
NodoBinario left;
left
right
NodoBinario right;
public NodoBinario (Object elemento)
{
dato = elemento;
left = null; right = null;
}
// Métodos...
}
MC Beatriz Beltrán Martínez
Recursividad
108
Primavera 2016
FCC-BUAP
• Recorrido:
• Acceso a todos los nodos de un árbol
• Ej: Para realizar una operación en cada nodo
• Fácil implementación mediante recursividad.
• Tipos de recorrido:
• Según el orden en que se "visitan" los nodos.
• Recorrido preorder.
• Recorridos postorder.
• Recorridos inorder.
MC Beatriz Beltrán Martínez
Recorridos
109
// en la clase NodoBinario
public void mostrarPreorden()
{
System.out.println(dato);
if (left != null)
left.mostrarPreorden();
if (right != null)
right.mostrarPreorden();
}
Preorden
1
2
3
4
6
5
MC Beatriz Beltrán Martínez
• Recorrido preorden:
1. Nodo raíz
2. Subárbol left en preorden
3. Subárbol right en preorden
FCC-BUAP
Primavera 2016
Recorridos
7
110
Inorden
2
1
// en la clase NodoBinario
public void mostrarInorden()
{
if (left != null)
left.mostrarInorden();
System.out.println(dato);
if (right != null)
right.mostrarInorden();
}
5
3
7
4
MC Beatriz Beltrán Martínez
• Recorrido inorden:
1. Subárbol left en inorden
2. Nodo raíz
3. Subárbol right en inorden
FCC-BUAP
Primavera 2016
Recorridos
6
111
Postorden
7
1
// en la clase NodoBinario
public void mostrarPostorden()
{
if (left != null)
left.mostrarPostorden();
if (right != null)
right.mostrarPostorden();
System.out.println(dato);
}
6
3
5
2
MC Beatriz Beltrán Martínez
• Recorrido postorden:
1. Subárbol left en postorden
2. Subárbol right en postorden
3. Nodo raíz
FCC-BUAP
Primavera 2016
Recorridos
4
112