[C++]Albero

[Luc@s]

struct STree
{
int item;
STree *l, *r;
STree(int Item, STree *L, STree *R)
{
item = Item;
l = L;
r = R;
}
};

typedef STree *node;

class CTree
{
private:
node tree;
int rad;
public:
CTree();
CTree(int n);
~CTree();
void add(int n);
int serch(int n);
};

CTree::CTree()
{
rad = 0;
tree = new STree(0, NULL, NULL);
}
// init tree
CTree::CTree(int n)
{
rad = n;
tree = new STree(n, NULL, NULL);
}

CTree::~CTree()
{
}

void CTree::add(int n)
{
node p = tree;
while( (p->l != NULL) && (p->r != NULL) )
{
if(n > rad)
{
p = p->l;
}
else
{
p = p->r;
}
}
if(p->l == NULL)
{
p->r->item = n;
}
else if(p->r == NULL)
{
p->l->item = n;
}
}

int CTree::serch(int n)
{
node p = tree;
while( (p->l != NULL) && (p->r != NULL) && (p->item != n) )
{
if(n > rad)
{
p = p->l;
}
else
{
p = p->r;
}
}
return p->item;
}



Dove sbaglio??



Tnk 100000000000

[Luc@s]

#include "STree.hpp"

class CTree
{
private:
node tree;
int rad;
public:
CTree();
CTree(int n);
~CTree();
void add(int n);
int serch(int n);
};

CTree::CTree()
{
rad = 0;
tree = new STree(0, NULL, NULL);
}
// init tree
CTree::CTree(int n)
{
rad = n;
tree = new STree(n, NULL, NULL);
}

CTree::~CTree()
{
}

void CTree::add(int n)
{
node p = tree;
while( (p->l != NULL) && (p->r != NULL) )
{
if(n > rad)
{
p = p->l;
}
else
{
p = p->r;
}
}
if(p->l == NULL)
{
// ERRORE QUI
p->r = new STree(n, NULL, NULL);
}
else if(p->r == NULL)
{
// QUI
p->l = new STree(n, NULL, NULL);
}
}

int CTree::serch(int n)
{
node p = tree;
while( (p->l != NULL) && (p->r != NULL) && (p->item != n) )
{
if(n > rad)
{
p = p->l;
}
else
{
p = p->r;
}
}
return p->item;
}



Risolto :)

[Luc@s]

#include "STree.hpp"
#define DEBUG

class CTree
{
private:
node tree;
int rad;
public:
CTree();
CTree(int n);
~CTree();
void add(int n);
int serch(int n);
};

CTree::CTree()
{
rad = 0;
tree = new STree(0, NULL, NULL);
}
// init tree
CTree::CTree(int n)
{
rad = n;
tree = new STree(n, NULL, NULL);
}

CTree::~CTree()
{
}

void CTree::add(int n)
{
node p = tree;
while( (p->l != NULL) && (p->r != NULL) )
{
// SE è MINORE VA A SINISTRA
if(n > rad)
{
p = p->l;
}
// SE è MAGGIORE VA A DESTRA
else if(n < rad)
{
p = p->r;
}
}
p->r = new STree(n, NULL, NULL);
#ifdef DEBUG
#include <iostream>
std::cout << "Stato elemento => " << p->item << "\n";
std::cout << "Stato l =>" << ((p->l == NULL) ? " NODO ESTERNO" : " NODO INTERNO") << "\n";
std::cout << "Stato r =>" << ((p->r == NULL) ? " NODO ESTERNO" : " NODO INTERNO") << "\n";
#endif
}
// NON VA
int CTree::serch(int n)
{
node p = tree;
while( (p->l != NULL) && (p->r != NULL) && (p->item != n) )
{
if(n > rad)
{
p = p->l;
}
else if(n < rad)
{
p = p->r;
}
#ifdef DEBUG
#include <iostream>
std::cout << "Siamo all ' elemento " << p->item << "\n";
#endif
}
return p->item;
}


Cosi me li mette sempre su r..............come mai???

[verloc]

per non saper ne leggere e ne scrivere
(2 secondi dedicati alla lettura perché non devi postare l'intera classe se vuoi che qualcuno ti aiuti)

e se è UGUALE? :)

[Luc@s]

Originariamente inviato da verloc
per non saper ne leggere e ne scrivere
(2 secondi dedicati alla lettura perché non devi postare l'intera classe se vuoi che qualcuno ti aiuti)

e se è UGUALE? :)

cominciamo a partire dal fatto che nn ci saranno duplicati :)

[verloc]

ammempar che come va va lo metti sempre in r

(mannaggie a capa tua!) :)

...

p->r = new STree(n, NULL, NULL);


ps.search non serch

[Luc@s]

//////////////////////////////////////////////
// CTree.hpp //
//////////////////////////////////////////////
#include "STree.hpp"

