Arboles binarios
Páginas: 8 (1879 palabras)
Publicado: 3 de marzo de 2011
ÁRBOLES
|INDICE |Pág. |
|2.- Árboles | |
|2.1 Definición de un Árbol |4 ||2.2 Terminología y Características de los Árboles |4 |
|2.3 Árboles de Expansión Mínimos |6 |
|2.4 Árboles Binarios |9 |
|2.5Recorridos de un Árbol |10 |
|2.6 Árboles de Decisión y el tiempo Mínimo para el Ordenamiento |14 |
|2.7 Isomotismo de Árboles |15 |
|Bibliografía|18 |
1. Introducción.
Todo el mundo tiene claro el concepto de árbol, al menos en su aspecto botánico. Sin embargo, los árboles no son sólo eso de lo que estamos rodeados cuando nos perdemos en un bosque, sino que también se usan en otros muchos ámbitos. Así por ejemplo, todos hemosmanejado alguna vez el concepto de árbol genealógico, o hemos visto clasificaciones jerárquicas como las del reino animal. En todos esos casos manejamos el concepto de árbol.
Centrándonos en el mundo de la informática, los árboles se utilizan en distintos ámbitos. Por ejemplo, al organizar la información para facilitar la búsqueda en un disco duro, utilizamos una estructura de directorios ysubdirectorios en forma de árbol. También se usan los árboles asociados a distintos esquemas para el desarrollo de los algoritmos, tales como la programación dinámica, la ramificación y poda, el esquema divide y vencerás, etc.
Si nos referimos a estructuras de datos, las pilas, colas y listas son estructuras lineales, puesto que en todas ellas cada elemento tiene un único elemento anterior y unúnico elemento posterior.
Pero, además, existen estructuras de datos no lineales, en las que esta restricción desaparece. Esto es, en estas estructuras cada elemento puede tener varios anteriores y/o varios posteriores.
Las listas enlazadas son estructuras lineales. Son flexibles pero son secuenciales, un elemento de tras del otro.
Los árboles, junto con los grafos son estructuras de datos nolineales. Estos superan las desventajas de una lista y sus elementos se pueden recorrer de distintas formas, no necesariamente uno de tras de otro y son muy útiles para la búsqueda y recuperación de la información.
2.1 Definición
Un árbol es una estructura de datos no lineal y homogénea en el que cada elemento puede tener varios elementos posteriores, pero tan sólo puede tener unelemento anterior.
2.2 Terminología y Características de los Árboles
De hecho, podemos establecer una clasificación jerárquica de todos los tipos de datos que hemos visto, de modo que unos sean casos particulares de otros. Así, el tipo de estructura más general son los grafos. En un grafo cada elemento puede tener varios elementos anteriores y varios elementos posteriores. Los árboles no son másque un tipo especial de grafo en el que cada elemento puede tener varios posteriores, pero tan sólo puede tener un elemento anterior. Tanto grafos como árboles son estructuras no lineales.
Si añadimos a los árboles la restricción de que cada elemento puede tener un solo posterior, llegamos a las estructuras lineales, y más concretamente a las listas. Así pues, las listas no son más que un...
|INDICE |Pág. |
|2.- Árboles | |
|2.1 Definición de un Árbol |4 ||2.2 Terminología y Características de los Árboles |4 |
|2.3 Árboles de Expansión Mínimos |6 |
|2.4 Árboles Binarios |9 |
|2.5Recorridos de un Árbol |10 |
|2.6 Árboles de Decisión y el tiempo Mínimo para el Ordenamiento |14 |
|2.7 Isomotismo de Árboles |15 |
|Bibliografía|18 |
1. Introducción.
Todo el mundo tiene claro el concepto de árbol, al menos en su aspecto botánico. Sin embargo, los árboles no son sólo eso de lo que estamos rodeados cuando nos perdemos en un bosque, sino que también se usan en otros muchos ámbitos. Así por ejemplo, todos hemosmanejado alguna vez el concepto de árbol genealógico, o hemos visto clasificaciones jerárquicas como las del reino animal. En todos esos casos manejamos el concepto de árbol.
Centrándonos en el mundo de la informática, los árboles se utilizan en distintos ámbitos. Por ejemplo, al organizar la información para facilitar la búsqueda en un disco duro, utilizamos una estructura de directorios ysubdirectorios en forma de árbol. También se usan los árboles asociados a distintos esquemas para el desarrollo de los algoritmos, tales como la programación dinámica, la ramificación y poda, el esquema divide y vencerás, etc.
Si nos referimos a estructuras de datos, las pilas, colas y listas son estructuras lineales, puesto que en todas ellas cada elemento tiene un único elemento anterior y unúnico elemento posterior.
Pero, además, existen estructuras de datos no lineales, en las que esta restricción desaparece. Esto es, en estas estructuras cada elemento puede tener varios anteriores y/o varios posteriores.
Las listas enlazadas son estructuras lineales. Son flexibles pero son secuenciales, un elemento de tras del otro.
Los árboles, junto con los grafos son estructuras de datos nolineales. Estos superan las desventajas de una lista y sus elementos se pueden recorrer de distintas formas, no necesariamente uno de tras de otro y son muy útiles para la búsqueda y recuperación de la información.
2.1 Definición
Un árbol es una estructura de datos no lineal y homogénea en el que cada elemento puede tener varios elementos posteriores, pero tan sólo puede tener unelemento anterior.
2.2 Terminología y Características de los Árboles
De hecho, podemos establecer una clasificación jerárquica de todos los tipos de datos que hemos visto, de modo que unos sean casos particulares de otros. Así, el tipo de estructura más general son los grafos. En un grafo cada elemento puede tener varios elementos anteriores y varios elementos posteriores. Los árboles no son másque un tipo especial de grafo en el que cada elemento puede tener varios posteriores, pero tan sólo puede tener un elemento anterior. Tanto grafos como árboles son estructuras no lineales.
Si añadimos a los árboles la restricción de que cada elemento puede tener un solo posterior, llegamos a las estructuras lineales, y más concretamente a las listas. Así pues, las listas no son más que un...
Leer documento completo
Regístrate para leer el documento completo.