Ciencia y tecnologia

Solo disponible en BuenasTareas
  • Páginas : 35 (8501 palabras )
  • Descarga(s) : 0
  • Publicado : 18 de noviembre de 2010
Leer documento completo
Vista previa del texto
Arboles Binarios Objetivo: Dar una introducción a los árboles y mostrar la forma de implementar un árbol binario, ya sea en una estructura estática (un vector) o dinámicamente (semejante a una lista ligada). Descripción: A lo largo de la siguiente práctica se mostrarán algunos conceptos útiles para comprender que es y para que pudiera servir un árbol, además de que se mostrarán dos pequeñosejemplos que muestran algunos ejemplos de utilidad para árboles binarios. Nota:
El presente documento es una pequeña síntesis sobre árboles binarios. Se trata este tema porque estos representan una de las estructuras de datos más importantes en computación y estos pueden aplicarse para la solución de una gran variedad de problemas, pero no muchas personas los ven como una buena solución puesto que losconsideran un tanto complejos. El objetivo del presente será dejar claro que es un árbol binario y crear algunos ejemplos para tratar de tener una mayor comprensión. Y así después cada uno de nosotros podamos definir si es conveniente aplicarlos a la solución de algún problema o si alguna otra estructura de datos puede ser una mejor opción. Puesto que solo veremos árboles las estructuras de datosalternativas corren por su cuenta :-)

Desarrollo:

Conceptos y Terminología básica
Si vamos a trabajar con árboles, lo primero que tenemos que ver es que es un árbol. Aquí tenemos algunas definiciones para árbol: - 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 un elemento anterior. - Esuna estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; de los cuales uno 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. - Un árbol es una estructura compuesta por un dato y varios árboles. Dado un nodo cualquiera de la estructura, podemosconsiderarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo. - Son estructuras dinámicas no lineales. 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. En las estructuras de datos lineales cada elementotiene un único elemento anterior y un único elemento posterior. 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ás que un tipo especial de grafo en el que cada elemento puede tener varios elementos posteriores, pero tan sólo puede tener un elemento anterior. Tanto grafos comoárboles son estructuras no lineales. Creo que la mayoría, sino es que todos, hemos utilizado los árboles cuando hemos hecho un árbol genealógico o alguna estructura jerárquica de alguna organización. Y que me dicen de la forma en la que organizamos la información en nuestras maquinas (se hace en una estructura de directorios y subdirectorios en forma de árbol, para facilitar su búsqueda). Talvez sindarnos cuenta, pero hemos manejado el concepto de árbol .

Además de la definición debemos conocer otros conceptos bastante importantes, pues estos pudieran ser útiles a la hora de codificar un árbol: En relación con otros nodos:  Nodo padre. Nodo que contiene un puntero al nodo actual. En un árbol un nodo solo puede tener un nodo padre. X es padre de Y sí y solo sí el nodo X apunta a Y.También se dice que X es antecesor de Y. En la Figura 1: B es padre de E y F.  Nodo hijo. Cualquiera de los nodos apuntados por uno de los nodos del árbol. Un nodo puede tener varios hijos. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y. En la Figura 1: E es hijo de B.  Hermano. Dos nodos serán hermanos si son descendientes directos de...
tracking img