Funciones para la Manipulación de Árboles y Bosques

1. Función lista_hojas

La función lista_hojas toma un árbol como entrada y devuelve una lista con todas las letras que se encuentran en las hojas del árbol, tomadas de izquierda a derecha.

func lista_hojas(a:árbol) dev l:lista

l <- raíz(a) == "" ? <> : <raíz(a)>

finfunc

func lista_hojas_b(b:bosque) dev l:lista

si vacio(b) entonces

l <- <>

si no

l <- lista_hojas(primer(b)) ++ lista_hojas_b(resto(b))

finsi

finfunc

2. Función fila

La función fila toma un árbol y un número natural como entrada, y devuelve una lista con todas las letras del árbol que se encuentran en la profundidad indicada por el número natural.

Func fila(a:árbol, n:natural) dev l:lista

Si vacio(a) entonces

L <- <>

Si !vacio(a) ^ (n=0) entonces

L <- <raíz(a)>

Si no

L <- fila_b(hijos(a), n-1)

Finfunc

Func fila_b(b:bosque, n:natural) dev l:lista

Si vacio(b) entonces

L <- <>

Si no

L <- fila(primer(b), n) ++ fila_b(resto(b), n)

Finsi

finfunc

3. Función es_camino

La función es_camino toma una lista y un árbol binario como entrada, y devuelve un valor booleano que indica si, comenzando en la raíz del árbol, existe un camino formado por las letras que aparecen en la lista indicada.

func es_camino(l:lista, a:a_bin) dev bool

si vacio(a) entonces

b <- falso

si vacio(l) entonces

b <- verdadero

si no

si raíz(a) != primero(l) entonces

b <- falso

si raíz(a) = primero(l) entonces

b <- es_camino(resto(l), izq(a)) V es_camino(resto(l), der(a))

finsi

finsi

finfunc

4. Función altura

La función altura toma un árbol binario como entrada y calcula su altura.

Func altura(a:a_bin) dev natural

Si vacio(a) entonces “ERROR”

Si no

Si vacio(izq(a)) entonces

Si vacio(der(a)) entonces

Devolver 0

Si no devolver 1 + altura(der(a))

Finsi

Si no

Si (vacio(der(a))) entonces

Devolver 1 + altura(izq(a))

Si no

Devolver 1 + max(altura(izq(a)), altura(der(a)))

Finsi

Finsi

finsi

finfunc

5. Función semicompleto

La función semicompleto toma un árbol binario como entrada y comprueba si es semicompleto.

Func niveles(a:a_bin) dev n:natural

Si vacio(a) entonces

n <- 0

si no

n <- 1 + niveles(izq(a))

finsi

finfunc

Func completo(a:a_bin) dev b:bool

Si vacio(a) entonces

b <- verdadero

si no

b <- completo(izq(a)) ^ completo(der(a)) ^ (niveles(izq(a)) == niveles(der(a)))

finsi

finfunc

Func semicompleto(a:a_bin) dev b:bool

si vacio(a) entonces

b <- verdadero

si no

si completo(a) V (completo(izq(a)) ^ semicompleto(der(a)) ^ (niveles(izq(a)) == niveles(der(a)))) V (semicompleto(izq(a)) ^ completo(der(a)) ^ (niveles(izq(a)) == niveles(der(a)) + 1))

b <- verdadero

finsi

finfun

6. Función monticulo_maximos

La función monticulo_maximos toma un árbol binario como entrada y comprueba si es un montículo de máximos.

Func Mayor_igual(y:entero, a:arbol) dev b:bool

Si vacio(a) entonces

B <- verdadero

Si no

B <- (y <= raíz(a)) ^ Mayor_igual(y, izq(a)) ^ Mayor_igual(y, der(a))

Finsi

finfunc

7. Función son_iguales (Árboles Generales)

La función son_iguales toma dos árboles generales como entrada y comprueba si son iguales, tanto en forma como en contenido.

Func iguales(a1, a2: arbol) dev bool

Si raíz(a1) != raíz(a2) entonces

b <- falso

si no

b <- iguales_b(hijos(a1), hijos(a2))

finsi

finfunc

func iguales_b(b1,b2: arbol) dev bool

si vacio(b1) != vacio(b2) entonces

b <- falso

si no

b <- iguales(primer(b1), primer(b2)) ^ iguales_b(resto(b1), resto(b2))

finsi

finfunc

8. Función iguales (Árboles Binarios)

La función iguales toma dos árboles binarios como entrada y comprueba si ambos árboles tienen los mismos elementos y en la misma posición.

func iguales(a1,a2:a_bin)dev b:bool

si vacio(a1) ^ vacio(a2) entonces

b <- verdadero

si vacio(a1) != vacio(a2) entonces

b <- falso

si no

b <- (raíz(a1) == raíz(a2)) ^ iguales(izq(a1), izq(a2)) ^ iguales(der(a1), der(a2))

