Mètode de BinaryTree que calcula el mínim de cada profunditat

Donada la classe BinaryTree<T>, implementa el mètode públic RECURSIU:

    void minAtDepth(vector<T> &l) const;

Aquest mètode guarda en un vector el mínim dels valors dels nodes de
l’arbre de cada nivell de profunditat tenint en compte que l’arrel es
troba a profunditat 0. El vector hauria d’emmagatzemar a la casella 0 el
mínim dels nodes a profunditat 0, a la casella 1 el mínim de profunditat
1, etc. El vector on es retorna el resultat inicialment és buit.

Exemple:

        10
       /  \
      4    8
     / \    \
    7   2    5
         \
          3
    	

   k    Nodes    minAtDepth(k)
  --- --------- ---------------
   0     10           10
   1    4, 8           4
   2   7, 2, 5         2
   3      3            3

Què has de lliurar

Entre els fitxers que s’adjunten en aquest exercici, trobaràs
BinaryTree.old.hpp, a on hi ha una implementació de la classe genèrica
BinaryTree. En primer lloc, hauràs de fer:

    cp BinaryTree.old.hpp BinaryTree.hpp

A continuació si obres el fitxer BinaryTree.hpp al final del mateix
trobaràs el mètode que has d’implementar:

    template <typename T>
    void BinaryTree<T>::minAtDepth(vector<T>& l) const {
    }

IMPORTANT: No toquis la resta de la implementació de la classe, excepte
si necessites afegir algun mètode auxiliar o atribut a la part privada.

També pots trobar entre els fitxers que s’adjunten a l’exercici el
fitxer program.cpp (programa principal) i Makefile per a compilar i
generar l’executable. El programa principal que t’oferim ja s’encarrega
de llegir els arbres binaris i fer les crides al mètode indicat. Només
cal que implementis el mètode minAtDepth.

Per a pujar la teva solució, has de crear el fitxer solution.tar així:

    tar cf solution.tar BinaryTree.hpp

Observacions

- No es pot usar cap contenidor auxiliar de la STL (stack, queue, list,
  …) llevat de vector.

- Has de trobar una solució RECURSIVA i eficient del problema. En
  particular, no hi hauria d’haver cap bucle en cap de les
  funcions/accions que implementis.

- Recorda que tots els mètodes que implementis han de tenir les
  corresponents Precondició (Pre) i Postcondició (Post).

- En les crides recursives inclou la hipòtesi d’inducció (HI) i la
  funció de fita (FF).

Entrada

Una seqüència d’arbres binaris.

Sortida

Per a cada arbre binari s’escriurà el resultat del mètode minAtDepth.

El programa principal que t’oferim ja s’encarrega de llegir la seqüència
d’arbres binaris i fer les crides corresponents al mètode de BinaryTree
que se’t demana d’implementar. Només cal que facis les modificacions
abans esmentades dins el fitxer BinaryTree.hpp.

Per més detalls de com és l’entrada i la sortida consulta els jocs de
proves públics.

Informació del problema

Autoria: Bernardino Casas

Generació: 2026-06-11T20:22:07.346Z

© Jutge.org, 2006–2026.
https://jutge.org
