Ci-dessous, les différences entre deux révisions de la page.
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:33] 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:==== | ====-Calculer la hauteur d'un arbre:==== | ||
+ | {{ : | ||
La hauteur de l' | La hauteur de l' | ||
Ligne 13: | Ligne 14: | ||
La hauteur de l' | La hauteur de l' | ||
====-Calculer la taille d'un arbre:==== | ====-Calculer la taille d'un arbre:==== | ||
+ | {{ : | ||
Calculer la taille d'un arbre permet de compter le nombre de nœud que possède l' | Calculer la taille d'un arbre permet de compter le nombre de nœud que possède l' | ||
La taille de l' | La taille de l' | ||
====-Parcourir un arbre dans l' | ====-Parcourir un arbre dans l' | ||
- | Parcourir un arbre dans l' | + | {{ : |
+ | Parcourir un arbre dans l' | ||
- | Pour l' | + | Pour l' |
+ | |||
+ | ====-Parcourir un arbre dans l' | ||
+ | {{ : | ||
+ | Parcourir un arbre dans l' | ||
+ | Pour l' | ||
+ | |||
+ | ====-Parcourir un arbre dans l' | ||
+ | {{ : | ||
+ | Parcourir un arbre dans l' | ||
+ | Pour l' | ||
+ | =====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' | ||
+ | * 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é | ||
+ | {{ : | ||
+ | On peut appliquer le même résonnement quand la partie '' | ||
+ | * La hauteur de ce graphe est de 5. | ||
+ | * La taille de ce graphe est de 11. | ||
+ | * Parcourir dans l' | ||
+ | * Parcourir dans l' |