Cerca de subarbres binaris X09609

Considerem la representació habitual amb nodes de la clase Arbre per manegar arbres binaris genèrics d’elements de tipus T que podeu trobar als fitxers públics. Un arbre només té un atribut: un punter al primer node. Cada node conté la seva info i dos punters que representen els seus succesors.

Volem una nova operació de la classe que donat un arbre a i un valor x de tipus T comprovi si x apareix en a; cas que la cerca sigui exitosa, ha d’obtenir el subarbre que tingui com a arrel l’aparició d’x més propera a l’arrel d’a. Cas d’haver-hi diferents aparicions d’x a la distància mínima, ha d’obtenir el subarbre de més a l’esquerra. Feu servir la següent especificació:

Exemples: siguin els següents arbres d’enters

llavors les instruccions a.sub_arrel(a1, -2), b.sub_arrel(b1, 1), c.sub_arrel(c1, 10), d.sub_arrel(d1, 6) han de produir els següents arbres

Dissenyeu aquesta operació sense utilitzar cap de les operacions públiques del arbres binaris, accedint directament als atributs de la classe Arbre. Si que podeu fer servir l’operació privada

Entrada

L’entrada és un arbre i un enter x.

Sortida

La sortida és un subarbre de l’arbre d’entrada amb x com a l’arrel amb les condicions de l’enunciat.

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 i sense posar-hi cap “include”.