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 10:59] qt |
les_fiches_revisions:algorithmique:algo_arbres [2021/01/19 11:57] (Version actuelle) qt |
||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
- | |||
---- | ---- | ||
====== Algorithmes sur les arbres binaires et sur les arbres binaires de recherche ====== | ====== Algorithmes sur les arbres binaires et sur les arbres binaires de recherche ====== | ||
Ligne 5: | Ligne 4: | ||
Il est conseillé de lire le cours " | Il est conseillé de lire le cours " | ||
- | + | ---- | |
+ | =====Arbre binaire===== | ||
====-Calculer la hauteur d'un arbre:==== | ====-Calculer la hauteur d'un arbre:==== | ||
+ | {{ : | ||
La hauteur de l' | La hauteur de l' | ||
- | {{ : | ||
- | La hauteur de cette arbre sera de 4. | + | |
+ | La hauteur de l'arbre ci-dessus est de 4. | ||
====-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' | ||
+ | ====-Parcourir un arbre dans l' | ||
+ | {{ : | ||
+ | Parcourir un arbre dans 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' |