Cerca en un BST (arbre de cerca binària) X70970

Implementeu una funció RECURSIVA que, donat un arbre binari de cerca (BST) d’enters t, i un valor x, retorna un booleà indicant si x apareix a l’arbre. Aquesta és la capcelera:

// Pre: t és un BST
// Post: Retorna cert si i només si x apareix a t
bool searchInBST(BinaryTree<int> &t, int x);

Recordeu que un BST és un arbre a on cada subarbre no buit r(t₀,t₁) cumpleix que l’arrel r és major estricte que tots els valors que apareixen en el seu subarbre esquerre t₀, i r és menor estricte que tots els valors que apareixen en el seu subarbre dret t₁. La gràcia dels BST és que, per a trobar si un cert element hi apareix, ho podem fer més ràpid aprofitant el fet que els seus elements cumpleixen aquesta propietat d’ordenació. Tingueu en compte que els jocs de proves consistiran en arbres bastant equilibrats, així que valdrà la pena que feu això.

Aquí tenim un exemple de paràmetres d’entrada de la funció i la corresponent sortida:

t: 3(1(,2),5(4,))
x: 2
=>
true

Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, program.cpp, BinaryTree.hpp, searchInBST.hpp. Us falta crear el fitxer searchInBST.cpp amb els corresponents includes i implementar-hi la funció anterior. Quan pugeu la vostra solució al jutge, només cal que pugeu un tar construït així:

tar cf solution.tar searchInBST.cpp

Entrada

L’entrada té una primera línea amb un string describint un BST d’enters.

Després segueixen un nombre arbitrari de casos. Cada cas consisteix en una línia amb un enter x. Fixeu-vos en que el programa que us oferim ja s’encarrega de llegir aquesta entrada. Només cal que implementeu la funció abans esmentada.

Sortida

Per a cada cas, la sortida conté la corresponent indicació de si l’element pertany a l’arbre o no. Fixeu-vos en que el programa que us oferim ja s’encarrega d’escriure aquesta sortida. Només cal que implementeu la funció abans esmentada.

Observació

La vostra funció i subfuncions que creeu han de treballar només amb arbres. Heu de trobar una solució RECURSIVA del problema. En les crides recursives, incloeu la hipòtesi d’inducció, és a dir una explicació del que es cumpleix després de la crida, i també la funció de fita/decreixement o una justificació de perquè la funció recursiva acaba.