Unidad iv arboles y grafos
Páginas: 6 (1370 palabras)
Publicado: 6 de noviembre de 2011
UNIDAD IV
ESTRUCTURAS NO LINEALES
4.1. ÁRBOLES
Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.
Los árboles pueden ser construidos con estructurasestáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas.
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 construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar loscapítulos y secciones de un libro, representaciones de estadísticas, etc.
Ejemplo de un Diagrama de Árbol en Probabilidad
4.1.1 Concepto de Árbol
En ciencias de la Informática, un Árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijosconectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.
Otra definición de ÁRBOL sería:
Conjunto de Nodos que cumplencon las relaciones Padre, Hijo y Hermano. Llamamos Hijos de un Nodo a todos los nodos que podemos llegar directamente por medio de un apuntador hacia ellos y descendencia a todos los que pudiéramos llegar a través de los Hijos y su propia Descendencia.
Llamamos Padre al Nodo del cual proviene el Nodo hijo. Existe un Nodo que no tiene padre y le llamamos Raíz del Árbol.
4.1.1.2. REPRESENTACIÓN ENMEMORIA DE ÁRBOLES
Hay dos formas tradicionales de representar un árbol binario en memoria:
Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.
Por medio de arreglos.
Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará lainformación del nodo. Los dos restantes se utilizarán para apuntar al subárbol izquierdo y derecho del subárbol en cuestión. Cada nodo se representa gráficamente de la siguiente manera:
Los árboles binarios también pueden ser almacenados como una estructura de datos implícita en vectores, y si el árbol es un árbol binario completo, este método no desaprovecha el espacio en memoria. Tomaremos comonotación la siguiente:
Si un nodo tiene un índice i, sus hijos se encuentran en índices 2i + 1 y 2i + 2, mientras que sus padres (si los tiene) se encuentra en el índice (partiendo de que la raíz tenga índice cero). Este método tiene como ventajas el tener almacenados los datos de forma más compacta y por tener una forma más rápida y eficiente de localizar los datos en particular durante unPreorden transversal. Sin embargo, desperdicia mucho espacio en memoria.
4.1.2. CLASIFICACIÓN DE ÁRBOLES
4.1.2.1 ÁRBOLES GENERALES
En un árbol general cada nodo puede poseer un número indeterminado de hijos. La implementación de los nodos en este caso se realiza de la siguiente manera: como no se sabe de antemano cuantos hijos tiene un nodo en particular se utilizan dos referencias, una asu primer hijo y otra a su hermano más cercano. La raíz del árbol necesariamente tiene la referencia a su hermano como null.
Nótese que todo árbol general puede representarse como un árbol binario, con la salvedad que el hijo derecho de la raíz es siempre null. Si se permite que la raíz del árbol tenga hermanos, lo que se conoce como bosque, entonces se tiene que el conjunto de los bosques...
ESTRUCTURAS NO LINEALES
4.1. ÁRBOLES
Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.
Los árboles pueden ser construidos con estructurasestáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas.
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 construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar loscapítulos y secciones de un libro, representaciones de estadísticas, etc.
Ejemplo de un Diagrama de Árbol en Probabilidad
4.1.1 Concepto de Árbol
En ciencias de la Informática, un Árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijosconectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.
Otra definición de ÁRBOL sería:
Conjunto de Nodos que cumplencon las relaciones Padre, Hijo y Hermano. Llamamos Hijos de un Nodo a todos los nodos que podemos llegar directamente por medio de un apuntador hacia ellos y descendencia a todos los que pudiéramos llegar a través de los Hijos y su propia Descendencia.
Llamamos Padre al Nodo del cual proviene el Nodo hijo. Existe un Nodo que no tiene padre y le llamamos Raíz del Árbol.
4.1.1.2. REPRESENTACIÓN ENMEMORIA DE ÁRBOLES
Hay dos formas tradicionales de representar un árbol binario en memoria:
Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.
Por medio de arreglos.
Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará lainformación del nodo. Los dos restantes se utilizarán para apuntar al subárbol izquierdo y derecho del subárbol en cuestión. Cada nodo se representa gráficamente de la siguiente manera:
Los árboles binarios también pueden ser almacenados como una estructura de datos implícita en vectores, y si el árbol es un árbol binario completo, este método no desaprovecha el espacio en memoria. Tomaremos comonotación la siguiente:
Si un nodo tiene un índice i, sus hijos se encuentran en índices 2i + 1 y 2i + 2, mientras que sus padres (si los tiene) se encuentra en el índice (partiendo de que la raíz tenga índice cero). Este método tiene como ventajas el tener almacenados los datos de forma más compacta y por tener una forma más rápida y eficiente de localizar los datos en particular durante unPreorden transversal. Sin embargo, desperdicia mucho espacio en memoria.
4.1.2. CLASIFICACIÓN DE ÁRBOLES
4.1.2.1 ÁRBOLES GENERALES
En un árbol general cada nodo puede poseer un número indeterminado de hijos. La implementación de los nodos en este caso se realiza de la siguiente manera: como no se sabe de antemano cuantos hijos tiene un nodo en particular se utilizan dos referencias, una asu primer hijo y otra a su hermano más cercano. La raíz del árbol necesariamente tiene la referencia a su hermano como null.
Nótese que todo árbol general puede representarse como un árbol binario, con la salvedad que el hijo derecho de la raíz es siempre null. Si se permite que la raíz del árbol tenga hermanos, lo que se conoce como bosque, entonces se tiene que el conjunto de los bosques...
Leer documento completo
Regístrate para leer el documento completo.