Propriétés (Bac 🎯)⚓︎
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
Sources et crédits pour ce cours
Pour préparer ce cours, j'ai utilisé :
- le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
- le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
- l'article sur les arbres en NSI de Sébastien Hoarau
- le cours de mon collègue Pierre Duclosson
- les cours de Gilles Lassus et de Franck Chambon
🔖 Synthèse de ce qu'il faut retenir pour le bac
Maximum et minimum⚓︎
Point de cours 2 : maximum ou minimum dans un arbre binaire de recherche
Soit un arbre binaire vérifiant la propriété d'arbre binaire de recherche.
- Minimum : Pour déterminer le minimum des éléments stockés dans les noeuds de l'arbre il faut et il suffit de partir du noeud racine et de toujours descendre dans le fils/sous-arbre gauche tant que celui-ci est non vide. Le minimum est alors l'élément stocké dans le premier noeud atteint dont le fils/sous-arbre gauche est vide.
- Maximum : Pour déterminer le maximum des éléments stockés dans les noeuds de l'arbre il faut et il suffit de partir du noeud racine et de toujours descendre dans le fils/sous-arbe droit tant que celui-ci est non vide. Le maximum est alors l'élément stocké dans le premier noeud atteint dont le fils/sous-arbre droit est vide.
Exercice 2
Déterminez le maximum et le minimum des éléments stockés dans l'arbre binaire de recherche ci-dessous :
En appliquant les algorithmes décrits dans le point de cours 2:
- le minimum des éléments stockés dans l'arbre est
'DLY' - le maximum des éléments stockés dans l'arbre st
'ZQF'
Parcours infixe⚓︎
Point de cours 3 : parcours infixe d'un arbre binaire de recherche
Le parcours infixe d'un arbre binaire vérifiant la propriété d'arbre binaire de recherche donne une énumération dans l'ordre croissant des éléments stockés dans les noeuds.
Exercice 3
Énumérez dans l'ordre du parcours infixe les éléments stockés dans les noeuds de l'arbre binaire de recherche de l'exercice 2.
En énumérant les élément dans l'ordre du parcours infixe, on obtient les éléments dans l'ordre croissant :
'DLY' - 'FFO' - 'KME' - 'QLT' - 'THG' - 'TSA' - 'YXT' - 'ZQF'