Nodes dominants en arbre binari-recursiu. S98355

Un node dominant en un arbre binari és un node que té un valor que és més gran que qualsevol dels nodes que tenen els seus fills esquerre i dret. Implementa un algorisme recursiu que, donat un arbre binary d’enters, retorni la llista de tots els nodes dominants de l’arbre. NOTA IMPORTANT: les fulles de l’arbre MAI són nodes dominants.

/* Pre: a és un arbre binary d'enters. */
/* Post: Retorna una llista amb tots els nodes dominants de l'arbre 
o una llista buida si no n'hi ha cap */
list<int> Dominants(BinaryTree<int> &a) {
}

NOTES IMPORTANTS:

• L’algorisme ha de ser eficient, és a dir, que no realitzi càlculs innecessaris.

• Entre els fitxers que s’adjunten en aquest exercici trobaràs el fitxer BinaryTree.hpp que conté la implementació de la classe BinaryTree. No cal que modifiquis aquest fitxer.

• També trobaràs el fitxer program.cpp i el Makefile per a compilar i generar l’executable. El programa principal ja s’encarrega de llegir les dades de l’arbre i cridar al mètode indicat. Només cal que implementis el mètode Dominants.

• Es valorarà la correctesa i eficiència de la solució així com la correcta especificació de la precondició, la postcondició, la hipòtesi d’inducció i la funció fita.

• Per a pujar la solució has de crear el fitxer solution.tar així:
  
  tar cf solution.tar Dominants.cpp

Entrada

Com a entrada hi haurà els nodes de l’arbre en postordre.

Sortida

Com a sortida es mostrarà l’arbre original i la llista de nodes dominants.