Buonasera! Sto cercando (disperatamente) di svolgere un esercizio, ma ho dei problemi a riguardo.
L'esercizio è il seguente :
"Sia dato un albero binario di ricerca T (i cui nodi contengono esclusivamente un campo chiave, un campo figlio sinistro e un campo figlio destro). Scrivere un algoritmo ITERATIVO efficiente che cancelli dall'albero T tutti i nodi che stanno a profondità compresa tra i valori l1 e l2 (dati in ingresso) e le cui chiavi siano pari e comprese tra i valori k1 e k2 (anch'essi dati in ingresso). Tutte le condizioni da verificare si riferiscono sempre all'albero originario fornito in ingresso. "
Allora io ho pensato di utilizzare una coda, credendo (probabilmente erroneamente) di rendere più efficiente l'algoritmo con una visita in ampiezza piuttosto che in profondità. Il problema che non riesco a superare è però alla base, e cioè in che modo conservo l'informazione della profondità? O meglio a che punto l'aggiorno? Mi ritrovo con una profondità non coerente al nodo per cui il controllo che poi devo andare a fare prima della cancellazione mi risulta sfalsato.
Non chiedo che qualcuno mi risolva l'esercizio in C, ma magari se possibile qualcuno potrebbe aiutarmi dandomi qualche input che mi aiuti anche nel ragionamento per arrivare alla soluzione. Ho provato anche utilizzando uno stack, ma il mio problema resta "a che punto della funzione aggiorno la profondità in modo che essa rimanga coerente" ?!
Grazie mille spero qualcuno possa aiutarmi