[C++]: Albero binario e ricerca elemento più piccolo

[giudf]

Ragazzi,

Mi sto dilettando sugli alberi binari, e sto facendo una valanga di esercizi che mi scarico di volta in volta dalla rete... Ne ho, però, trovato uno che mi sta "incastrando" perchè non riesco a trovare un algoritmo giusto per risolverlo, dunque il prototipo della funzione è questo:

int OrderStatistic(TREENODEPTR t, int *i)

(TREENODEPTR è un puntatore ad una struttura TREE [la classica struct dell'albero binario con un intero, un puntatore destro ed uno sinistro])

Dunque la funzione deve trovare l'iesimo elemento più piccolo dell'albero:

se i = 1 l'elemento più piccolo
se i = 2 il secondo e così via

Con una "marea" di funzioni ausiliari magari si farebbe, ma a qualcuno non viene in mente un metodo + furbo ?

Grazie

[giudf]

... Non mi siete stati molto d'aiuto, ma sono riuscito a risolverlo ugualmente con una sola funzione ausiliaria [ovviamente solo con gli alberi di ricerca binaria, xkè altrimenti sarebbe impossibile] (meglio sbattendoci la testa le cose entrano meglio)

Cmq, avevo bisogno di un consiglio:
Qualcuno sa di qualche sito che propone esercizi di alberi e liste (possibilmente con ricorsione) ve lo chiedo perchè ho fatto una ricerchina con google ma non ho trovato granchè, e quel poco che ho trovato era o troppo banale o già l'avevo fatto.

TNX !!!

[fastcoder]

Lo so che hai risolto...ma secondo te questa funzione può andare (senza funzioni ausiliarie)?

int OrderStatistic(TREENODEPTR t, int *i)
{
  if( !t )
    return MAX_INT;
  if( !t->left )
  {
    return t->value;
  }
  else
  {
    int r = OrderStatistic(t->left, i);
    if( *i > 1 )
    {
      r = t->value;
      *i--;
    }
  }
  return r;
}

ovviamente l'albero deve essere ordinato

[giudf]

Carina, carina veramente, il mio compilatore (gcc di Fedora 5.0), xò se dichiaro variabili in mezzo al codice mi da warning, quindi ne ho dovuta far per forza una aux che prendeva tre argomenti !!

Cmq si, credo la tua funzione vada, ed è anke molto elegante !!

[fastcoder]

Probabilmente perchè non è C++ o Ansi C99 (dato che è il gcc probabilmente compila il file come C becero )
Comunque mi è anche venuta in mente una funzione per un albero non ordinato..farei

struct recMinValue
{
  int v;
  recMinValue *prev;
  recMinValue(int i) { v = i; prev = NULL; }
}

recMinValue *tail = NULL;
recMinValue *head = NULL;
    
int OrderStatistic(TREENODEPTR t, int *i)
{
  void traverse(t)
  {
    if( t->right )
      traverse(t->right);
    if( t->left )
      traverse(t->left);
    aggiungere t->value a lista mantenendone l'ordine (in testa i valori minori)
  }

  if( !t )
    return MAX_INT;
  
  head = tail = NULL;
  traverse(t, i);
  
  ritornare il valore dell'elemento i-esimo della lista ordinata
  
  return r;
}

Ovviamente non compila e non è completa (purtroppo ora non ho molto tempo ) L'idea è di mantere una lista accessoria ordinata con in testa i valori minori....riempirla con un semplice attraversamento dell'albero mantenendo l'ordinamento (in maniera non troppo complessa in fondo) e poi ritornare l'i-esimo elemento partendo dalla testa.
Sicuramente questo metodo occupa memoria ed è più lento...ma se l'albero non è ordinato non credo di conoscere un metodo più furbo (in fondo questo metodo è un trucchetto...siccome l'albero non è ordinato creo una lista ordinata e uso quella)

[giudf]

Per quanto riguarda esercizi vari sulla ricorsione non sai dove posso trovare qualcosa ?

Io ne ho fatti parecchi e, finora sono riuscito a farli tutti, solo uno mi ha dato problemi e vedendo la soluzione, continuo a non capire come lavora, te la voglio mostrare sperando che puoi "illuminarmi" (anche se per iscritto è difficile):

Dunque, l'esercizio riguarda la ricorsione su liste, e si richiede, data una lista di far ritornare il puntatore all'inizio della lista invertita, il codice è questo:

L_PTR InvertiLista(L_PTR L){
   L_PTR temp;
   if(!(L) || !(L->next))
     return L;
    else{
      temp = InvertiLista(L->next)
      L->next->next = L;
      L->next = NULL;
      return temp } }

L'ho provata e funzione alla grande ma come ? Quello non riesco a capirlo !!!

[fastcoder]

In effetti è un poco complicato da capire
Provando ad eseguirla sulla carta in effetti funziona in modo furbo, provo a spiegarmi:
- il pratica viene chiamata successivamente la funzione con tutti gli elementi della lista
in ordine (ricorsione)
- quando arriva all'ultimo elemento la ricorsione finisce e viene eseguito il backtracking
- il back tracking come dice il nome procede per ogni elemento a ritroso e se faccio
L->next->next = L in pratica non faccio che dire che l'elemento successivo di quello
che sto considerando punta a me medesimo; la cosa non chiara era perchè mettevo a null
il next dell'elemento corrente (in fondo c'erano anche gli altri elementi); in effetti però
quell'assegnamento viene sovrascritto nel back tracking successivo; questo però
non avviene per il primo elemento che fa uscire dalla funzione che quindi ha next uguale
a NULL in quanto in effetti ora è l'ultimo elemento della lista;
- l'ultima furbata è quella di salvarsi il temp prima della ricorsione e ritornare L quando a finito la
ricorsione...in questo modo si salva l'elemento corrente e ritorna sempre quello (quindi alla fine
ritorna l'ultimo elemento della lista originale che è la testa della lista invertita)
Proprio una furbata.
Proviamo la lista A->B->C (se ci riesco):
1) InvertiLista(A)
2) InvertiList(B)
3) InvertiLista(C)
ora mi fermo e ritorno C quindi in 2 ho temp = C, L = B quindi L->next->next è in realtà
B->next->next=B che è anche C->next = B, inoltre metto B->next = NULL; poi torno C
poi ritorno in 1 e ho temp = C, L=A quindi L->next->next è in realtà A->next->next=A che è
anche B->next=A, e poi A->next = null, poi torno ancora C
a questo punto esco da 1 con:
C->B->A
Spero di aver capito e nel caso di essermi spiegato...
Per i siti mi spiace ma non ne conosco

[giudf]

Grazie, 6 l'uomo giusto.... ora devi fare solo l'esame al posto mio !!! :maLOL:

[fastcoder]

Mi spiace....l'ho già fatto e molti anni fa

[giudf]

... l'avevamo notato un po tutti.

Vabbè io vado a prende il treno (l'exam ce l'ho alle 15:00) ci si vede !!!