Bayo

DEBER DE ESTRUCTURA DE DATOS
BYRON CHICAIZA
TERCERO SISTEMAS

¿QUE ES RECURSIVIDAD?

Primero debemos decir que la recursividad no es una estructura de datos, sino
que es una técnica de programación que nos permite que un bloque de
instrucciones se ejecute n veces. Remplaza en ocasiones a estructuras repetitivas.
Este concepto será de gran utilidad para el capítulo de la estructura dedatos tipo
árbol.
En Java los métodos pueden llamarse a sí mismos. Si dentro de un método existe
la llamada a sí mismo decimos que el método es recursivo.
ARBOLES RECURSIVOS
Este tipo de organización se utiliza mucho para representar información ordenada, para mostrar relaciones
estructurales entre elementos de un conjunto y, en general, para modelar situaciones que se puedan e xpresar
entérminos de jerarquías. Se estudian en particular los árboles ordenados, los árboles balanceados y los
árboles de sintaxis.
Un árbol binario es una estructura recursiva, compuesta por un elemento, denominado la raíz, y por dos
árboles binarios asociados, denominados subárbol derecho y subárbol izquierdo. El hecho de definir la
estructura de datos en términos de sí misma es lo que hace que sedenomine recursiva. El formalismo gráfico
escogido para representar un árbol aparece en la figura 4.1. En él, se hace explícito que los dos subárboles
tienen la misma composición estructural del árbol completo. El caso más sencillo de árbol binario es un
árbol vacío, el cual no tiene elementos ni subárboles asociados. El símbolo escogido para representarlo es .

Otro formalismo posible pararepresentar árboles binarios, cuando se quieren hacer explícitos todos los
componentes de la estructura, utiliza un nombre para cada uno de los elementos del árbol y líneas para las
relaciones de composición, como se muestra en la figura

Un elemento e2 es hijo de un elemento e1, si e2 es la raíz de uno de los subárboles asociados con e1. En
ese mismo caso, se dice que e1 es el padre de e2. Unelemento e2 es hermano de un elemento e3 si ambos
tienen el mismo padre.

Un elemento de un árbol binario es una hoja si sus dos subárboles asociados son vacíos. En la figura 4.2, los
elementos e4, e5, e6 y e7 son hojas. El formalismo gráfico para expresar que un árbol está compuesto
solamente por una hoja aparece en la figura Todo elemento de un árbol que no es una hoja se denomina un
elementono terminal o interior.

Para el árbol de la siguiente figura:

Se tiene que:
La raíz es 20 y los dos subárboles asociados son:

Los elementos 5, 12 y 25 son hojas
Los nodos interiores son 20 y 10.
El padre de 5 es 10. El padre de 25 es 20. Los hijos de 10 son 5 y 12.
Los elementos 5 y 12 son hermanos.
Un camino entre dos elementos e1 y e2 de un árbol binario es una secuencia , quecumple
que el primer elemento es e1, el último es e2, y cada elemento es padre de su sucesor. No siempre existe un
camino entre dos elementos de un árbol, pero si existe, éste es único. La raíz de un árbol se caracteriza
porque tiene un camino a cualquier elemento del árbol. La longitud de un camino es n-1, o
sea, el número de veces que se debe aplicar la relación padrehijo durante el recorrido.Siempre existe un
camino de longitud 0 que lleva de un elemento r a sí mismo y corresponde a la secuencia < r >. Por último, se
tiene que un camino que parte de la raíz y termina en una hoja se conoce como una rama.
Ejemplo 4.2

Para el árbol que se muestra en la siguiente figura:

Se cumple que:

La longitud del camino < a, b, e > es 2. La longitud del camino < a > es 0.
No existe uncamino entre d y c.
El único camino que lleva de c a h es < c, f, h >.
El camino < a, c, f, g > es una rama.
Desde la raíz existe un camino que lleva hasta cualquier otro elemento de la estructura.
Un elemento e1 es ancestro de un elemento e2, si existe un camino entre e1 y e2. En ese mismo caso, se
dice que e2 es descendiente de e1. El nivel de un elemento dentro de un árbol binario se...