Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
----
====== Algorithmes sur les arbres binaires et sur les arbres binaires de recherche ======

Il est conseillé de lire le cours "[[les_fiches_revisions:structure_des_donnees:arbres|Les Arbres]]" pour approfondir la notion d'arbre binaire. 

----
=====Arbre binaire=====
====-Calculer la hauteur d'un arbre:====
{{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_1.png?250 |}}

La hauteur de l'arbre est le nombre de nœud qu'il y a dans la plus grande branche de l'arbre avec la feuille comprise.


La hauteur de l'arbre ci-dessus est de 4.
====-Calculer la taille d'un arbre:====
{{ :les_fiches_revisions:algorithmique:nsi_term_algo_arbre_1.png?250 |}}
Calculer la taille d'un arbre permet de compter le nombre de nœud que possède l'arbre. 

La taille de l'arbre ci-dessus est de 10.
====-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 son nœud.

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 : 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 : 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

Outils de la page
