Arbre binaire de recherche

Soyez le premier à donner votre avis sur cette source.

Vue 25 499 fois - Téléchargée 3 038 fois

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.

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;
        }
    }
    
}

Codes Sources

A voir également

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.