Inserció a un BST Y74034

Donat un arbre binari de cerca (BST) d’enters i un valor, implementa una funció que retorni un nou BST amb el valor inserit a la posició correcta. Si el valor ja existeix a l’arbre, la funció ha de retornar el mateix arbre sense canvis.

/**
 * @brief Insereix un valor en un BST.
 *
 * @param t Un arbre binari de cerca.
 * @param x Valor a inserir.
 * @returns Un nou BST amb `x` inserit a la posició correcta.
 *          Si `x` ja és a `t`, retorna `t` sense canvis.
 */
BinTree<int> bst_inserta(BinTree<int> t, int x);

Recordeu que BinTree<int> és immutable: no es pot modificar un arbre existent, sinó que cal construir-ne un de nou.

Entrada

L’entrada consisteix en una seqüència de casos. Cada cas conté un arbre binari de cerca en format visual i, a continuació, una seqüència d’enters a inserir.

Sortida

Per a cada cas, la sortida mostra l’arbre resultant d’inserir tots els valors a l’arbre inicial, en format visual.

Observació

Els fitxers públics (icona del gatet) són: la classe BinTree (fitxer bintree.hh), l’entrada/sortida de BinTree (bintree-io.hh) i el programa principal. També hi ha un Makefile i el directori .vscode que té la configuració per compilar i debuggar amb VSCode.

Has d’implementar bst_inserta en un fitxer .cc nou, compilar (està preparat per poder compilar i debuggar amb VSCode), i finalment enviar només el fitxer amb la funció.