Newsgroup: it.comp.lang.c++
Titolo: Albero

 *CODE*
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->l != NULL) && (p->item != n) )
 {
   if(n > rad)
  {
   p = p->l;
  }
    else
    {
     p = p->r;
    }
  }
  return p->item;
}
 *CODE*
-- 
Kleidemos
C++ Programmer
kleidemo...@altervista.org
http://kleidemos.altervista.org/

Non mi va:(


#include "STree.hpp"


CTree::~CTree()
{
}

   *// 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


#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???
Tnk


 Cosi me li mette sempre su r..............come mai???
BASTA!!! :-P 
-- 
Luc

What??


La domanda??

cos' era quel BASTA??
Cmq perche va solo sui nodi R ???
tnk


 Cmq perche va solo sui nodi R ???
Non lo so non ho tempo per controllare tutto quel codice...
Mi dispiace, vedrai che qualcuno ti risponderà... intanto... chi cerca
trova...

 What??
Credo derivi dal fatto che 6 posts su 8 in questo thread sono tuoi e...
apparentemente spedisci codice e non dici nulla...
Ora finalmente una domanda (quella che solo sui nodi R)...
Vedro' di rispondere se mi viene voglia di leggermi il tuo codice... (e'
piu' facile invogliare a leggere spedendo solo il pezzo rilevante).
Tommy
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

STree(n, NULL, NULL);
cosa sono i tre parametri?
tree e' il puntatore alla radice vero?
rad e' il valore della radice vero?
Stree esattamente cosa e'?
Dati questi misteri spero di non aver scritto sciocchezze... tuttavia
non credo.
Spero questo ti sia di aiuto.


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
        std::cout << "Stato elemento => " << p->item << "\n";
      #endif
  }else if(n > rad) // SE è MAGGIORE VA A DESTRA
    {
     p = p->R();
     #ifdef DEBUG
        std::cout << "Stato elemento => " << p->item << "\n";
      #endif
    }
 }
  if(p->R() == NULL)
  {
   p->r = new STree(n, NULL, NULL);
     #ifdef DEBUG
     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
     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
    }
}
Questo è il medoto add()...........pero mi da sempre nodo interno su r e
esterno su l.
E che se l e r sono pieni nn so cosa fare :(


 Quello era Luc!!
ROTFL! 
-- 
Luc

  node p = tree;
L'unico modo per farlo e'... spiegarti le cose come ho fatto ora ed
aspettare il tuo nuovo algoritmo oppure mandarti io una versione
funzionante in pseudocodice.
Vedi tu...
Questo mio post e' molto lungo e spero non contenga troppi errori anche
perche' non ho voglia di rileggerlo... Scusa.


void CTree::add(int n)
{
 STree * p = tree;
 while( (p->L() != NULL) || (p->R() != NULL) )
 {
   // SE è MINORE VA A SINISTRA
  if(p->Item() >= radix)
  {
   p = p->L();
     #ifdef DEBUG
        std::cerr << "Stato elemento => " << p->item << "\n";
      #endif
  }else if(p->Item() > radix) // SE è MAGGIORE VA A DESTRA
    {
     p = p->R();
     #ifdef DEBUG
        std::cerr << "Stato elemento => " << p->item << "\n";
      #endif
    }
 }
  if(p->R() == NULL)
  {
   p->r = new STree(n, NULL, NULL);
     #ifdef DEBUG
     std::cerr << "Stato l =>" << ((p->L() == NULL) ? " NODO ESTERNO" : "
NODO INTERNO") << "\n";
        std::cerr << "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
     std::cerr << "Stato l =>" << ((p->L() == NULL) ? " NODO ESTERNO" : "
NODO INTERNO") << "\n";
        std::cerr << "Stato r =>" << ((p->R() == NULL) ? " NODO ESTERNO" : "
NODO INTERNO") << "\n";
     #endif
    }
}
Cosi mi da un errore :(

 perche' non ho voglia di rileggerlo... Scusa.
ragazzo, hai vinto il premio "Buon Samaritano 2004". Davvero.

 }
su questa parte gia' di avevo risposto ma .... a quanto pare non leggi (e
non rispondi):
<QUOTE>
Non devi guardare quale dei due sia null, come ti ho dimostrato
potrebbero esserlo tutti e due.
Devi invece guardare dove va messo!
</QUOTE>
per sapere come guardare dove va messo rileggiti il post precedente....
Continuo a spedirti pezzi di post vecchi in quanto prima di ripostare sul NG
dovresti provare a mettere in pratica tutto quello che ti si dice....
Concludo con il concetto iniziale di questo post:
Io la ti avevo appena scritto un messaggio di piu' di 500 parole, con
spiegati tutti i tuoi errori e con piu' o meno 5 domande...
Il tuo post in risposta e' di 5 parole!
Ti ricordo che sono io che sto facendo un favore a te a risponderti e non tu
a me. Quindi se io non valgo piu' di 5 parole allora cio' significa che
dalla prossima volta io non ti degnero' di piu' di 5 parole che in questo
caso sarebbero dovute essere:
"rileggi il post di prima"
Tommy

Ti ringrazio x l'aiuto che mi hai dato e mi scuso se nn ti ho risposto
subito e per i fuimi di codice che ho postato.
Tnk x i consigli :):)


> ROTFL!
E quando ce vo' ce vo' !!
ciao.

 Tnk x i consigli :):)
