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

xjokerx

Utente Attivo
161
8
CPU
Intel Core I5-3570k 3.40Ghz + Hyper 412s
Scheda Madre
Asrock Z77 Extreme 4
HDD
WD Black 1 TB 7200rpm
RAM
Kingston 8 Gb 1600
GPU
Sapphire r9 280 3gb
Audio
Integrato
PSU
Corsair CX600M
Case
Cooler Master HAF 912 Plus
OS
Windows 7 ultimate 64-bit
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.
C++:
#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

Moderatore
Staff Forum
Utente Èlite
22,660
11,441
CPU
1-Neurone
Dissipatore
Ventaglio
RAM
Scarsa
Net
Segnali di fumo
OS
Windows 10000 BUG
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
 
Ultima modifica:

_Achille

Utente Èlite
3,067
725
CPU
Intel i5-6600K @4.6 GHz
Dissipatore
Cryorig H5
Scheda Madre
ASRock Z170 Extreme 6
HDD
WesternDigital 1TB & Crucial MX200 250GB
RAM
Corsair Ven 16GB DDR4 2133MHz
GPU
Sapphire RX 580 Nitro+
Monitor
Dell S2418H
PSU
RM550X
Case
NZXT S340
Periferiche
Anne Pro 2, Razer Abyssus
OS
Windows 10 Pro
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.
 
Ultima modifica:

xjokerx

Utente Attivo
161
8
CPU
Intel Core I5-3570k 3.40Ghz + Hyper 412s
Scheda Madre
Asrock Z77 Extreme 4
HDD
WD Black 1 TB 7200rpm
RAM
Kingston 8 Gb 1600
GPU
Sapphire r9 280 3gb
Audio
Integrato
PSU
Corsair CX600M
Case
Cooler Master HAF 912 Plus
OS
Windows 7 ultimate 64-bit
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

Moderatore
Staff Forum
Utente Èlite
22,660
11,441
CPU
1-Neurone
Dissipatore
Ventaglio
RAM
Scarsa
Net
Segnali di fumo
OS
Windows 10000 BUG
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

Utente Attivo
609
173
CPU
AMD Ryzen 5 2400G
Dissipatore
Arctic Alpine64 Plus
Scheda Madre
Gigabyte GA-AX370-Gaming 3
HDD
Crucial MX500 250 GB, Crucial BX500 240 GB
RAM
G.Skill F4-3200C14D-16GFX FlareX 16 GB
Monitor
HP 2010i
PSU
Corsair TX550M
Case
Sharkoon M25-W
Periferiche
Magicforce 68, Logitech G203
OS
Windows 10 Pro, Fedora 31
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.
 
Ultima modifica:

xjokerx

Utente Attivo
161
8
CPU
Intel Core I5-3570k 3.40Ghz + Hyper 412s
Scheda Madre
Asrock Z77 Extreme 4
HDD
WD Black 1 TB 7200rpm
RAM
Kingston 8 Gb 1600
GPU
Sapphire r9 280 3gb
Audio
Integrato
PSU
Corsair CX600M
Case
Cooler Master HAF 912 Plus
OS
Windows 7 ultimate 64-bit
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
 

Ci sono discussioni simili a riguardo, dai un'occhiata!

Entra

oppure Accedi utilizzando
Discord Ufficiale Entra ora!

Discussioni Simili