Download Arboles (Trees)

Algoritmos y Estructura
de Datos
Tema : Arboles
Grupo 4
1
Arboles (Trees)
• Arboles
• Arboles binarios
• Recorridos de árboles
• Patrón método template
• Estructuras de datos para
árboles
2
Arboles
• un árbol representa una jeraquía
ejemplos:
estructura organizativa de una empresa
tabla de contenido de un libro
3
Arboles (1)
•` Sistema de ficheros de Unix o DOS/Windows
4
Arboles (2)
•Representación:
Conjuntos anidados
Paréntesis anidados
Indentación
Grafo
Representación más usual: grafo
5
Terminología de Arboles
• A es el nodo raíz
• B es el padre de D y E
• C es el primo de B
• D y E son los hijos de B
• D, E, F, G, I son nodos externos o
hojas
• A, B, C, H son nodos internos
• La profundidad (nivel) de E es 2
• La altura del árbol es 3
• El grado del nodo B es 2
• Propiedad: (#aristas) = (#nodos) - 1
6
Arboles binarios
• Arbol ordenado: el hijo de cada nodo está ordenado
• Arbol binario: árbol ordenado con todos los nodos internos de
grado 2
• Definición recursiva de árbol binario:
• Un árbol binario es:
- un nodo externo (hoja) o
- un nodo interno (la raíz) y dos árboles binarios (subárbol
izquierdo y subárbol derecho)
7
Ejemplos de Arboles Binarios
• expresión aritmética
• río especial
8
Ejemplos de Arboles Binarios
• Árboles de
decisión
9
Propiedades de Arboles Binarios
• (# nodos externos) = (# nodos internos) + 1
• (# nodos nivel i)  2 i
• (# nodos externos)  2 altura
• (altura)  log2 (# nodos externos)
• (altura)  log2 (# nodos) - 1
• (altura)  (# nodos internos) - ((# nodos) - 1)/2
10
TDAs para Arboles
•
Métodos contenedor genéricos
-size(), isEmpty(), elements()
•
Métodos contenedor posicionales
-positions(), swapElements(p,q), replaceElement(p,e)
•
Métodos consulta
-isRoot(p), isInternal(p), isExternal(p)
•
Métodos acceso
-root(), parent(p), children(p)
•
Métodos actualización
-específico de la
aplicación
11
TDAs para Arboles Binarios
• Métodos acceso
-leftChild(p), rightChild(p), sibling(p)
• métodos actualización
-expandExternal(p), removeAboveExternal(p)
-otros métodos específicos de la aplicación
12
Recorrido de árboles (1)
• recorrido preorder
Algoritmo preOrder(v)
“visitar” nodo v
for each hijo w de v do
realizar recursivamente preOrder(w)
• Ejm: lectura de un documento desde el inicio hasta el final
13
Recorrido de árboles (2)
• recorrido postorder
Algoritmo postOrder(v)
for each hijo w de v do
realizar recursivamente postOrder(w)
“visitar” nodo v
• comando du (disk usage) de Unix
14
Evaluación de Expresiones Aritméticas
• especialización de recorrido postorder
Algoritmo evaluateExpression(v)
if v es un nodo externo
return la variable almacenada en v
else
asignar a o el operador almacenado en v
x  evaluateExpression(leftChild(v))
y  evaluateExpression(rightChild(v))
return x o y
15
Recorrido de árboles (3)
• recorrido inorder de un árbol binario
Algoritmo inOrder(v)
realizar recursivamente inOrder(leftChild(v))
“visitar” nodo v
realizar recursivamente inOrder(rightChild(v))
• impresión de una expresión aritmética
especialización de un recorrido inorder
print “(“ antes de recorrer el subárbol izquierdo
print “)” antes de recorrer el subárbol derecho
16
Recorrido de árboles (4)
1
3
2
4
8
5
9
6
7
10
Inorden: 8 4 9 2 10 5 1 6 3 7
Preorden: 1 2 4 8 9 5 10 3 6 7
Postorden: 8 9 4 10 5 2 6 7 3 1
17
Recorrido de Euler en Arboles
Binarios
• Recorrido genérico de un árbol binario
• los recorridos preorder, inorder, y postorder son casos
especiales del recorrido de Euler
• “caminar alrededor” del árbol y visitar cada nodo tres veces:
• a la izquierda
• desde abajo
• a la derecha
18
Patrón método Template
• Mecanismo de cómputo genérico que puede ser
especializado redefiniendo ciertos pasos.
• implementado por medio de una clase abstracta de Java con
métodos que pueder ser redifinidos por sus subclases
19
Especializando el Recorrido
Genérico para Arbol Binario
• Imprimiendo una expresión aritmética
public class PrintExpressionTraversal extends BinaryTreeTraversal {
...
protected void external(Position p, TraversalResult r) {
System.out.print(p.element());
}
protected void left(Position p, TraversalResult r) {
System.out.print("(");
}
protected void below(Position p, TraversalResult r) {
System.out.print(p.element());
}
protected void right(Position p, TraversalResult r) {
System.out.print(")");
}
20
Estructura de Datos para Arboles Binarios
mediante nodos enlazados
21
Representación de Arboles
Generales
árbol T
Arbol binario T' representa T
22