ciao ragazzi c'e' un nuovo problema se inserisco dei caratteri uguali nei nodi non funziona
è CORRETTO se le lettere nei nodi sono tutte diverse
triplette da inserire:
a 0 0
b 0 a
c 1 a
d 1 b
e 1 c.
albero risultante:
a
/ \
b c
\ \
d e
è ERRATO se ci sono lettere uguale nei nodi
triplette da inserire:
a 0 0
a 0 a
a 1 a
inserisce i due successori del nodo radice "a" e se adesso faccio inserire un altro nodo "a" sotto al precedente, lui controlla solo la radice, vede che c'e' un nodo con campo "a" pieno in entrambi i lati e non me ne fa inserire altri. SI FERMA QUI
a 1 a
a 1 a.
io invece devo essere in grado di fare un albero anche di questo tipo! 
albero risultante:
a
/ \
a a
\ \
a a
Come posso fare io devo poter inserire anche lettere uguali nei nodi successori
codice:
#include <iostream>
/*
SPIEGAZIONE:
Per ogni inserimento si deve specificare una tripletta:
-l'informazione carattere da inserire;
-l'informazione 0 o 1 se è a sinistra o a destra del nodo padre;
-l'informazione carattere del nodo padre.
Per la radice dell'albero l'inserimento è a sinistra=0 e il nodo padre è 0.
Gli inserimenti terminano con il ".".
ESEMPIO:
triplette da inserire:
a 0 0
b 0 a
c 1 a
d 1 b
e 1 c.
albero risultante:
a
/ \
b c
\ \
d e
visita in ordine anticipato a b d c e
visita in ordine differito d b e c a
visita in ordine simmetrico b d a c e
*/
using namespace std;
class btree
{public:
enum side{L, R};
private:
struct elem
{ char inf;
elem* l; elem* r;
};
elem* root;
void deltree(elem* p);
bool ins(elem*p, char s, side sd, char finf);
void va(elem* p);
void vd(elem* p);
void vs(elem* p);
btree(const btree&);
btree& operator=(const btree&);
public:
btree();
~btree();
bool insert(char s, side sd, char finf);
void voa();
void vod();
void vos();
};
void btree::deltree(elem* p)
{ if (p!=0)
{ deltree(p->l); deltree(p->r);
delete p;
}
}
bool btree::insert(char s,side sd=L, char finf=0)
{ if (root==0)
{ root=new elem;
root->r=0; root->l=0; root->inf=s;
return true;
}
return ins(root, s, sd, finf);
}
bool btree::ins(elem*p, char s, side sd, char finf)
{ if (p==0) return false;
if (p->inf==finf)
{ switch (sd)
{ case L:
if (p->l==0)
{ p->l=new elem;
p->l->r=0; p->l->l=0;
p->l->inf=s; return true;
}
return false;
case R:
if (p->r==0)
{ p->r=new elem;
p->r->r=0; p->r->l=0;
p->r->inf=s; return true;
}
return false;
}
}
else if (ins(p->l,s,sd,finf)==true)
return true;
else if (ins(p->r,s,sd,finf)==true)
return true;
return false;
}
void btree::va(elem* p)
{ if (p!=0)
{ cout<<p->inf<<" ";
va(p->l);
va(p->r);
}
}
void btree::vd(elem* p)
{ if (p!=0)
{ vd(p->l);
vd(p->r);
cout<<p->inf<<" ";
}
}
void btree::vs(elem* p)
{ if (p!=0)
{ vs(p->l);
cout<<p->inf<<" ";
vs(p->r);
}
}
btree::btree()
{ root=0;}
btree::~btree()
{ deltree(root);}
void btree::voa()
{ va(root);}
void btree::vod()
{ vd(root);}
void btree::vos()
{ vs(root);}
int main()
{
char n1,n3,stop;
int n2;
char cc;
btree::side ss;
btree tt;
while ( 1 )
{
cin>>n1;
if( n1 == '.') break;
cin>>n2>>n3;
ss=(btree::side) n2;
if (tt.insert(n1,ss,n3))
cout<<"Inserimento effettuato\n";
else cout<<"Informazione "<< n3 << " non esistente \n" << " oppure lato occupato\n";
}
cout<<"Visita in ordine anticipato:\n";
tt.voa(); cout<< '\n';
cout<<"Visita in ordine differito:\n";
tt.vod(); cout<< '\n';
cout<<"Visita in ordine simmetrico:\n";
tt.vos(); cout<< '\n';
cin>>stop;
return 0;
}
RAGAZZI sono nella confusione piu' totale
Rispondi quotando
