Le nombre de feuilles d'un arbre se calcule récursivement par :

1 si c'est une feuille, sinon feuilles(gauche) + feuilles(droit)

Où est inséré un nouvel élément dans un ABR ?

Toujours comme une feuille. L'insertion dans un ABR descend comme une recherche et crée un nouveau nœud à l'emplacement vide trouvé. Le nouvel élément est toujours une feuille.

Pour l'arbre ABR : racine 10, fils gauche 5, fils droit 15. Le parcours préfixe donne :

10, 5, 15. Le parcours préfixe visite la racine d'abord (10), puis le sous-arbre gauche (5), puis le sous-arbre droit (15) : 10, 5, 15.

Quelle est la complexité temporelle des parcours d'un arbre de n nœuds ?

O(n). Tous les parcours (préfixe, infixe, suffixe, largeur) visitent chaque nœud exactement une fois, soit une complexité O(n).

Si on utilise une pile au lieu d'une file dans le parcours en largeur, on obtient :

Un parcours en profondeur. Remplacer la file (FIFO) par une pile (LIFO) transforme le parcours en largeur en un parcours en profondeur (DFS).

Le nombre de feuilles d'un arbre se calcule récursivement par :

1 si c'est une feuille, sinon feuilles(gauche) + feuilles(droit). Si le nœud n'a pas de fils, c'est une feuille (retourner 1). Sinon, le nombre de feuilles est la somme des feuilles du sous-arbre gauche et du sous-arbre droit.

La recherche dans un ABR est analogue à :

Une recherche dichotomique. Comme la recherche dichotomique dans un tableau trié, la recherche dans un ABR élimine la moitié des candidats à chaque comparaison (si l'arbre est équilibré).

NSI (Spé) — Algorithmique

Algorithmes sur les arbres

Q: Dans quel ordre le parcours infixe visite-t-il les nœuds ?

Gauche, racine, droit. Le parcours infixe visite d'abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Dans un ABR, cela donne les valeurs en ordre croissant.

Q: Quelle structure de données utilise le parcours en largeur ?

Une file. Le parcours en largeur (BFS) utilise une file (FIFO) pour traiter les nœuds niveau par niveau.

Q: Quelle est la complexité de la recherche dans un ABR équilibré de n nœuds ?

O(log n). Dans un ABR équilibré, la hauteur est O(log n), et la recherche descend d'un niveau à chaque comparaison, soit O(log n) au total.

Q: Le parcours suffixe (postordre) visite les nœuds dans l'ordre :

Gauche, droit, racine. Le parcours suffixe visite d'abord le sous-arbre gauche, puis le sous-arbre droit, et enfin la racine. Il est utile pour évaluer des expressions arithmétiques en notation postfixée.

Parcours d'arbres (préfixe, infixe, suffixe, largeur), insertion et recherche dans un ABR

Résumé synthétiqueFiche en 5 sectionsQuiz de 10 questionsGratuit, sans pub

Résumé

Les algorithmes sur les arbres sont principalement récursifs. Les trois parcours en profondeur d'un arbre binaire sont : préfixe (racine, gauche, droit), infixe (gauche, racine, droit) et suffixe (gauche, droit, racine). Par exemple, pour l'arbre de racine A avec fils B (gauche) et C (droit), le parcours préfixe donne A-B-C, l'infixe B-A-C et le suffixe B-C-A. Le parcours en largeur (BFS) visite les nœuds niveau par niveau en utilisant une file. Dans un ABR, la recherche compare la valeur cherchée à la racine et descend à gauche ou à droite : c'est une dichotomie sur l'arbre. L'insertion dans un ABR descend jusqu'à trouver un emplacement vide (None) et y crée un nouveau nœud. La complexité de ces opérations est O(h) où h est la hauteur de l'arbre, soit O(log n) pour un arbre équilibré.

Thème complet

Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale

Ce thème dans une autre classe

Seconde — Mathématiques

Algorithmique et programmation

Première — Mathématiques

Algorithmique et programmation Python

Première — Maths (Spé)

Algorithmique et programmation Python

Articles utiles

Spécialités

Bac NSI 2026 : comment réussir l'épreuve écrite et pratique

Questions fréquentes

Les points clés à retenir sur Algorithmes sur les arbres, extraits du quiz de révision.

Dans quel ordre le parcours infixe visite-t-il les nœuds ?

Réponse : Gauche, racine, droit

Le parcours infixe visite d'abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Dans un ABR, cela donne les valeurs en ordre croissant.

Quelle structure de données utilise le parcours en largeur ?

Réponse : Une file

Le parcours en largeur (BFS) utilise une file (FIFO) pour traiter les nœuds niveau par niveau.

Quelle est la complexité de la recherche dans un ABR équilibré de n nœuds ?

Réponse : O(log n)

Dans un ABR équilibré, la hauteur est O(log n), et la recherche descend d'un niveau à chaque comparaison, soit O(log n) au total.

Le parcours suffixe (postordre) visite les nœuds dans l'ordre :

Réponse : Gauche, droit, racine

Le parcours suffixe visite d'abord le sous-arbre gauche, puis le sous-arbre droit, et enfin la racine. Il est utile pour évaluer des expressions arithmétiques en notation postfixée.

Résumé

Questions fréquentes

Les points clés à retenir sur Algorithmes sur les arbres, extraits du quiz de révision.

Dans quel ordre le parcours infixe visite-t-il les nœuds ?

Réponse : Gauche, racine, droit

Le parcours infixe visite d'abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Dans un ABR, cela donne les valeurs en ordre croissant.

Quelle structure de données utilise le parcours en largeur ?

Réponse : Une file

Le parcours en largeur (BFS) utilise une file (FIFO) pour traiter les nœuds niveau par niveau.

Quelle est la complexité de la recherche dans un ABR équilibré de n nœuds ?

Réponse : O(log n)

Dans un ABR équilibré, la hauteur est O(log n), et la recherche descend d'un niveau à chaque comparaison, soit O(log n) au total.

Le parcours suffixe (postordre) visite les nœuds dans l'ordre :

Réponse : Gauche, droit, racine

Le parcours suffixe visite d'abord le sous-arbre gauche, puis le sous-arbre droit, et enfin la racine. Il est utile pour évaluer des expressions arithmétiques en notation postfixée.

Algorithmes sur les arbres

Résumé

Parcours en profondeur (DFS)

Parcours en largeur (BFS)

Recherche dans un ABR

Insertion dans un ABR

Calculs récursifs sur les arbres

Quiz - Algorithmes sur les arbres

Ce thème dans une autre classe

Articles utiles

Questions fréquentes

Algorithmes sur les arbres

Résumé

Parcours en profondeur (DFS)

Parcours en largeur (BFS)

Recherche dans un ABR

Insertion dans un ABR

Calculs récursifs sur les arbres

Quiz - Algorithmes sur les arbres

Ce thème dans une autre classe

Articles utiles

Questions fréquentes