class CTree
{
private:
node tree;
int rad;
public:
CTree();
CTree(int n);
~CTree();
void add(int n);
int search(int n);
};

CTree::CTree()
{
rad = 0;
tree = new STree(0, NULL, NULL);
}
// init tree
CTree::CTree(int n)
{
rad = n;
tree = new STree(n, NULL, NULL);
}

CTree::~CTree()
{
}

void CTree::add(int n)
{
node p = tree;
while( (p->L() != NULL) && (p->R() != NULL) )
{
// SE è MINORE VA A SINISTRA
if(n < rad)
{
p = p->L();
#ifdef DEBUG
#include <iostream>
std::cout << "Stato elemento => " << p->item << "\n";
#endif
}else if(n > rad) // SE è MAGGIORE VA A DESTRA
{
p = p->R();
#ifdef DEBUG
#include <iostream>
std::cout << "Stato elemento => " << p->item << "\n";
#endif
}
}
if(p->R() == NULL)
{
p->r = new STree(n, NULL, NULL);
#ifdef DEBUG
#include <iostream>
std::cout << "Stato l =>" << ((p->L() == NULL) ? " NODO ESTERNO" : " NODO INTERNO") << "\n";
std::cout << "Stato r =>" << ((p->R() == NULL) ? " NODO ESTERNO" : " NODO INTERNO") << "\n";
#endif
}else if(p->L() == NULL)
{
p->l = new STree(n, NULL, NULL);
#ifdef DEBUG
#include <iostream>
std::cout << "Stato l =>" << ((p->L() == NULL) ? " NODO ESTERNO" : " NODO INTERNO") << "\n";
std::cout << "Stato r =>" << ((p->R() == NULL) ? " NODO ESTERNO" : " NODO INTERNO") << "\n";
#endif
}
}
// TODO:
// da Migliorare
int CTree::search(int n)
{
node p = tree;
while( (p->Empty() != true) && (p->item != n) )
{
if(n < rad)
{
p = p->L();
}
else if(n > rad)
{
p = p->R();
}
#ifdef DEBUG_C
#include <iostream>
std::cout << "Siamo all ' elemento " << p->Item() << "\n";
#endif
}
return (p->Item());
}



Cosi nn va lo stesso :muro: :muro:

[/\/\@®¢Ø]

Primo errore che ho notato:


CTree::CTree()
{
rad = 0;
tree = new STree(0, NULL, NULL);
}

CTree::CTree(int n)
{
rad = n;
tree = new STree(n, NULL, NULL);
}

con questo codice, che differenza c'e' tra un albero vuoto e uno che contiene solo lo zero ? O meglio: che differenza c'e' tra un albero costruito con

CTree x(0);

e uno costruito

CTree x;
x.add(0);

(a rigore dovrebbero essere uguali, o no ? ;) )

[/\/\@®¢Ø]

Seconda osservazione, di tipo stilistico:
Se vuoi che gli altri riescano a leggere il tuo codice
( e vuoi riuscirci tu dopo una settimana che l'hai scritto )
devi usare una certa coerenza nella stesura.
Se decici che le classi/strutture cominciano con le maiscole, fallo sempre, altrimenti poi uno si trova un node che non sa se e' un node classe (cioe' un Node) o un node istanza (cioe' node).
Cerca di tenere il codice strutturato in modo uniforme; un blocco di codice dovrebbe essere piu' indentato della funzione che lo contiene, spezzoni del tipo

if ( something )
{
while( something_else )
{
do_it(); }
}

non aiuta di certo.

Evita poi di cospargere il codice di #include, ancor piu' di includere venti volte la stessa intestazione.
Se ti serve una libreria aggiungi

#ifdef DEBUG
#include <iostream>
#endif

solo all'inizio invece che ogni volta, e invece di tanti #ifdef per il codice raccoglili in un punto solo, ad esempio in una funzione di debug


void debug( const string& s )
{
#ifdef DEBUG
cerr << string << endl;
#endif
}


Nel caso DEBUG non sia definito il compilatore sapra' eliminare completamente la chiamata.

[/\/\@®¢Ø]

dimenticavo: mescolare spazi e tabulazione e' come mescolare birra e vodka: divertente finche' si vuole ma i risultati poi sono nefasti.
Quindi sempre o l'uno o l'altro (vale sia per il C++ che per gli alcolici :D )


void CTree::add(int n)
{
while( (p->L() != NULL) && (p->R() != NULL) )
{
// blah
}
if(p->R() == NULL)
// blah
}
else if(p->L() == NULL)
{
// blah
}
}

domandone: che succede quando sia il figlio sinistro sia quello destro della radice sono presenti ? Dove viene inserito il nodo ?

[/\/\@®¢Ø]

Per il debug:

se vuoi scrivere in output qualcosa di piu' elaborato di una stringa puoi fare qualcosa di piu' evoluto:


class Debugger
{
public:
template <class T>
Debugger& operator << (const T& t )
{
#ifdef DEBUG
cerr << t;
#endif
return *this;
}
private:
std::ostream& out;
};


In questo modo puoi scrivere

d << "5+2=" << 5+2 << endl;

che verra' eseguito solo in caso di debug
(dovrebbe, non ho testato il codice, ma l'idea e'quella)

[Luc@s]

Originariamente inviato da /\/\@®¢Ø

domandone: che succede quando sia il figlio sinistro sia quello destro della radice sono presenti ? Dove viene inserito il nodo ?

Ottima domanda.
Non so pero la risposta:(

[verloc]

devi assicurarti di aver capito bene l'argomento,scrivere codice di getto porta a questo(non sapere cosa si sta facendo).

Aia studià ! :)

[/\/\@®¢Ø]

Originariamente inviato da Luc@s
Ottima domanda.
Non so pero la risposta:(
Vediamo: non puoi mettere il nuovo numero come figlio del nodo radice perche' il posto e' gia' occupato; pero' il figlio e' a sua volta e' un albero, e puoi quindi provare a inserire il nodo in quell'albero; procedi cosi' finche' non trovi uno spazio libero.
il tuo codice dovrebbe quindi somigliare a qualcosa del genere:


void CTree::add(Int n)
{
root = insert( root , n );
}

void CTree::insert( node r , int n )
{ // abbiamo spazio per un nuovo nodo
if ( r == 0 )
return new node(n,0,0);
// non c'e' spazio, riproviamo con i figli
if ( n <= r->rad )
r->l = insert( r->l , n );
else
r->r = insert( r->r , n );
}


Ti torna come funziona l'algoritmo ?
In ogni caso per argomenti come questo dovresti dotarti di una minima base teorica; consigliatissimo "Introduzione agli algoritmi" di Cormen,LEiserson.Rivest, una lettura non facile ma utilissima.

[cionci]

Originariamente inviato da /\/\@®¢Ø
e' come mescolare birra e vodka: divertente finche' si vuole ma i risultati poi sono nefasti.
Ah sì ?!?!?!? :doh: Ecco perchè ieri sera :Puke: :coffee:

Comunque Luc@s non ti scoraggiare...non era poi così male...e continua con gli esercizi sugli alberi binari ;)

[Luc@s]

Il tuo algo mi da errore /\/\@®¢Ø :(

[/\/\@®¢Ø]

Originariamente inviato da Luc@s
Il tuo algo mi da errore /\/\@®¢Ø :(
Ma come ho scritto il mio era un esempio di come puo' venire implementato, non l'ho provato col tuo codice; capire come funziona un algoritmo e riuscire ad implementarselo e' la cosa piu' importante, se vai avanti di copia/incolla tanto vale usare le librerie gia' pronte
(Si' avete ragione, e' pure un :mc: per il fatto che non funziona :D)

[verloc]

Marco sta tentando di farti capire la cosa fondamentale(e che doveva essere chiaro fin dall'inizio prima di scrivere codice):
che gli a.b nella loro implementazione classica sono


STRUTTURE RICORSIVE.

non abbiamo tenuto conto ancora che la classe ha bisogno di un distruttore dell'albero(dato che si allocano i nodi dinamicamente).


adesso facciamo prima così:
senò ci schiatt' a cap' :)

http://www.stickysauce.com/tutorials/programming/cplusplus/lesson18.htm

e come esercizio potresti aggiungere un metodo che stampi sul video l'albero ordinato.

Domandone secondo:e se invece di interi fossero double oppure CMele?
suggerimento:quando può dirsi che una mela è + grande di un'altra? ;)

[cionci]

Secondo me per fare quello che voelva fare Luc@s era più semplice un approccio di questo tipo:

class bin_tree {
bin_tree *sx;
bin_tree *dx;
int info;
bin_tree() { };
public:
bin_tree(int in):sx(NULL),dx(NULL),info(in) { };
int height();
bin_tree *add(int in);
bin_tree *search(int in)
};

int bin_tree::height()
{
if(sx && dx)
return 1+(sx->height() < dx->height()) ? sx->height() : dx->height();
return 0;
}

bin_tree *bin_tree::add(int in)
{
if(sx && dx)
{
return (sx->height() > dx->height())?dx->add(in):sx->add(in);
}
bin_tree *tmp = new bin_tree(in);
if(sx) dx = tmp;
else sx = tmp;
return tmp;
}

bin_tree *bin_tree::search(int in)
{
bin_tree *res = NULL;
if(info == in)
return this;
if(sx)
res = sx->search(in);
if(!res && dx)
res = dx->search(in);
return res;
}

Poi volendo si può inserire qualche interfaccia per visitare l'albero...