finsi

finfunc

9. Función es_imagen_especular

La función es_imagen_especular toma dos árboles generales como entrada y comprueba si el segundo árbol es la imagen especular del primero.

Func imagen_especular(a1, a2: arbol) dev b:bool

Si raíz(a1) = raíz(a2) entonces

b <- imagen_especular_b(hijos(a1), invertir_bosque(hijos(a2)))

Si no

b <- falso

finsi

finfunc

func imagen_especular_b(b1,b2: bosque) dev b:bool

si vacio(b1) != vacio(b2) entonces

b <- falso

si vacio(b1) ^ vacio(b2) entonces

b <- verdadero

si no

b <- imagen_especular(primer(b1), primer(b2)) ^ imagen_especular_b(resto(b1), resto(b2))

finsi

finfunc

10. Función grado_arbol

La función grado_arbol toma un árbol como entrada y calcula su grado. El grado de un árbol es el máximo de los grados de sus nodos.

func grado_arbol(a:arbol)dev n:natural

devuelve n <- max(num_hijos(a), grado_arbol_b(hijos(a)))

finfunc

func grado_arbol_b(b:bosque) dev n:natural

si vacio(b) entonces

n <- 0

si no

n <- maximo(grado_arbol(primer(b)), grado_arbol_b(resto(b)))

finsi

finfunc

11. Función contarPadresPares

La función contarPadresPares toma un árbol como entrada y devuelve la cantidad de nodos que tienen un número par de hijos (0 hijos no se considera un número par).

func contarPadresPares(a:arbol) dev n:natural

si (num_hijos(a) % 2 == 0) ^ (num_hijos(a) != 0) entonces

n <- 1 + contarPadresPares_b(hijos(a))

si no

n <- contarPadresPares_b(hijos(a))

finsi

finfunc

func contarPadresPares_b(b:bosque)dev n:natural

si vacio(b) entonces

n <- 0

si no

n <- contarPadresPares(primer(b)) + contarPadresPares_b(resto(b))

finsi

finfunc

Ejercicios con Árboles Generales

1. Función num_nodos

La función num_nodos toma un árbol general como entrada y calcula cuántos nodos hay en él.

Func num_nodos(a:arbol) dev natural

Devolver n <- 1 + num_nodos_b(hijos(a))

Finfunc

Func num_nodos_b(b:bosque) dev n:natural

Si vacio(b) entonces

Devolver n <- 0

Si no

n <- num_nodos(primer(b)) + num_nodos_b(resto(b))

Finsi

Finfunc

2. Función num_hojas

La función num_hojas toma un árbol general como entrada y devuelve la cantidad total de hojas que tiene.

Func num_hojas(a:arbol) dev n:natural

Si vacio(hijos(a)) entonces

n <- 1

Si no

n <- num_hojas_b(hijos(a))

Finsi

Finfunc

Func num_hojas_b(b:bosque) dev n:natural

Si vacio(b) entonces

n <- 0

Si no

n <- num_hojas(primer(b)) + num_hojas_b(resto(b))

Finsi

finfunc

3. Función max_hijos

La función max_hijos toma un árbol general como entrada y devuelve la mayor cantidad de hijos en un mismo nodo que hay en el árbol.

func max_hijos(a:arbol) dev n:natural

n <- maximo(num_hijos(a), max_hijos_b(hijos(a)))

finsi

func max_hijos_b(b:bosque) dev n:natural

si vacio(b) entonces

n <- 0

si no

n <- maximo(max_hijos(primer(b)), max_hijos_b(resto(b)))

finsi

finfunc

4. Función nivel_n

La función nivel_n toma un árbol binario y un número natural como entrada, y crea una lista con todos los nodos que se encuentren en el nivel indicado por el número natural.

func nivel_n(a:a_bin, n:natural) dev lista

si vacio(a) entonces

l <- <>

si (n=0) entonces

l <- <raíz(a)>

si no

l <- nivel_n(izq(a), n-1) ++ nivel_n(der(a), n-1)

finsi

finfun

5. Función niveles_entre

La función niveles_entre toma un árbol binario y dos números naturales como entrada, y crea una lista con todos los nodos que se encuentren entre los niveles indicados por los dos números naturales.

fun niveles_entre(a:a_bin, n1, n2) dev lista

si vacio(a) entonces

l <- <>

si (n1 = n2) entonces

l <- nivel_n(a, n1)

si (n1 > n2) entonces

Error

Si no

l <- niveles_entre(a, n1, n2-1) ++ nivel_n(a, n2)

Finsi

Finfun

6. Función recorrer_niveles

La función recorrer_niveles toma un árbol binario como entrada y crea una lista formada por todos los niveles del árbol binario.

fun recorrer_niveles(a:a_bin) dev l:lista

si vacio(a) entonces

l <- <>

Si no

l <- niveles_entre(a, 0, altura(a))

Finsi

finfunc