DOMANDA Alberi Di Ricerca C

Fab996

Utente Attivo
174
5
Devo scrivere una funzione di stampa dei valori contenuti nei nodi nel cammino dalla radice ad un nodo contenente un valore i in un BST(Binary search tree)

Ho scritto questa funzione che effettivamente funziona:

Codice:
typedef struct TNodo {
    int Atomo;
    struct TNodo *left;
    struct TNodo *right;
} Nodo;

typedef Nodo* Bst;

void print(Bst b,int i) {
    if(b!=NULL) {
        if(b->Atomo == i) {
            printf("%d\n",b->Atomo);
            return;
        }
        else {
            if(i<b->Atomo)
                print(b->left,i);
            else
                print(b->right,i);
        }
    }
    printf("%d\n",b->Atomo);
}



Il mio dubbio è che prima di arrivare a questo algoritmo, scrivevo lo stesso algoritmo omettendo il return, quindi mi veniva stampato il valore cercato 2 volte, una volta dal primo if(b->Atomo==i), la seconda volta in quanto la funzione ricorsiva torna indietro di un passo ma b punta ancora al valore quindi viene ristampato dal secondo printf(). Quindi mi è venuto in mente di mettere questo return che non torna niente(in quanto a volte l'ho visto), però sinceramente non ho capito come un return possa non tornare alcun valore e come mai con il return è come se la funzione ricorsiva facesse due passi all'indietro e quindi l'ultimo valore cercato viene stampato una sola volta..
 

1nd33d

Utente Attivo
653
279
CPU
Intel i5 3570K @ 4,5Ghz
Dissipatore
Scythe Mugen 2
Scheda Madre
Gigabyte Z77X-UD3H
HDD
Samsung 840 PRO 256GB + Sandisk Ultra 250GB + Sandisk Plus 960GB
RAM
2x8GB Crucial Ballistix Tactical @2000Mhz CL9
GPU
XFX RX480 GTR Black Edition
Audio
Auzentech X-Fi Forte
Monitor
AOC i2369VW
PSU
Seasonic P660
Case
eh?
Periferiche
Razer Naga HEX v2
OS
Windows 10 64bit - Linux Mint 18
La keywork return non fa altro che terminare la funzione rimuovendo il record dallo stack e fornendo allo stack chiamante un risultato. Return senza nulla è come ritornare void (niente insomma), e il motivo per cui non ti stampa due volte il valore è che non viene eseguito l'ultimo printf della funzione.

edit: ho capito dopo come hai implementato la funzione
 
  • Like
Reactions: Fab996

Fab996

Utente Attivo
174
5
La keywork return non fa altro che terminare la funzione rimuovendo il record dallo stack e fornendo allo stack chiamante un risultato. Return senza nulla è come ritornare void (niente insomma), e il motivo per cui non ti stampa due volte il valore è che non viene eseguito l'ultimo printf della funzione.

Comunque non mi pare che la funzione faccia quello che dici, nel senso che stampa solo il valore cercato (tra l'altro noto) mentre dovrebbe stampare i valori dei nodi nel cammino dalla radice al nodo trovato.

Infatti li stampa, stampa tutti i valori del cammino dalla radice al nodo che possiede quel valore, solo che prima(senza return) il nodo che possedeva proprio quel valore inserito, veniva stampato due volte. Che poi mi sono accorto che quel return è inutile bastava scrivere
Codice:
void print(Bst b,int i) {
    if(b!=NULL) {
        if(b->Atomo == i) {
            printf("%d\n",b->Atomo);
           
        }
        else {
            if(i<b->Atomo)
                print(b->left,i);
            else
                print(b->right,i);
            printf("%d\n",b->Atomo);
        }
    }
}
 

1nd33d

Utente Attivo
653
279
CPU
Intel i5 3570K @ 4,5Ghz
Dissipatore
Scythe Mugen 2
Scheda Madre
Gigabyte Z77X-UD3H
HDD
Samsung 840 PRO 256GB + Sandisk Ultra 250GB + Sandisk Plus 960GB
RAM
2x8GB Crucial Ballistix Tactical @2000Mhz CL9
GPU
XFX RX480 GTR Black Edition
Audio
Auzentech X-Fi Forte
Monitor
AOC i2369VW
PSU
Seasonic P660
Case
eh?
Periferiche
Razer Naga HEX v2
OS
Windows 10 64bit - Linux Mint 18
L'unico "problema" ora è che se il valore non c'è nell'albero, tu comunque stampi un cammino, o no? Comunque sarebbe per lo più una questione di forma.
 
  • Like
Reactions: Fab996

Fab996

Utente Attivo
174
5
Quella situazione non l'ho trattata in quanto non descritta dal problema, comunque penso si possa risolvere scrivendo una funzione che verifica se il valore è presente nell'albero e poi con un if-else che se il valore è presente fa partire la funzione ricorsiva, altrimenti stampa un errore.
Avrei un'altra domanda, devo scrivere una funzione che conti i nodi ad un determinato livello di un albero binario
Io ho scritto questo codice, il problema è che funziona solo per alberi binari completi, come posso implementarlo che funzioni per alberi binari qualsiasi ?
Codice:
int nodilivello(Bit_node n,int i) {
    if (i==0)
        return 1;
    if (n!=NULL)
        return nodilivello(n->left,i-1) + nodilivello(n->right,i-1);
    else
        return 0;
}
 

rodhellas

Utente Èlite
1,518
425
CPU
Ryzen 5 3600
Dissipatore
GELID Phantom
Scheda Madre
MSI B450 Gaming Plus Max
HDD
500GB m.2 + 2TB HDD
RAM
16GB Corsair LPX 3000mhz
GPU
Gigabyte GTX 960 OC
Audio
Integrata
Monitor
SyncMaster 223BW
PSU
Antec HCG-520M
Case
Meshify C
Net
Gigabit Fastweb
OS
Windows 10 64bit
Per terminare la ricorsione devi ritornare qualcosa. Essendo void la funz
Quella situazione non l'ho trattata in quanto non descritta dal problema, comunque penso si possa risolvere scrivendo una funzione che verifica se il valore è presente nell'albero e poi con un if-else che se il valore è presente fa partire la funzione ricorsiva, altrimenti stampa un errore.
Avrei un'altra domanda, devo scrivere una funzione che conti i nodi ad un determinato livello di un albero binario
Io ho scritto questo codice, il problema è che funziona solo per alberi binari completi, come posso implementarlo che funzioni per alberi binari qualsiasi ?
Codice:
int nodilivello(Bit_node n,int i) {
    if (i==0)
        return 1;
    if (n!=NULL)
        return nodilivello(n->left,i-1) + nodilivello(n->right,i-1);
    else
        return 0;
}
Invece di controllare se n sia nullo, controlla che il nodo a cui punta n sia nullo ( quindi n->left != NULL && n->right != NULL) e in base a ciò scorri l'albero
 

Entra

oppure Accedi utilizzando

Hot: PS5 VS XBOX X/S?

  • Playstation 5

    Voti: 456 63.3%
  • XBOX Series X/S

    Voti: 264 36.7%

Discussioni Simili