Se non sei ancora riuscito prova seguendo questo semplice algoritmo:
<PSEUDOCODE>
new_node = alloc node
new_node->item = n;
new_node->left = new_node->right = 0;
if root is not null
     prev = p = root
     while p is not null
          prev = p
          if n >= p->item then
                p = p->right
          else
                p = p->left
          endif
     endwhile
     if n >= prev->item then 
          prev->rigth = new_node
     else
          prev->left = new_node
     endif
else
     root = new_node
endif
</PSEUDOCODE>
Ovviamente ci sono altri modi, questo non e' affatto l'unico.
Ci sono altri modi per scrivere questo codice iterativo ed ovviamente
tanti modi per scriverlo ricorsivo (anches se in questo caso e' di gran
lunga da preferire una soluzione iterativa).
Ovvimente puoi assegnare new_node dentro il while ed evitare di avere
prev, ma ho pensato che cosi' ti sarebbe piu' facile...
... e poi evitare prev significa comunque mettere un altro controllo
dentro il while e quindi non e' che sia poi una soluzione migliore.
In pratica il codice in italiano funziona cosi':
<SPIEGAZIONE>
Alloca il nuovo nodo con ->item uguale ad n e i due puntatori a 0. Se ci
fosse un problema nell'allocazione ritorna subito dalla funziona, lancia
una eccezione, spegni il computer, fai quello che vuoi!
Se la radice punta a null (ovvero l'albero e' vuoto) allora fai puntare
il puntatore alla radice al nuovo nodo (ora l'albero e' di un solo nodo!
questo e' il primo inserimento!)
Se la radice non punta a null dobbiamo invece trovare dove mettere il
nodo.....
Fai puntare prev e p alla radice e poi usa p per scorrere l'albero e
prev per tenere il nodo dell'iterazione precedente.
Quando n (il valore da inserire) e' maggiore o uguale al valore del nodo
attuale (p->item) allora scorri l'albero a destra altrimenti a sinistra.
Quando esci dal while perche' p e' null prev conterra' il nodo su cui
attaccare il nostr new_node.
Ovviamente un altro test ti dira' se devi attaccarlo a prev->right o
prev->left.
</SPIEGAZIONE>
Spero ti sia di aiuto, ma ricorda, ti aiuteranno sempre in meno persone
se non fai vedere di sforzarti, di sforzarti a scrivere domande, a
postare solo il codice importante, ad evitare di postare parti inutili e
soprattutto a cercare di mettere in pratica tutti i suggerimenti che ti
si dicono invece di ignorarli.
Questo mi fa venire in mente quanto ti ho dato le correzioni di inglese
del tuo sito, te ne davo 10 e ne correggevi solo 1... te ne ripostavo 9
e ne correggevi un'altra... mah... poi mi sono stancato ed ho smesso!
La stessa cosa tende a capitare molto spesso in altre situazioni, come
questo thread sull'albero... Io le cose le noto, poi se perseverano
smetto di aiutare. Ho notato che molti sul NG (leggendo i commenti di
questo thread) hanno gia' smesso...


Ho risolto in questo modo:
void CTree::add(int n)
{
   STree * p;
    STree * prev;
    STree * news = new STree(n, NULL, NULL);
    if(tree != NULL)
     p = prev = tree;
    while(p != NULL)
    {
     prev = p;
     if(n >= p->Item())
     {
      p = p->l;
     }else
     {
      p = p->r;
     }
    }
    if(n >= prev->Item() )
    {
     prev->r = news;
    }else if( n < prev->Item() )
    {
     prev->l = news;
    }else
    {
      tree = news;
    }
}
Direi che ho preso una cantonata immensa e mi scuso per il tempo che ho
fatto perdere a tutti.
Scusatemi ancora
-- 
Kleidemos
kleidemo...@altervista.org
http://kleidemos.altervista.org/

 Scusatemi ancora
Ok....
Prima il codice era lontanissimo dal funzionare.
Ora ci sei vicino ma serve ancora qualche modifica. Riguarda i post
precedenti, riguarda il pseudocodice, rileggi questa mail. Cerca quindi di
capire i tuoi errori ed una volta capiti prova di rimediare. Ad ogni modo
con questo codice hai fatto un grande passo avanti.
Tommy

 precedenti, riguarda il pseudocodice, rileggi questa mail.
Lo faro.
Cmq ora ho capito, forse, dove sbagliavo.
Grazie a te cmq per la pazienza :)


 *CODE*
