Arboles

4.1 Introducción

Los arboles 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 arboles pueden ser construidos con estructuras estáticas y dinámicas. Las estáticas sonarreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas.
La definición de árbol es la siguiente: 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,ansestro, etc.. Formalmente se define un á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 arboles disjuntos, llamados subarboles. Una forma particular de árbol puede ser la estructura vacía.
La figura siguiente representa a un árbol general.

Se utiliza la recursión para definir un árbol porque representa la forma másapropiada y porque además es una característica inherente de los mismos.
Los arboles 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 los capítulos y secciones de un libro.

4.2 Terminología

Laterminología que por lo regular se utiliza para el manejo de arboles es la siguiente:
* HIJO. 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.
* 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.
* HERMANO. Dos nodos serán hermanos si son descendientes directos de un mismonodo.
* HOJA. Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).
* NODO INTERIOR. Es un nodo que no es raíz ni terminal.
* GRADO. Es el número de descendientes directos de un determinado nodo.
* GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol.
* NIVEL. Es el número de arcos que deben ser recorridos para llegar a un determinadonodo. Por definición la raíz tiene nivel 1.
* ALTURA. Es el máximo número de niveles de todos los nodos del árbol.
* PESO. Es el número de nodos del árbol sin contar la raíz.
* LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y asísucesivamente.

ARBOLES BINARIOS
videos
http://www.youtube.com/watch?v=_RzoDzSxcak&feature=related
http://www.youtube.com/watch?v=E_3haW_CWr8
http://www.youtube.com/watch?v=Vb9gjz636yI&feature=fvw (recorridos)
http://www.youtube.com/watch?v=Rr1t8UX_d10&feature=related (árbol binario de búsq. Parte 1
http://www.youtube.com/watch?v=tzEi3n2r2CM&feature=related (árbolbinario de busq. Parte 2
http://www.youtube.com/watch?v=AWxb_x1fMnc&feature=related (arboles balanceados)
http://www.youtube.com/watch?v=a85qM2ugf74&feature=related Ejemplo a. balanceado eliminación

5.1 Introducción

A los arboles ordenados de grado dos se les conoce como arboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de losarboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.
La representación gráfica de un árbol binario es la siguiente:

5.2 Representación en Memoria

Hay dos formas tradicionales de representar un árbol binario en memoria:
* Por medio de datos tipo punteros también conocidos...