DOMANDA Alberi Di Ricerca C

[Fab996]

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:

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]

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

 

[Fab996]

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

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]

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.

 

[Fab996]

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 ?

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]

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 ?

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