Non credo vada bene (comunque usa i tag [ code]).
Se ho capito quello che hai scritto, tu elimini i nodi pari partendo dalle foglie dell'albero (perché richiami ricorsivamente la funzione sui rami sx e dx e solo dopo fai la verifica su pari o dispari), quindi poi ti risulta ovviamente difficile costruire l'albero T'.
Secondo me dovresti intanto iniziare a invertire le parti e togliere il return prima di inserisciabr(), in questo modo:
nodo* Algo(T){
nodo*app;
If T.key%2==0
nuovo=Alloca nuovo nodo;
nuovo.key=T.key;
inserisciabr(app,nuovo);
if T!=Nill
If T.sx!=Nill
app=Algo(T.sx);
If T.dx!=Nill
app=Algo(T.dx);
return app;
}
In questo modo prima controlla se il nodo corrente è pari, e nel caso lo inserisce nell'altro albero, dopodiché procede sul ramo sx e poi sul dx.
Ovviamente neanche questa è la soluzione corretta, perché le specifiche ti chiedono anche di eliminare i nodi dal primo albero, ma quello prova a farlo tu.
ciao