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 vfor 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 velse
asignar a o el operador almacenado en vx 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éticaespecialización de un recorrido inorderprint “(“ antes de recorrer el subárbol izquierdoprint “)” antes de recorrer el subárbol derecho
16
Recorrido de árboles (4)
Inorden: 8 4 9 2 10 5 1 6 3 7Preorden: 1 2 4 8 9 5 10 3 6 7Postorden: 8 9 4 10 5 2 6 7 3 1
1
2 3
4 5 6 7
8 9 10
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