Exercices corrigés pour apprendre l'algorithmique

1
2
3
4
5
6
7
fonction hauteur ( T : arbre ) renvoie un entier 
  
        si T est vide 
                renvoyer 0 
        sinon 
                renvoyer 1 + max (hauteur ( FilsGauche(T)) , hauteur(FilsDroit(T) ) 
        fin si

1
2
3
4
5
6
7
unsigned Height (tree T)  
{  
        if ( IsEmpty(T) )  
                return 0;  
        else  
                return 1 + max( Height(Left(T) ), Height(Right(T) ) );  
}

1
2
3
4
unsigned max(unsigned a,unsigned b) 
{ 
	return (a>b)? a : b ; 
}

1
2
3
4
5
6
7
fonction NombreNœud( T : arbre ) renvoie un entier
 
        si ( EstVide( T ) )
                renvoyer 0;
        sinon
                renvoyer 1 + NombreNœud(FilsGauche(T)) + NombreNœud(FilsDroit(T));
        fin si

1
2
3
4
5
6
7
8
9
fonction NombreFeuilles ( T : arbre ) renvoie un entier 
  
        si T est vide alors 
                renvoyer 0; 
        sinon si T est une feuille alors  
                renvoyer 1 
        sinon 
                renvoyer NombreFeuilles( FilsGauche(T) ) + NombreFeuilles( FilsDroit(T) ); 
        fin si

1
2
3
4
5
6
7
8
9
unsigned NbLeaves( tree T)  
{  
        if( IsEmpty(T) )  
                return 0;  
        else if ( IsLeaf(T) )  
                return 1;  
        else  
                return NbLeaves(Left(T)) + NbLeaves(Right(T));  
}

1
2
3
4
5
6
7
8
9
10
 
fonction NombreNoeudsInternes(T : arbre ) renvoie un entier 
  
        si EstVide(T) alors 
                renvoyer 0 
        sinon si EstUneFeuille(T) alors 
                renvoyer 0 
        sinon  
                renvoyer 1 + NombreNoeudsInternes(FilsGauche(T)) + 
                                NombreNoeudsInternes(FilsDroit(T));

1
2
3
4
5
6
7
8
9
unsigned NbInternalNodes(tree T)  
{  
        if (IsEmpty(T))  
                return 0;  
        else if(IsLeaf(T))  
                return 0;  
        else  
                return 1 + NbInternalNodes(Left(T)) + NbInternalNodes(Right(T));  
}

1
2
3
4
5
6
7
8
9
fonction CreerArbre(val : TElement, fg : arbre , fd : arbre ) renvoie un arbre 
  
        X <- Allouer un nœud en mémoire. 
  
        X.valeur <- val; 
        X.fils_gauche <- fg; 
        X.fils_droit <- fd; 
  
        renvoyer X;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  
tree Create(TElement val, tree ls, tree rs)  
{  
        tree res;  
  
        res = malloc(sizeof(*res));  
  
        if( res == NULL )  
        {  
                fprintf(stderr,"Impossible d'allouer le noeud");  
                return NULL;  
        }  
  
        res->value = val;  
        res->left = ls;  
        res->right = rs;  
  
        return res;  
}

1
2
3
4
5
6
7
8
 
procedure supprime( src : arbre ) 
  
        si non EstVide(src) alors 
                supprime(FilsGauche(src)); 
                supprime(FilsDroit(src)); 
                supprimeNoeud(src); 
        fin si

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  
void Erase(tree * src)  
{  
        tree ls = Left(*src);  
        tree rs = Right(*src);  
  
        if( ! IsEmpty(*src) )  
        {  
                Erase( &ls );  
                Erase( &rs );  
  
                free( *src );  
                *src = NULL;  
        }  
}