ARBRE BINAIRE DE RECHERCHE

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