Arboles C++

EDA 04/05

Tema 7. Árboles

Tema 7.

Árboles

INTRODUCCIÓN ............................................................................................................................................1 DEFINICIONES ...........................................................................................................................................1 RECORRIDOS EN UN ÁRBOL.......................................................................................................................4 ÁRBOLES BINARIOS .....................................................................................................................................5 ESPECIFICACIÓN ALGEBRAICA..................................................................................................................5 INTERFAZ DE UNA CLASE ÁRBOL BINARIO ................................................................................................6 EJEMPLO: CÁLCULO DE LA PROFUNDIDAD .................................................................................................6 EJEMPLOS DE RECORRIDOS........................................................................................................................7 POSIBLES IMPLEMENTACIONES ..................................................................................................................9 EJEMPLO DE IMPLEMENTACIÓN DINÁMICA ..............................................................................................11 ÁRBOLES BINARIOS ORDENADOS.............................................................................................................13 ESPECIFICACIÓN ALGEBRAICA ................................................................................................................14 INTERFAZ DE UNA CLASE ÁRBOL BINARIO ORDENADO ...........................................................................16 EJEMPLO: FUNCIÓN DE PERTENENCIA A UN ABO....................................................................................16 EJEMPLO DE IMPLEMENTACIÓN DINÁMICA ..............................................................................................17 ÁRBOLES AVL ............................................................................................................................................20 ÁRBOLESGENERALES...............................................................................................................................23 ESPECIFICACIÓN ALGEBRAICA ................................................................................................................23 REPRESENTACIÓN DE ÁRBOLES GENERALES MEDIANTE ÁRBOLES BINARIOS ...........................................24 PROBLEMAS RESUELTOS..........................................................................................................................27 PROBLEMAS ...............................................................................................................................................29

Bibliografía :
• • • • Y. Langsam, M.J. Augenstein, A.M. Tenenbaum: Estructuras de datos con C y C++. Ed. Prentice Hall, 1997. E. Horowitz, S. Sahni: Fundamentals of data structures in C++.Ed. Computer Science Press, 1997. N. Dale: C++ plus data structures. Ed. Jones and Bartlett, 1999. R. Hernández, J.C. Lázaro, R. Dormido, S. Ros. Estructuras de datos y algoritmos. Ed. Prentice-Hall, 2.000.

Página 0

EDA 04/05

Tema 7. Árboles

Tema 7.

Árboles

Introducción
Un árbol es una estructura de datos no lineal que establece una jerarquía entre sus elementos. Ejemplo: Unaexpresión aritmética se puede representar con un árbol. Utilización: para representar taxonomías, jerarquías, índices en ficheros y bases de datos, espacios de decisión en problemas, en la construcción de compiladores, etc.
Definiciones

Un árbol A es una estructura de datos no lineal, homogénea, que establece una jerarquía entre sus elementos. Nodo: elemento de un árbol. Definición recursiva de...