Newsgroup: it.comp.lang.pascal
Titolo: Alberi binari!

Salve per tenervi un po in esercizio ;) vi posto questo mio problema
Definire un algoritmo RICORSIVO, che ricevuti in ingresso un albero binario 
di ricerca e due chiavi di valore intero k1 e k2 con k1<=k2, cancelli tutti 
i nodi dell'albero che hanno un valore compreso tra k1 e k2 (duplicati e 
estremi compresi).
Chi mi da una mano ?
Tnx
ReDiCuori
-- 
-- 
L'informatica è un' arte
---------------------------------------------------------
www.securitygroup.it
Società di servizio che opera nel campo
della sicurezza aziendale
---------------------------------------------------------
www.pascallike.too.it
http://utenti.lycos.it/pascallike
il sito sulla programmazione pascal
sorgenti, tutorial ed utility
------------------------------------------------------------
www.treves-srl.com
Libreria Internazionale Treves
Via Toledo 249/250 Napoli
------------------------------------------------------------
www.alphalibri.com
Vendita ingrosso di libri
Via S.Anna dei Lombardi 10 , Napoli
------------------------------------------------------- 

 
Uhm sei stato un po' vago. I dati dentro la struttura sono ordinati o 
messi come capita? quando elimini uno { o più } elementi l'albero deve 
rimanere un bel alberello binario o può avere un sacco di foglie morte?
Visto che hai parlato di duplicati non credo che l'ablero sia ordinato 
tipo questo qui sotto:
     1
    / \
   2   3
  / \ / \
4  5 6  7
{ scusate per l'ascii }
Si più preciso :D
cmq la ricorisività non è un problema anzi forse è pure meglio cioè 
basta chiamare
EliminaK1K2(K1, K1, Albero^.R );
EliminaK1K2(K1, K1, Albero^.L );
il problema è cosa succede quando si elimina un elemento { ad esempio il 
3 } che ha dei "figli" si puo' decidere far "shiftare" gli elementi { ma 
cosi si perde l'ordinamento } oppure bisogna fare un bel po' di macheggi
cioè una cosa è arrivare a
     1
    / \
   2   7
  / \ / \
4  5 6
una cosa è
     1
    / \
   2   4
  / \ / \
5  6 7
oppure l'ordinamento puo' essere fato in modo diverso
     1
    / \
   2   5
  / \ / \
3  4 6  7
Insomma dire albero binario è un po' vago :D
-- 
Il Razziatore,
The Only Good Windows is an uninstalled Windows
-----------------------------------------------
MSN   : 
IlRazz...@netscape.net
ICQ   : 67552596
Yhaoo : Razziatore82
-----------------------------------------------
Founder of MediaPlayer Project
http://mpp.iwebland.com

 messi come capita?
Raz Raz ... mi meraviglio di te ho detto albero binario di RICERCA quindi 
l'albero è ordinato :)
se T è il tuo albero  Key[T]> di tutte le chiavi presenti nel sottoalbero 
sinizio e Key[T]<= di tutte le chiavi presenti nel sottoalbero destro. 
Quindi cancellando cancellando devo rimanere intatte le proprietà 
dell'albero binario.
           6
      4        10
   2    5   6       14
1    3        7  12    15
date K1=10 e K2=14  bisogna cancellare 10,14,12. NB K1 e K2 possono non 
essere contenute nell'abero binario di ricerca, il tutto deve essere 
impostato come una funzione.
ora
     se T=nil  ----> return nil
     altrimenti   T è  una radice con sotto albero sinistro e destro
                e Key[T] può essere
                                                  1)  Key[T]<K1<K2
                                                  2)  K1<=Key[T]<=K2 o 
K1<Key[T]<K2
                                                  3)  K1<K2<Key[T]
   a mio parere la situazione tu conveniete è la (2) quindi avevo pensado di 
spostarmi fino ad ottenerla
    cancellaIntervallo (t,k1,k2)
        if t=nil return nil
        else if Key[T]<k1
              return cancellaIntervallo(t.dx,k1,k2)
        else if Key[T]>k2
              return cancellaIntervallo(
t.sx
,k1,k2)
        else
            if Key[T] =>k1
                nodo=stacca_max(
t.sx
);
                Key[T]=Key[Nodo];
            else
                 nodo=stacca_max(t);
                 Key[t]=key[nodo];
             t=cancellaIntervallo(t,k1,k2);
             return t;
Mi... penso di averlo scritto... ma con la ricorsione non è che ci sono 
uscito in tutte le sere in questi anni !!! Lo controlli ?!? Tnx
Stacca_max prende il nodo con la chiave più grande (quello più a destra di 
tutti) lo stacca dall'albero e ritorna il puntatore.... (dovrei pure 
implementarlo :( ) come le odio queste cose !!!


 il tutto deve essere impostato come una funzione.
io ho un'idea e una mezza implementazione, ma questa non l'ho capita. Vuoi 
che restituisca un albero diverso (nuovo, riallocato) senza toccare il 
vecchio?  altrimenti non comprendo :)
-- 
Dreadnaut - 
http://dreadnaut.servebeer.com/
(Life would be easier if I had the source code)

 vecchio?  altrimenti non comprendo :)
Voglio che modifichi l'albero e ritorni l'albero modificato come se fosse 
una funzione


Dai Dread che ho altri 2 o3 rompicapi simili... :)
ReDiCuori
-- 
-- 
L'informatica è un' arte
---------------------------------------------------------
www.securitygroup.it
Società di servizio che opera nel campo
della sicurezza aziendale
---------------------------------------------------------
www.pascallike.too.it
http://utenti.lycos.it/pascallike
il sito sulla programmazione pascal
sorgenti, tutorial ed utility
------------------------------------------------------------
www.treves-srl.com
Libreria Internazionale Treves
Via Toledo 249/250 Napoli
------------------------------------------------------------
www.alphalibri.com
Vendita ingrosso di libri
Via S.Anna dei Lombardi 10 , Napoli
-------------------------------------------------------
"ReDiCuori" <redicu...@NOSPAMlibero.it> ha scritto nel messaggio 
news:VBOOd.22449$Of5....@nntpserver.swip.net...


 Dai Dread che ho altri 2 o3 rompicapi simili... :)
irc #turbopascal dove ci aspetta (ne sono certo) il buon Razz :)


 ha scritto nel messaggio 
news:Xns95F9D897BB497ether@casa...


 Che server ?
azzurra (ero al tel prima)


 
Sorry ero online ma non so perchè non ero joinato a #TurboPascal, chiedo 
scusa :D
