Arbre binaire de recherche
Description
J'ai remarqué que codée un arbre binaire de recherche n'est pas évident et encore moin la suppression d'un noeud et l'affichage sous forme d'un arbre.
Voici ma source, dont je ne suis pas sûr à 100%. Donc si vous avez des remarques, merci d'avance.
Voici ma source, dont je ne suis pas sûr à 100%. Donc si vous avez des remarques, merci d'avance.
Source / Exemple :
void Noeud::supprime(int nb)
{
// noeud->etiquette() == noeud->v
Noeud *tmp;
Noeud *pere_tmp;
if( nb < etiquette() )
if( fg->noeud_vide() ){
cerr<<endl<<"n.suppresssion: "<<nb;
cerr<<" n'appartient pas a l'arbre"<<endl;
}
else{
if( nb == fg->etiquette() )
if( (fg->fg)->noeud_vide()&& (fg->fd)->noeud_vide() ){
delete fg;
fg = VIDE;
}
else // fg a au moin un descendant :
if( (fg->fg)->noeud_vide() ){
tmp = fg;
fg = fg->fd;
delete tmp;
}
else // fg->fg existe :
if( (fg->fd)->noeud_vide() ){
tmp = fg;
fg = fg->fd;
delete tmp;
}
else{ // fg a exactement 2 descendants :
tmp = fg->fg;
pere_tmp = fg;
// tmp == max dans fg->fg
while(tmp->fd != VIDE){
pere_tmp = tmp;
tmp = tmp->fd;
}
if( tmp == fg->fg){
fg->v = (fg->fg)->v;
fg->fg = (fg->fg)->fg;
delete tmp;
}
else{
fg->v = tmp->v;
pere_tmp->fd = tmp->fg;
delete tmp;
}
}
else
fg->supprime(nb);
}
else // nb > v (égalité impossible par hypothèse)
if( fd->noeud_vide() ){
cerr<<endl<<"n.suppresssion: "<<nb;
cerr<<" n'apprtient pas a l'arbre binaire"<<endl;
}
else{
if( nb == fd->etiquette() )
if( (fd->fg)->noeud_vide() && (fd->fd)->noeud_vide() ){
delete fd;
fd = VIDE;
}
else // fd a au moin un descendant :
if( (fd->fg)->noeud_vide() ){
tmp = fd;
fd = fd->fd;
delete tmp;
}
else // fg->fg existe :
if( (fd->fd)->noeud_vide() ){
tmp = fd;
fd = fd->fg;
delete tmp;
}
else{ // fd a exactement 2 descendants :
tmp = fd->fg;
pere_tmp = fd;
// tmp == max dans fg->fg
while( tmp->fd != VIDE ){
pere_tmp = tmp;
tmp = tmp->fd;
}
if( tmp == fd->fg){
fd->v = (fd->fg)->v;
fd->fg = (fd->fg)->fg;
delete tmp;
}
else{
fd->v = tmp->v;
pere_tmp->fd = tmp->fg;
delete tmp;
}
}
else
fd->supprime(nb);
}
}
void Noeud::affiche_sous_arbre()
{
int h = hauteur()-1, i, j;
int *t = new int[h+1]; for(i=0; i<h; i++) t[i] = 1;
t[h] = 0; // sécurité pour éviter de sortir du tableau.
Noeud *tmp;
i = h-1;
bool test = true;
while( i >= 0 ){
tmp = recherche(t, h);
// affichage du noeud :
if( test && !tmp->noeud_vide() ){
for(j=0; t[j] == -1 || t[j] == 1; j++){
if( t[j+1] == 0 || j == h-1)
if( t[j] == -1 )
printf(" %c", 192);
else
printf(" %c", 218);
else
if( t[j]*t[j+1] == -1)
printf(" %c", 179);
else
printf(" ");
}
printf("%6d", tmp->etiquette());
if( tmp->fg != VIDE && tmp->fd != VIDE)
printf(" %c%c", 196, 180);
else
if( tmp->fg != VIDE )
printf(" %c%c", 196, 191);
else
if( tmp->fd != VIDE )
printf(" %c%c", 196, 217);
cout<<endl;
}
// noeud suivant :
switch(t[i]){
case 1:
t[i] = 0;
test = true;
break;
case 0:
t[i] = -1;
for(j=i+1; j<h; j++) t[j] = 1;
i = h-1;
test = true;
break;
case -1:
i--;
test = false;
break;
default:
cerr<<" ? "<<endl;
}
}
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.