Antecessors d'un node d'un arbre binari X48392

Donat un arbre binari de valors enters i un enter, escriviu una funció que retorni una llista amb tots els antecessors del valor donat dins l’arbre. Considereu que l’arbre no conté valors repetits.

(Per veure una figura amb l’arbre corresponent a l’exemple d’entrada, consulteu la versió pdf d’aquest enunciat.)

Per exemple, donat l’arbre:

Si el valor d’entrada fos 5, la funció hauria de retornar la llista [3, 6, 7]. Si el valor fos 7, la funció hauria de retornar la llista []. Si el valor fos 10, la funció hauria de retornar la llista [].

Entrada

Com a entrada hi haurà la mida de l’arbre i els nodes de l’arbre binari en postordre. Per cada node s’indica el seu valor i el nombre de fills (2 fills, -1 indica un fill esquerre, 1 indica un fill dret o 0 fills). Podeu utilitzar l’operador >> definit dins la classe arbreBin per llegir l’arbre binari.

A continuació hi haurà una llista amb un o més valors enters.

Sortida

Com a sortida es mostrarà l’estructura de l’arbre binari d’entrada (podeu utilitzar l’operador << definit dins la classe arbreBin) i els antecessors de cada valor de la llista d’entrada.

Observació

Cal fer servir la classe arbreBin que us donem.

Heu d’enviar el fitxer amb la solució program.cpp comprimida en un fitxer .tar amb la funció demanada i el programa principal que la usi:

tar cvf program.tar program.cpp

Observeu que per compilar us donem el Makefile, el mòdul arbreBin i el mòdul listIOint que ofereix operadors de lectura i escriptura de llistes d’enters.