Chapalapachala

INACAP Sede Temuco Estructura de Datos Analista Programador

Estructura de datos Árbol

Nombre Alumno: Juan P. Cayul Asignatura: Estructura de Datos Profesor: Luis Miranda Segovia Fecha: 18 dic 2012

Introducción

El árbol es una estructura de datos muy importante en informática y en ciencias de la computación, se trata de estructuras no lineales a diferencia de las que vimosanteriormente, las listas, que se consideran lineales. Los árboles se utilizan para representar fórmulas algebraicas, organizar objetos en orden de tal forma que las búsquedas sean muy eficientes y en aplicaciones diversas como inteligencia artificial o algoritmos de cifrado. Casi todos los sistemas operativos almacenan sus archivos en árboles o estructuras similares a árboles. También se utilizan en eldiseño de compiladores, procesamiento de texto y algoritmos de búsqueda. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

Árboles generales
De manera intuitiva, el concepto de árbol implica una estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre sí a través de ramas. Unárbol consta de un conjunto finito de elementos, llamados nodos y de un conjunto finito de líneas dirigidas, llamadas ramas que conectan los nodos. Un árbol es un conjunto de uno o más nodos tales que: hay un nodo especial llamado raíz y los restantes se dividen en n ≥ 0 conjuntos disjuntos tal que cada uno de estos conjuntos es un árbol y se los conoce como subárboles.

Terminología
1. Nodo:También llamado vértice o elemento del árbol. Es el contenedor de los datos y los enlaces a sus hijos y a su padre. 2. Nodo Raíz: Es el nodo donde comienza el árbol. Cada árbol tiene solamente un nodo raíz, desde el cual cuelgan todos sus descendientes. 3. Nodo Rama: También llamado nodo interior o interno. Es un nodo cualquiera que puede tener hijos, aunque en este preciso momento no los tenga. Es todonodo que no es raíz o hoja. 4. Nodo Hoja: También llamado nodo terminal. Es un nodo cualquiera que no puede tener hijos y nunca los podrá tener. Es un nodo que no tiene ningún subárbol. 5. Nodo Hermano: Es un nodo que es hijo del mismo padre. 6. Camino: Son los enlaces que van desde un nodo hasta otro nodo. 7. Rama: Es un camino que termina en una hoja. 8. Nivel del Nodo: Es la longitud delcamino desde el nodo raíz al nodo específico mas uno. 9. Altura del Arbol: También llamado profundidad. Es el número máximo de nodos de una rama del árbol. Es igual al nivel más alto de los nodos del árbol. 10. Peso del Arbol: Es el número de nodos terminales 11. Arbol Vacío: Es un árbol que en este momento no tiene ningún nodo. De existir solo un nodo, ese nodo es el nodo raíz. 12. Grado de un Nodo:Es el número de subárboles que tiene un nodo. Los nodos hoja tienen grado cero. 13. Grado de un Arbol: El grado máximo de todos los nodos del árbol. 14. Ancestros del Nodo: Son todos los nodos del árbol en el camino que va desde el raíz hasta el nodo específico.

Representación
Las formas más frecuentes de representar un árbol en papel son como árbol invertido y como una lista.Representación como árbol invertido El nodo raíz se encuentra en la parte más alta de una jerarquía, de la que descienden ramas que van a parar a los nodos hijos, y así sucesivamente.

Representación de lista Otro formato utilizado para representar un árbol es la lista entre paréntesis. Esta notación se utiliza con expresiones algebraicas. En esta representación, cada paréntesis abierto indica el comienzo deun nuevo nivel y cada paréntesis cerrado completa un nivel y se mueve hacia arriba un nivel en el árbol.

A (B (E), C (F), D (G, H))

Declaraciones de tipos para manejar árboles en C #define ORDEN 5 struct nodo \{ int dato; struct nodo *rama[ORDEN]; };

Para C, y basándonos en la declaración de nodo que hemos visto más arriba, trabajaremos con los siguientes tipos:

typedef struct...