Différences

Ci-dessous, les différences entre deux révisions de la page.

--- 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
@@ Ligne 5: / Ligne 5: @@
 ----
+=====Arbre binaire=====
 ====-Calculer la hauteur d'un arbre:====
 {{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_1.png?250 |}}
@@ Ligne 20: / Ligne 20: @@
 ====-Parcourir un arbre dans l'ordre infixe:====
 {{ :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:====
 {{ :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.
-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:====
 {{ :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.
-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

Wiki NSI

Outils pour utilisateurs

Outils du site

Différences

Outils de la page