Questa č la mia versione (compilata con DEV C++):
#include <iostream>
#include <ctime>
#include <cstdlib>
typedef struct CTreeNode_t { int n;
                            struct CTreeNode_t* left;
                            struct CTreeNode_t* right;
        } CTreeNode, *PCTreeNode;
class CTree {
  private:
    PCTreeNode FRoot;
    void InternalDestroyCTree(PCTreeNode&);
    void InternalAdd(int, PCTreeNode&);
    void InternalShowInOrder(PCTreeNode);
  public:
    CTree() { FRoot = NULL; }
    virtual ~CTree() { InternalDestroyCTree(FRoot); }
    void Add(int n);
    void ShowInOrder();
};
void CTree::InternalAdd(int n, PCTreeNode& ARoot)
{
     if (ARoot == NULL)
     {
         ARoot = new CTreeNode;
         ARoot->n = n;
         ARoot->left = NULL;
         ARoot->right = NULL;
     }
     else
     if (n <= ARoot->n) InternalAdd(n, ARoot->left);
     else
     if (n > ARoot->n) InternalAdd(n, ARoot->right);
}
void CTree::Add(int n)
{
     InternalAdd(n, FRoot);
}
void CTree::InternalShowInOrder(PCTreeNode P)
{
     if (P->left) InternalShowInOrder(P->left);
     std::cout << P->n << ";";
     if (P->right) InternalShowInOrder(P->right);
}
void CTree::ShowInOrder()
{
     std::cout << "Items sorted: ";
     InternalShowInOrder(FRoot);
     std::cout << std::endl;
}
void CTree::InternalDestroyCTree(PCTreeNode& P)
{
     if (P->left) InternalDestroyCTree(P->left);
     if (P->right) InternalDestroyCTree(P->right);
     delete P;
     P = NULL;
}
int main(int argc, char *argv[])
{
    CTree Albero;
    int i;
    srand(time(NULL));
    printf("Numbers inserted: ");
    for (i = 0; i < 10; i++) {
        int n = rand() % 50;
        printf("%d;", n);
        Albero.Add(n);
    }
    printf("\n");
    Albero.ShowInOrder();
    system("PAUSE");
    return 0;
}


Tnk
