[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

[/\/\@®¢Ø]

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 )

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ì ?!?!?!? Ecco perchè ieri sera

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 per il fatto che non funziona )

[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...s/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...