Arboles (computación)

Estructura de Datos con Orientación a Objetos

Árboles

6. Árboles 6.1 Introducción. Hasta el momento sólo se han estudiado estructuras lineales estáticas y dinámicas de datos: a un elemento sólo le sigue otro elemento. Al analizar la estructura árbol se introduce el concepto de estructura de ramificación entre nodos. Los árboles representan las estructuras no-lineales y dinámicas de datosmás importantes en computación. Dinámicas, puesto que la estructura árbol puede cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos. En la tabla 6.1 se presentan las estructuras de datos más importantes clasificadas de acuerdo a su estaticidad y dinamismo. Tabla 6.1 Estructuras estáticas y dinámicas ESTRUCTURAS ESTÁTICASARREGLOS REGISTROS CONJUNTOS ESTRUCTURAS DINÁMICAS LISTAS ÁRBOLES

Es de observar que las pilas y colas no fueron consideradas en esta clasificación, puesto que dependen de la estructura que se utilice para implementarlas. En la tabla 6.2 se presentan las estructuras de datos más importantes clasificadas de acuerdo con su linealidad y su nolinealidad: Tabla 6.2 Estructuras lineales y no-linealesESTRUCTURAS LINEALES ARREGLOS REGISTROS CONJUNTOS PILAS COLAS LISTAS 6.2Árboles en general Un árbol es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc. Formalmente se defineun árbol de tipo T como una estructura homogénea que es la concatenación de un elemento de tipo T junto con un número finito de árboles disjuntos, llamados subárboles. Una forma particular de árbol puede ser la estructura vacía. Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente a los mismos. ESTRUCTURAS NO-LINEALESÁRBOLES

A B D I F J K E C H L G

(A (B (D (I), E, F (J, K)), C (G, H (L)))) b)

a)
1.A, 1.1.B, 1.1.1.D, 1.1.1.1.I, 1.1.2.E, 1.1.3.F, 1.1.3.1.J, 1.1.3.2.K, 1.2.C, 1.2.1.G, 1.2.2.H, 1.2.2.1.L c)

1

Estructura de Datos con Orientación a Objetos

Árboles

A B D I E F J C C G H L Figura 6.1 Diferentes formas de representar una estructura de árbol. a) Diagramas de Venn. b) Anidaciónde paréntesis. c) d) e) Notación decimal de Dewey. d) Notación indentada. e) Grafo. Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para registrar la historia de un campeonato de tenis, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerarlos capítulos y secciones de un libro. Gráficamente puede representarse una estructura árbol de diferentes formas y todas ellas equivalentes. En la figura 6.1 se presentan cinco diagramas correspondientes a una estructura árbol. En la figura 6.1a) se representa por medio de Diagramas de Venn; en la figura 6.1b) por medio de anidación de paréntesis; en la figura 6.1c) por medio de la notacióndecimal de Dewey; en la figura 6.1d) por medio de la notación i dentada, y en la figura 6.1e) por medio de grafos. Esta última n representación es la que comúnmente se utiliza; y ha originado el término árbol por su parecido abstracto con el vegetal (raíz, ramas, hojas). Es de notar que en esta representación la raíz se dibuja arriba, aunque en el vegetal se encuentre abajo. 6.2.1 Características ypropiedades de los árboles. Las siguientes son las características y propiedades más importantes de los árboles en general: a) Todo árbol que no es vacío, tiene un único nodo raíz. b) Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. En este caso es común utilizar la expresión X es hijo de Y. c) Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta...