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:structure_des_donnees:arbres [2021/05/05 17:07] mc [Les arbres] |
les_fiches_revisions:structure_des_donnees:arbres [2023/01/18 16:13] (Version actuelle) lag [Les arbres] |
||
---|---|---|---|
Ligne 3: | Ligne 3: | ||
Les arbres sont des types abstraits permettant de structurer les données. | Les arbres sont des types abstraits permettant de structurer les données. | ||
- | Un arbre binaire un cas particulier | + | Les arbres binaires sont une forme plus précise |
{{ : | {{ : | ||
- | //__**Vocabulaire | + | //__**Quelques thermes sont à connaitre pour parler d' |
- | * //__nœud :__// chaque | + | * //__nœud :__// élément |
- | * // | + | * // |
- | * //__nœud fils :__// les nœuds D et E sont les fils du nœud B | + | * //__nœud fils :__// 1 ou 2 nœud(s) sous un autre nœud (ex : J et K sont les fils de F) |
- | * //__nœud père :__// le nœud B est le père des nœuds | + | * //__nœud père :__// nœuds au-dessus de nœuds |
* //__feuille :__// nœud n' | * //__feuille :__// nœud n' | ||
* //__arête :__// segment qui relie deux nœuds | * //__arête :__// segment qui relie deux nœuds | ||
* // | * // | ||
* //__hauteur d'un arbre :__// profondeur maximale de l' | * //__hauteur d'un arbre :__// profondeur maximale de l' | ||
- | * //__taille d'un arbre :__// nombre de nœuds composant l' | + | * //__taille d'un arbre :__// nombre de nœuds composant l' |
- | Dans un arbre binaire, chaque nœud possède au plus 2 fils (souvent appelés fils droit et fils gauche). | ||
- | Le sous-arbre d'un nœud est l' | + | Un arbre binaire ( ayant donc 1 ou 2 fils) aura forcément des sous-arbres , qui peuvent être comparés à des branches |
+ | Ici , le sous-arbre gauche de A est en rouge et le droit est est violet. | ||
+ | {{ : | ||
====Arbres binaires de recherche==== | ====Arbres binaires de recherche==== | ||
Un arbre binaire de recherche est un cas particulier d' | Un arbre binaire de recherche est un cas particulier d' |