Arboles Binarios
Esta
estructura se usa principalmente para representar datos con una relación
jerárquica entre sus elementos, como por ejemplo registros, árboles
genealógicos, y tablas de contenidos. Veremos los recorridos que se pueden
hacer en los árboles binarios, también se va a ampliar sobre árboles en los
lenguajes de programación funcional. Introducción
* Recorrido en amplitud. * Es aquel recorrido que recorre el árbol por niveles del
nivel superior a los niveles inferiores, en el ejemplo sería: Recorridos de árbol
binario
*
Recorrido en profundidad. * Existen 3: Preorden,
Postorden, Inorden. Recorridos
*
Recorrer un árbol en preorden consiste en primer lugar, examinar el dato del
nodo raíz, posteriormente se recorre el subárbol izquierdo en preorden y
finalmente se recorre el subárbol derecho en preorden. Recorrido Preorden
* Recorrer un árbol en Postorden consiste en primer lugar
en recorrer el subárbol izquierdo en Postorden, luego se recorre el subárbol
derecho en Postorden y finalmente se visita el nodo raíz. Recorrido
Postorden
* Recorrer un árbol en Inorden consiste en primer lugar en
recorrer el subárbol izquierdo en Inorden, luego se examina el dato del nodo
raíz, y finalmente se recorre el subárbol derecho en Inorden. Recorrido
Inorden
*
Los ordenamientos más importantes son llamados: pre-orden, post-orden e
Inorden. Si un árbol T es nulo, entonces, la lista vacía es el listado:
pre-orden, post- orden e Inorden del árbol T. Si T consiste de un solo nodo n,
entonces, n es el listado: pre-orden, post- orden e Inorden del árbol T.
Recorridos en Lenguajes de Programación funcional
*
Los algoritmos de recorrido de un árbol binario presentan tres tipos de
actividades comunes: *. Visitar el nodo raíz *. Recorrer el subárbol izquierdo *. Recorrer el subárbol derecho Recorridos en Lenguajes de
Programación funcional
· Recorrido Inorden.
· Recorrido Postorden.
Arboles
generales
Un
árbol es una estructura no lineal a cíclica utilizada para organizar
información de forma eficiente.
La
definición es recursiva:
Un
´árbol es una colección de valores {v1, v2,. . . vn} tales que ¦
*
Si n = 0 el ´árbol se dice vacío. ¦ En otro caso, existe un valor destacado que
se denomina raíz (p.e. v1), y los demás elementos forman parte de colecciones
disjuntas que a su vez son ´arboles. Estos ´árboles se llaman subárboles de la
raíz.
Las
estructuras tipo ´árbol se usan principalmente para representar datos con una
relación jerárquica entre sus elementos, como ´arboles genealógicos, tablas,
etc. X
La
terminología de los ´árboles se realiza con las típicas notaciones de las
relaciones familiares en los ´arboles genealógicos: padre, hijo, hermano,
ascendente, descendente, etc.
Algunas
definiciones
Nodo,
son los elementos del ´árbol.
Raíz
del ´árbol: todos los ´árboles que no están vacíos tienen un ´único nodo raíz.
Todos los demás elementos o nodos se derivan o descienden de ´el.
Nodo
hoja es aquel nodo que no contiene ningún subárbol.
Tamaño
de un ´árbol es su número de nodos.
A
cada nodo que no es hoja se le asocia uno o varios subárboles llamados
descendientes o hijos. X De igual forma, cada nodo tiene asociado un antecesor
o ascendiente llamado padre.
Todos
los nodos tienen un solo padre excepto la raíz que no tiene padre.
Cada
nodo tiene asociado un número de nivel que se determina por la longitud del
camino desde la raíz al nodo específico.
La
altura o profundidad de un ´árbol es el nivel más profundo más uno.
