Exercices corrigés pour apprendre l'algorithmique, le club des développeurs et IT Pro [Link]
page=Arbres
FORUMS TUTORIELS FAQ BLOGS CHAT NEWSLETTER EMPLOI ÉTUDES DROIT CLUB
DI/DSI Solutions d'entreprise Cloud IA ALM Microsoft Java Dév. Web EDI Programmation SGBD Office Mobiles Systèmes
Programmation Algorithmique 2D-3D-Jeux Assembleur C C++ C# D Go Kotlin Objective C Pascal Perl Python Rust Swift
Qt XML Autres
ACCUEIL ALGO COURS ALGO FAQ ALGO FORUM ALGO EXERCICES ALGO LIVRES ALGO SOURCES ALGO
Architecte Applicatif H/F - CREDIT AGRICO LE ASSURANCES - Paris (75 001 )
Développeur Fullstack - LA BANQUE PO STALE - Toulouse (31000)
Tous les exercices Débuter - Algorithmique Exercices Exercices corrigés pour apprendre l'algorithmique
Exercices corrigés pour apprendre l'algorithmique
Nombre d'auteurs : 1 - Nombre d'exercices : 20 - Dernière mise à jour : 12 mai 2019
Rechercher
Une sélection des meilleurs exercices, accessibles aux débutants, avec des énoncés clairs et complets suivis de solutions détaillées.
Grâce à l'entraide bénévole, les membres du club répondent à vos questions directement sur le forum et vous aident lors de l'apprentissage du langage.
Commentez
Sommaire Structures de données Arbres
Calcul de la hauteur d'un arbre binaire
Calcul du nombre de nœuds d'un arbre binaire
Calcul du nombre feuilles d'un arbre binaire
Calcul du nombre de nœuds internes
Création d'un arbre
Suppression ou destruction complète d'un arbre
Algorithmes
Calcul de la hauteur d'un arbre binaire
Mis à jour le 4 juin 2018 par Malick
Objectif
Apprendre à calculer la hauteur d'un arbre.
Niveau de difficulté : débutant
Exercice
Calculer la hauteur d'un arbre en vous basant sur la définition récursive :
- un arbre vide est de hauteur 0 ;
- un arbre non vide a pour hauteur 1 + la hauteur maximale entre ses fils.
Auteur : Romuald Perrot
Source
Cacher cette solution
Pour ce faire, on partira du pseudo-code suivant :
Code : Sélectionner tout
1 fonction hauteur ( T : arbre ) renvoie un entier
2
3 si T est vide
4 renvoyer 0
5 sinon
6 renvoyer 1 + max (hauteur ( FilsGauche(T)) , hauteur(FilsDroit(T) )
7 fin si
Ce qui se traduit en langage C par :
Code c : Sélectionner tout
1 unsigned Height (tree T)
2 {
3 if ( IsEmpty(T) )
4 return 0;
5 else
6 return 1 + max( Height(Left(T) ), Height(Right(T) ) );
7 }
1 sur 6 17/04/2024, 13:17
Exercices corrigés pour apprendre l'algorithmique, le club des développeurs et IT Pro [Link]
La fonction max n'étant pas définie, nous le faisons maintenant :
Code c : Sélectionner tout
1 unsigned max(unsigned a,unsigned b)
2 {
3 return (a>b)? a : b ;
4 }
Calcul du nombre de nœuds d'un arbre binaire
Mis à jour le 5 juin 2018 par Malick
Objectif
Apprendre à calculer le nombre de nœuds d'un arbre.
Niveau de difficulté : débutant
Exercice
Calculer le nombre de nœuds en vous basant sur la définition récursive :
- si l'arbre est vide : renvoyer 0 ;
- sinon renvoyer 1 plus la somme du nombre de nœuds des sous-arbres.
Auteur : Romuald Perrot
Source
Cacher cette solution
Pour ce faire, on partira du pseudo-code suivant :
Code : Sélectionner tout
1 fonction NombreNœud( T : arbre ) renvoie un entier
2
3 si ( EstVide( T ) )
4 renvoyer 0;
5 sinon
6 renvoyer 1 + NombreNœud(FilsGauche(T)) + NombreNœud(FilsDroit(T));
7 fin si
Calcul du nombre feuilles d'un arbre binaire
Mis à jour le 12 juin 2018 par Malick
Objectif
Apprendre à calculer le nombre de feuille d'un arbre.
Niveau de difficulté : débutant
Exercice
Calculer le nombre de feuilles en vous basant sur la définition récursive :
un arbre vide n'a pas de feuille ;
un arbre non vide a son nombre de feuilles défini de la façon suivante :
si le nœud est une feuille, alors on renvoie 1,
si c'est un nœud interne, alors le nombre de feuilles est la somme du nombre de feuilles de chacun de ses fils.
Auteur : Romuald Perrot
Source
Cacher cette solution
Pour ce faire, on partira du pseudo-code suivant :
Code : Sélectionner tout
1 fonction NombreFeuilles ( T : arbre ) renvoie un entier
2
3 si T est vide alors
4 renvoyer 0;
5 sinon si T est une feuille alors
6 renvoyer 1
7 sinon
8 renvoyer NombreFeuilles( FilsGauche(T) ) + NombreFeuilles( FilsDroit(T) );
9 fin si
Ce qui nous donne en langage C :
Code c : Sélectionner tout
2 sur 6 17/04/2024, 13:17
Exercices corrigés pour apprendre l'algorithmique, le club des développeurs et IT Pro [Link]
1 unsigned NbLeaves( tree T)
2 {
3 if( IsEmpty(T) )
4 return 0;
5 else if ( IsLeaf(T) )
6 return 1;
7 else
8 return NbLeaves(Left(T)) + NbLeaves(Right(T));
9 }
Calcul du nombre de nœuds internes
Mis à jour le 12 juin 2018 par Malick
Objectif
Apprendre à calculer le nombre de nœuds internes.
Niveau de difficulté : débutant
Exercice
Calculer le nombre de nœuds internes en vous basant sur la définition récursive :
un arbre vide n'a pas de nœud interne.
si le nœud en cours n'a pas de fils alors renvoyer 0
si le nœud a au moins un fils, renvoyer 1 plus la somme des nœuds interne des sous-arbres.
Auteur : Romuald Perrot
Source
Cacher cette solution
On en déduit le pseudo-code correspondant :
Code : Sélectionner tout
1
2 fonction NombreNoeudsInternes(T : arbre ) renvoie un entier
3
4 si EstVide(T) alors
5 renvoyer 0
6 sinon si EstUneFeuille(T) alors
7 renvoyer 0
8 sinon
9 renvoyer 1 + NombreNoeudsInternes(FilsGauche(T)) +
10 NombreNoeudsInternes(FilsDroit(T));
Ce qui donne en langage C :
Code c : Sélectionner tout
1 unsigned NbInternalNodes(tree T)
2 {
3 if (IsEmpty(T))
4 return 0;
5 else if(IsLeaf(T))
6 return 0;
7 else
8 return 1 + NbInternalNodes(Left(T)) + NbInternalNodes(Right(T));
9 }
Création d'un arbre
Mis à jour le 13 juin 2018 par Malick
Objectif
Apprendre à créer un arbre, tant vide qu'à partir de deux sous-arbres.
Niveau de difficulté : débutant
Exercice
1. Créer un arbre vide.
2. Créer d'un arbre à partir d'un élément et de deux sous-arbres.
Auteur : Romuald Perrot
Source
Cacher cette solution
Créer un arbre vide.
Étant donné que nous avons défini un arbre comme étant un pointeur, un arbre vide est donc un pointeur null . La fonction de création d'un arbre vide est donc une
fonction qui nous renvoie la constante null .
Créer d'un arbre à partir d'un élément et de deux sous arbres.
Il faut tout d'abord créer un nœud ; ensuite, on place dans les fils gauche et droit les sous-arbres que l'on a passés en paramètre ainsi que la valeur associée au nœud.
Enfin, on renvoie ce nœud. En fait, ce n'est pas tout à fait exact, puisque ce n'est pas un nœud, mais un pointeur sur un nœud qu'il faut renvoyer. Nous utilisons cependant
3 sur 6 17/04/2024, 13:17
Exercices corrigés pour apprendre l'algorithmique, le club des développeurs et IT Pro [Link]
le terme nœud pour spécifier qu'il faut allouer un nœud en mémoire.
Voici le pseudo-code de la deuxième fonction :
Code : Sélectionner tout
1 fonction CreerArbre(val : TElement, fg : arbre , fd : arbre ) renvoie un arbre
2
3 X <- Allouer un nœud en mémoire.
4
5 [Link] <- val;
6 X.fils_gauche <- fg;
7 X.fils_droit <- fd;
8
9 renvoyer X;
Ce qui donnera en langage C :
Code c : Sélectionner tout
1
2 tree Create(TElement val, tree ls, tree rs)
3 {
4 tree res;
5
6 res = malloc(sizeof(*res));
7
8 if( res == NULL )
9 {
10 fprintf(stderr,"Impossible d'allouer le noeud");
11 return NULL;
12 }
13
14 res->value = val;
15 res->left = ls;
16 res->right = rs;
Notre fonction renvoie NULL s'il a été impossible d'allouer le nœud. Ceci est un choix arbitraire, vous pouvez très bien effectuer d'autres opérations à la place.
Suppression ou destruction complète d'un arbre
Mis à jour le 22 juin 2018 par Malick
Objectif
Apprendre comment supprimer ou détruire un arbre
Niveau de difficulté : débutant
Exercice
Créer un algorithme permettant de détruire complètement un arbre.
Auteur : Romuald Perrot
Source
Cacher cette solution
L'algorithme de suppression de l'arbre est simple : on supprime les feuilles une par une. On répète l'opération autant de fois qu'il y a de feuilles. Cette opération est donc
très dépendante du nombre de nœuds.
Cet algorithme est un simple parcours d'arbre. En effet, lorsque nous devrons traiter la racine, nous appellerons une fonction de suppression de la racine. Pour ce faire,
nous ne supprimerons que des feuilles avant de supprimer la racine, il faut supprimer les sous arbres gauche et droit. On en déduit donc que l'algorithme de suppression
est un parcours d'arbre postfixe.
Voici le pseudo code associé :
Code : Sélectionner tout
1
2 procedure supprime( src : arbre )
3
4 si non EstVide(src) alors
5 supprime(FilsGauche(src));
6 supprime(FilsDroit(src));
7 supprimeNoeud(src);
8 fin si
Le pseudo code est donc très simple. De la même manière, on en déduit le code en C :
Code c : Sélectionner tout
4 sur 6 17/04/2024, 13:17
Exercices corrigés pour apprendre l'algorithmique, le club des développeurs et IT Pro [Link]
1
2 void Erase(tree * src)
3 {
4 tree ls = Left(*src);
5 tree rs = Right(*src);
6
7 if( ! IsEmpty(*src) )
8 {
9 Erase( &ls );
10 Erase( &rs );
11
12 free( *src );
13 *src = NULL;
14 }
15 }
Algorithmes
Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre
intellectuelle protégée par les droits d'auteur. Copyright © 2024 Developpez Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même
partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous
encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.
Chef de projet Data Management H/F
36/4 4 Boule vard Va ugirard, 750 15 Paris
CREDIT AGRICO L E ASSURANCES
Développeur PHP / Angular
Tou louse
LA BANQ UE PO STALE
BEST OF DÉBUTER - ALGORITHMIQUE
Actualités les plus lues
Mois Année
Calcul formel en Python : les polynômes d'interpolation de Lagrange vus comme des vecteurs, un billet blog de Denis Hulo
Analyse combinatoire et Python : les combinaisons avec répétition, un billet blog de Denis Hulo
Communauté Algorithmique
Le forum Algorithmes et structures de données
Le forum Traitement d'images
Le forum Traitement du signal
Le forum Intelligence artificielle
Le forum Mathématiques
Les ressources Algorithmique
Cours et tutoriels Algorithmique
Les livres Algorithmique
Les sources Algorithmique
La FAQ Algorithmique
5 sur 6 17/04/2024, 13:17
Débuter en Algorithmique
Les cours pour débuter en Algorithmique
Connexion
Identifiant
Mot de passe
Je m e connec te !
S'inscrire Mot de passe oublié ?
J'apprends à programmer en Pascal Objet avec l'environnement de développement Lazarus
Contacter le responsable de la rubrique Algorithmique
Nous contacter Participez Hébergement Publicité / Advertising Informations légales Partenaire : Hébergement Web
© 2000-2024 - [Link]
