Les deux révisions précédentes
Révision précédente
Prochaine révision
|
Révision précédente
|
les_fiches_revisions:algorithmique:algo_arbres [2021/01/19 11:38] qt |
les_fiches_revisions:algorithmique:algo_arbres [2021/01/19 11:57] (Version actuelle) qt |
| |
---- | ---- |
| =====Arbre binaire===== |
====-Calculer la hauteur d'un arbre:==== | ====-Calculer la hauteur d'un arbre:==== |
{{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_1.png?250 |}} | {{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_1.png?250 |}} |
====-Parcourir un arbre dans l'ordre infixe:==== | ====-Parcourir un arbre dans l'ordre infixe:==== |
{{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_1.png?250 |}} | {{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_1.png?250 |}} |
Parcourir un arbre dans l'ordre infixe affichera l'arbre dans le sens inverse en donnant la feuille juste après sa branche. | Parcourir un arbre dans l'ordre infixe affichera l'arbre dans le sens inverse en donnant la feuille juste après son nœud. |
| |
Pour l'arbre ci-dessus, le programme parcourra dans l'ordre suivant: C, E, B, D, A, I, G, F, H, J | Pour l'arbre ci-dessus, le programme renverra: C, E, B, D, A, I, G, F, H, J |
| |
====-Parcourir un arbre dans l'ordre préfixe:==== | ====-Parcourir un arbre dans l'ordre préfixe:==== |
{{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_1.png?250 |}} | {{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_1.png?250 |}} |
Parcourir un arbre dans l'ordre préfixe affichera un nœud avant de visité c'est enfant. | Parcourir un arbre dans l'ordre préfixe affichera un nœud avant de visité c'est enfant. |
Pour l'arbre ci-dessus, le programme renverra dans l'ordre suivant: A, B, C, E, D, F, G, I, H, J | Pour l'arbre ci-dessus, le programme renverra : A, B, C, E, D, F, G, I, H, J |
| |
====-Parcourir un arbre dans l'ordre suffixe:==== | ====-Parcourir un arbre dans l'ordre suffixe:==== |
{{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_1.png?250 |}} | {{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_1.png?250 |}} |
Parcourir un arbre dans l'ordre suffixe affiche ses fils avant d'afficher les nœuds. | Parcourir un arbre dans l'ordre suffixe affiche ses fils avant d'afficher les nœuds. |
Pour l'arbre ci-dessus, le programme renverra dans l'ordre suivant: E, C, D, B, I, G, J, H, F, A | Pour l'arbre ci-dessus, le programme renverra : E, C, D, B, I, G, J, H, F, A |
| |
| =====Arbre binaire de recherche===== |
| Pour avoir un arbre binaire de recherche: |
| * il faut avoir un arbre binaire ! |
| * il faut que les clés de noeuds composant l'arbre soient ordonnables (on doit pouvoir classer les noeuds, par exemple, de la plus petite clé à la plus grande) |
| * soit x un noeud d'un arbre binaire de recherche. Si y est un noeud du sous-arbre gauche de x, alors il faut que y.clé ⩽ x.clé. Si y est un noeud du sous-arbre droit de x, il faut alors que x.clé ⩽ y.clé |
| {{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_4.png?400 |}} |
| |
| On peut appliquer le même résonnement quand la partie ''-Arbre binaire-'' vu ci-dessus |
| |
| * La hauteur de ce graphe est de 5. |
| * La taille de ce graphe est de 11. |
| * Parcourir dans l'ordre infixe : 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 |
| * Parcourir dans l'ordre préfixe : 15, 6, 18 , 3, 7, 17, 20 ,2 ,4 ,13 ,9 |