Comprovar si un arbre binari és un arbre binari de cerca X25695

Dissenyeu una funció que comprovi si un arbre binari és un arbre binari de cerca (BST). Un arbre binari de cerca és aquell en què:

• el subarbre esquerre d’un node només conté nodes amb valors inferiors a l’arrel d’aquest node,

• el subarbre dret d’un node només conté nodes amb valors més grans que el valor d’aquest node, i

• els subarbres dret i esquerre són ambdós arbres binaris de cerca

El següent arbre és un arbre binari de cerca (per veure la imatge cliqueu a la versió PDF):

El següent arbre no és un arbre binari de cerca:

Per resoldre aquest exercici de forma iterativa, es recomana que comproveu que el recorregut en inordre de l’arbre binari us dóna una llista ordenada de forma creixent.

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 esquerra, 1 indica un fill dret o 0 fills). Podeu utilitzar l’operador >> definit dins la classe arbreBin per llegir l’arbre binari.

Sortida

Com a sortida es mostrarà l’estructura de l’arbre binari (podeu utilitzar l’operador << definit dins la classe arbreBin) seguit d’un d’aquests dos textos:

L'arbre és un arbre binari de cerca.
L'arbre no és un arbre binari de cerca.

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:

tar cvf program.tar program.cpp

A l’enviar la solució escriviu una anotació ("Solució iterativa" o "Solució recursiva") segons el tipus de solució que hagueu fet.

Observeu que per compilar us donem el Makefile i el mòdul arbreBin.