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

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(BinTree<int> t, int x);

Recordeu que un BST és un arbre a on cada subarbre no buit $r(t_0,t_1)$ cumpleix que l’arrel $r$ és major estricte que tots els valors que apareixen en el seu subarbre esquerre $t_0$, i $r$ és menor estricte que tots els valors que apareixen en el seu subarbre dret $t_1$. 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               5
  |               |
   ----       ----
       |     |
       2     4

x: 2

=>

true

Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: main.cc, BinaryTree.hh, searchInBST.hh. Us falta crear el fitxer searchInBST.cc amb els corresponents includes i implementar-hi la funció anterior. Només cal que pugeu searchInBST.cc al jutge.

Entrada

La primera linia de l’entrada descriu el format en el que es descriuen els arbres, o bé INLINEFORMAT o bé VISUALFORMAT.

Després ve la descripció d’un únic arbre binari d’enters, que és un BST.

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.