Examen Septiembre-2 2018, preguntas y respuestas PDF

Preview

Summary

Examen Septiembre-2 2018, preguntas y respuestas...

Description

ADDA/EDA 2ª Convocatoria - Septiembre Curso 2018/2019

Ejercicio 2 – Árboles El árbol de sumas del árbol de enteros A, es otro árbol B con la misma estructura, tal que cada nodo de B es la suma de todos los descendientes de su correspondiente en A, incluyendo éste. Véase el siguiente ejemplo: 3

14

/ 2 / -3 / 5

\ -1 \ 8

\ -3

/ 4

/ 9 \ -2

/ 0

/ -1 \ 1

/ 5

\ 2 \ / 8 4

\ -3

\ -1 / 0

\ 1

SE PIDE: a) Implemente un algoritmo recursivo que devuelva el árbol de sumas de otro árbol. b) Calcule la complejidad del algoritmo implementado en el apartado a.

Solución Algoritmo: private static BinaryTree sumas(BinaryTree a) { BinaryTree res = null; switch (a.getType()) { case Empty: res = BinaryTree.empty(); break; case Leaf: res = BinaryTree.leaf(a.getLabel()); break; case Binary: res = BinaryTree.binary(a.getLabel() + sumas(a.getLeft()).getLabel() + sumas(a.getRight()).getLabel(), sumas(a.getLeft()), sumas(a.getRight())); break; } return res; }

Complejidad: La complejidad del algoritmo presentado es lineal, Θ(n), ya que es necesario recorrer todos los nodos del árbol....