[C++] Problema con calcolo peso di un BST

[xjokerx]

Salve, oggi vi scrivo perché ho riscontrato un problema con l'implementazione del codice per quanto riguarda il calcolo del peso di un albero. In sostanza devo fare un esercizio in cui mi si chiede di calcolare il peso di un nodo dato, indicando che il peso è la somma del valore del nodo dato e di tutti i nodi del sottoalbero dello stesso nodo. Ora il mio problema è che la funzione da me scritta restituisce sempre -1 e non riesco a capire perché non riesce a sommare le varie chiavi contenute nei nodi. Vi lascio il codice sperando possiate aiutarmi.

#include <iostream>
#include <fstream>

using namespace std;

template <class T>
class Nodo {
    T key;
    Nodo<T> *padre, *sx, *dx;
public:
    Nodo() {
        key = 0;
        padre = sx = dx = NULL;
    }
    void setKey(T key) { key = key;}
    void setPadre(Nodo<T>* p) {padre = p;}
    void setSx(Nodo<T>* s) {sx = s;}
    void setDx(Nodo<T>* d) {dx = d;}
    T getKey() {return key;}
    Nodo<T>* getPadre() {return padre;}
    Nodo<T>* getSx() {return sx;}
    Nodo<T>* getDx() {return dx;}
};

template <class T>
class BST {
private:
    Nodo<T>* root; //puntatore al nodo radice
    
    int n; //numero di nodi dell'albero
    
    Nodo<T>* _ricerca(T key, Nodo<T>* x) {
        //funzione ausiliaria per la ricerca di un nodo
        Nodo<T>* tmp = x;
        while (tmp != NULL && tmp->getKey() != key) {
            if (key < tmp->getKey())
                tmp = tmp->getSx();
            else
                tmp = tmp->getDx();
        }
        return tmp;
    }
    
    T _peso(Nodo<T>* x) {
        //funzione ricorsiva ausiliaria per calcolare il peso
        if (x) {
            return x->getKey()+_peso(x->getSx())+_peso(x->getDx());
        }
        return -1;
    }
    
public:
    BST() {
        root = NULL;
        n = 0;
    }
    
    BST<T>& ins (T key) {
        //funzione di inserimento di un valore nell'albero
        Nodo<T>* tmp = root;
        Nodo<T>* padre = NULL;
        Nodo<T>* x = new Nodo<T>();
        n++;
        while (tmp != NULL) {
            padre = tmp;
            if (key <= tmp->getKey())
                tmp = tmp->getSx();
            else
                tmp = tmp->getDx();
        }
        if (padre == NULL) {
            root = x;
            return *this;
        }
        if (key <= padre->getKey())
            padre->setSx(x);
        else
            padre->setDx(x);
        x->setPadre(padre);
        return *this;
    }
    
    T peso(T key) {
        //funzione per far restituire il peso
        Nodo<T>* tmp = _ricerca(key, root);
        if (tmp) {
            return _peso(tmp);
        }
        return -1;
    }
};

int main() {
    BST<int> *t = new BST<int>();
    t->ins(100).ins(40).ins(120).ins(70).ins(150);
    cout << t->peso(40) << endl;
    delete t;
    return 0;
}

 

[BAT]

Prova a cambiare l'istruzione interna di
void setKey(T key) { key = key;} // il nome del parametro secondo me maschera il nome dell'attributo key
in
this.key=key; ERRATO: VEDERE COMMENTO AL POST SUCCESSIVO
mi viene il forte dubbio che altrimenti non venga impostato il peso del nodo (in alternativa cambia il nome del tipo/parametro passato in T k e assegna key=k). IDEM: PROBABILE SINTASSI SCORRETTA

 

[_Achille]

Prova a cambiare l'istruzione interna di
void setKey(T key) { key = key;} // il nome del parametro secondo me maschera il nome dell'attributo key
in
this.key=key;
mi viene il forte dubbio che altrimenti non venga impostato il peso del nodo (in alternativa cambia il nome del tipo/parametro passato in T k e assegna key=k).

this->key = key ;)
In C++ this è un puntatore.

Ma che senso ha avere t come BST<int> *? Va bene pure se non puntatore ed eviti cose come t->ins(100).ins(40).ins(120)… che non è proprio il massimo con l’operatore -> all’inizio.

 

[xjokerx]

this->key = key ;)
In C++ this è un puntatore.

Ma che senso ha avere t come BST<int> *? Va bene pure se non puntatore ed eviti cose come t->ins(100).ins(40).ins(120)… che non è proprio il massimo con l’operatore -> all’inizio.

Prova a cambiare l'istruzione interna di
void setKey(T key) { key = key;} // il nome del parametro secondo me maschera il nome dell'attributo key
in
this.key=key;
mi viene il forte dubbio che altrimenti non venga impostato il peso del nodo (in alternativa cambia il nome del tipo/parametro passato in T k e assegna key=k).

Buonasera, grazie per le risposte, vi spiego perché l'uso dei template: in realtà l'esercizio non chiede solo int ma anche double quindi la classe deve adattarsi al tipo di dato che le viene fornito; postare l'intero esercizio sarebbe risultato troppo lungo, inoltre questo è codice scritto per testare il metodo per il peso, quello dell'esercizio comprende anche altri metodi implementati che vanno. Ho comunque provato a cambiare la funzione setKey aggiungendo il this e a cambiare il parametro passato al setKey ma continua a restituirmi -1 invece del valore del nodo..

 

[BAT]

nota che io ho scritto this.key ma l'ho fatto "alla Java" perché il C++ non l'ho mai studiato: quando all'università facemmo programmazione ad oggetti andammo direttamente su Java. La sintassi corretta è quella che ti ha suggerito @_Achille, non quella che ho scritto io.
Seconda cosa: il peso di un albero vuoto è zero: se interpreto correttamente il tuo codice, quando trovi un puntatore nullo (albero vuoto) fai ritornare -1. Quindi, sempre se la mia interpretazione è corretta, non otterrai mai un peso corretto (invece di return -1 prova invece con return 0 ).

 

[fabio93]

Nel metodo ins() non dovresti chiamare x->setKey(key); per avvalorare il nodo x?
E anche come dice @BAT00cent:

Quindi, sempre se la mia interpretazione è corretta, non otterrai mai un peso corretto (invece di return -1 prova invece con return 0 ).

il metodo peso() deve restituire 0 in caso di fallimento della ricerca.

 

[xjokerx]

Grazie ancora delle risposte! In effetti l’errore sembra essere nell’inserimento, provando una visita inorder andava in segmentation fault e cambiando il metodo di inserimento effettivamente funziona. Grazie a tutti!


Inviato dal mio iPhone utilizzando Toms Hardware Italia Forum