Scribd
Cargar
55 vistas2 páginas

Taller Algoritmos: MaxHeap y BST

El documento presenta dos problemas relacionados con estructuras de datos y árboles. El primer problema involucra la creación de un maxheap a partir de un arreglo aleatorio y la modificación de los hijos de un nodo específico. El segundo problema consiste en crear un BST con valores aleatorios, encontrar y almacenar en un vector las hojas con posición impar en preorder, e imprimir y eliminar esas hojas del árbol. Se entregan indicaciones para implementar los métodos necesarios en problema2.cpp sin modificar la clase BST.

Cargado por

benjamin
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
55 vistas2 páginas

Taller Algoritmos: MaxHeap y BST

El documento presenta dos problemas relacionados con estructuras de datos y árboles. El primer problema involucra la creación de un maxheap a partir de un arreglo aleatorio y la modificación de los hijos de un nodo específico. El segundo problema consiste en crear un BST con valores aleatorios, encontrar y almacenar en un vector las hojas con posición impar en preorder, e imprimir y eliminar esas hojas del árbol. Se entregan indicaciones para implementar los métodos necesarios en problema2.cpp sin modificar la clase BST.

Cargado por

benjamin
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

INFO088-17 Taller Estructuras de Datos y Algoritmos

Martes 5 de julio de 2022


Profs: Héctor Ferrada, Mauricio Ruiz-Tagle

CONTROL SUMATIVO Nº2 – Grupo 1

[3.0 puntos] PROBLEMA 1. Ejecución: ./problema1 n

Durante el trabajo en clases se estudiaron los métodos que convierten un arreglo en un maxheap. En particular, se trabajó con
el método makeMaxHeap, que está disponible en el código fuente [Link]. Utilice dicho método para crear un arreglo
de números enteros aleatorios X[1…n] (no considere la posición 0). Luego, debe leer una posición cualquiera del arreglo (valor
entero p) e intercambiar los valores de los hijos del nodo que se encuentra en esa posición. Para esto, deberá implementar el
método void intercambiaHijos(int *X, int n, int p); que a partir del valor p anterior, valide y reacomode, de ser necesario,
los subárboles que tienen como raíz a los hijos de p, a fin de que X continúe siendo un maxheap.

Ejemplo de ejecución para n = 30 y p = 4:


Bachillerato en Ciencias de la Ingeniería
INFO 063 - “Introducción a la Programación”
Jueves 28 Abril de 2022

[3.0 puntos] PROBLEMA 2. Ejecución: ./problema2 n

Se debe crear un BST con valores (claves) aleatorios. Una vez creado, se debe identificar aquellos nodos del árbol que sean
“hojas” y que, a su vez, tengan una posición (al recorrer en preorder) impar. En el ejemplo de la figura, las hojas que cumplen
esta condición están destacadas en gris:

Ejemplo de ejecución para n = 15:

Para lo anterior, debe crear un arreglo con las hojas de un BST cuyo preorder sea impar, para después eliminar estas hojas
desde el árbol. Para esto:

a) (0.5 pts) En el main(..), cree un BST, t, con n claves aleatorias (≤ M ) e imprima el árbol en preorder. Luego cree el
vector v, vacío y de tipo entero, para invocar al método encuentraHojas(...). A continuación invoque, con t y
v como parámetros, al método listaEliminando(...), para finalizar imprimiendo t nuevamente, mostrando que se
eliminaron las hojas encontradas.
b) (2.0 pts) Cree el método void encuentraHojas(nodoBST *tree, vector<int> &v, int &pre); el cual, recursivamente,
debe insertar en el vector de enteros v las claves de las hojas del árbol cuyo preorder pre sea impar.
c) (0.5 pts) Cree el método void listaEliminando(nodoBST *tree, vector¡int¿&v); el cual debe imprimir las hojas
encontradas y eliminarlas del BST.

Nota importante: no necesita modificar nada en la clase BST, utilice los métodos disponibles y trabaje solo en el fuente
[Link].

También podría gustarte