Camí preferent d'un arbre X38658

Recordeu que una fulla d’un arbre és un node sense cap successor. Un camí dins d’un arbre és una successió de nodes que van de l’arrel a una fulla.

Donat un arbre binari a d’elements de qualsevol tipus, definim el camí preferent de l’arbre a de la següent manera: si a és buit llavors el camí preferent d’a també és buit; en cas contrari, el camí preferent d’a el forma l’element arrel d’a seguit del camí preferent del fill d’a que tingui més elements. Si a té dos fills no buits amb el mateix nombre d’elements es tria el camí preferent del fill esquerre.

Volem una operació que ens permeti saber quin és el camí preferent d’un arbre d’enters, representant aquest camí amb una pila d’enters, ordenada de forma que el primer element del camí (si existeix) sigui al cim de la pila. Feu servir la següent especificació:

Exemple: considereu els dos arbres següents

• el camí preferent d’a és 7 6 -3 -5 2.
• el camí preferent de b és 7 -2 -3 5.

Entrada

L’entrada és un arbre d’enters.

Sortida

La sortida és una pila amb el camí preferent. L’arrel de l’arbre és al cim de la pila.

Observació

Només s’ha d’enviar un fitxer que contengui la funció amb la capçalera de l’enunciat i qualsevol altra funció auxiliar que cregueu convenient, sense la funció main. Afegiu-hi també els includes de les classes Arbre i stack mitjançant

#include "Arbre.hh"

#include <stack>