bachiller general

Árboles
Una de las estructuras de datos más importantes en programación es el árbol. Pueden usarse los
árboles para representar la información en una estructura jerárquica. Los árboles pueden
procesarse en forma recursiva y son muy adaptables a pruebas matemáticas. El estudio de
árboles ilustra las conexiones entre varios temas de la matemática discreta y ofrece
oportunidades paraaprovechar la matemática formal en la programación práctica.
La idea de estructura jerárquica es muy usada en la práctica. Por ejemplo, los libros son
a menudo organizados como una sucesión de capítulos cada uno de los cuales son una sucesión
de secciones que puede tener subdivisiones, y así sucesivamente.
Una empresa puede organizarse como las colecciones de unidades comerciales cada uno de lascuales pueden tener varias secciones. Las secciones, a su vez, pueden tener secciones múltiples,
y así sucesivamente.
El software es organizado como una colección de módulos cualquiera que pueden constituirse
de varios su modulos, con el nivel de refinamiento que los diseñadores encuentren apropiado.
En cierto nivel, los módulos se expresan en unidades básicas como los objetos, los métodos, oprocedimientos.
En otros términos, las estructuras jerarquías proporcionan una eficaz la manera de organizar la
información. Los árboles proporcionan una capacidad enorme para expresar la idea de
jerarquía. Ellos son objetos formales, matemáticos.
Definición 1
Un árbol o bien es un árbol vacío o es un nodo junto con una sucesión de árboles.
Sea A un conjunto cualquiera:
1. nil∈ Arbol(A)
2.(cons a a1 a2… an)∈ Arbol(A) si (a∈ A)∧ (a1, a2,… ,an ∈ Arbol(A))
La definición es inductiva. El punto de arranque para la definición inductiva es el árbol vacío.
La definición no dice lo que un árbol vacío es; esto queda como un término indefinido, y la
existencia del árbol vacío se acepta como un axioma. El término “nodo” no se define, y la
existencia de nodos para construir árboles tambiénse toma como un axioma.
Más adelante cuando se usen árboles para representar entidades matemáticas específicas
diremos exactamente qué entidades comprenden el la información que contiene cada nodo que
compone el árbol que se está construyendo.
Definición 2
El primer nodo que se agrega a un árbol no vacío es la raíz del árbol.
Cada miembro individual de la sucesión de árboles en la que sedivide un árbol no vacío se
denomina hijo.
Definición 3.
Un árbol no vacío cuya la sucesión asociada de árboles está vacía se llama hoja.
Una hoja sola es el tipo más simple de árbol no vacío. En este árbol la raíz es una hoja.
En un árbol más complejo, es decir, uno que consiste en un nodo con hijos, la raíz no es una
hoja.
Definición 4.
Se dice que s es un subárbol de t, si s es el propio to si t es no vacío y s es un subárbol de uno de
los hijos de t.
La definición del término subárbol también es inductiva.
Definición 5.
Un árbol s es una hoja de un árbol t si s es un subárbol de t y s es una hoja.

Página 1 de 6

Diagrama de un árbol, representación gráfica

raíz
ramas

nodos

hojas

Definición 6.
Se dice que un nodo n ocurre en un árbol t (o pertenece a t) yse denota n∈t, si t es un árbol que
consiste en un cierto nodo m con una sucesión de hijos (a1, a2, …..,an) y n o bien es m, o bien n
pertenece a uno de los hijos de m.
Ningún nodo pertenece al árbol vacío, por definición.
Definición 7.
Se dice que un nodo n es un nodo interior al árbol t si n pertenece a t y existe una sucesión de
árboles (a1, a2, …..,an) tal que n junto con esa sucesión esun subárbol de t.
Los árboles normalmente contienen datos adicionales en sus nodos y hojas.
La estructura del árbol (comprendiendo los nodos y hojas) proporciona un organización para
los valores de los datos, haciendo que la información sea más fácil de usar que si simplemente
estuviera contenida en una lista.
Se considera el árbol que representa la expresión aritmética (3. 4) + ((5. 6)/8)....