======Les arbres======

Les arbres sont des types abstraits permettant de structurer les données.

Les arbres binaires sont une forme plus précise d'arbre où chacun des nœuds ne peut avoir que 2 fils maximums:

{{ :les_fiches_revisions:arbre.png?nolink&400 |{{:les_fiches_revisions:arbre.png?nolink&400 |{{ :les_fiches_revisions:arbre.png?nolink&400 |{{ :les_fiches_revisions:arbre.png?400 |{{:les_fiches_revisions:arbre.png?400|}}

//__**Quelques thermes sont à connaitre pour parler d'arbre :**__//
  * //__nœud :__// élément qui forme l'arbre (ex : A, B, …)
  * //__nœud racine :__// initiale départ de l'arbre (ici : A)
  * //__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 :__// nœuds au-dessus de nœuds fils (ex: F est le père de J et K)
  * //__feuille :__// nœud n'ayant aucun fils (ex : D)
  * //__arête :__// segment qui relie deux nœuds
  * //__profondeur d'un nœud :__// nombre de nœuds du chemin entre la racine et le nœud (ex : F est à une profondeur de 3)
  * //__hauteur d'un arbre :__// profondeur maximale de l'arbre (ici : 5)
  * //__taille d'un arbre :__// nombre de nœuds composant l'arbre (ici : 17)


Un arbre binaire ( ayant donc 1 ou 2 fils) aura forcément des sous-arbres , qui peuvent être comparés à des branches d'un vraie arbre. Donc le sous-arbres gauches est tous les nœuds qui sont sous le nœud donné à gauche. C'est la même chose pour le sous-arbre droit mais cependant c'est à droite .
Ici , le sous-arbre gauche de A est en rouge et le droit est est violet.

{{ :les_fiches_revisions:structure_des_donnees:capture_d_ecran_2023-01-18_161010.png?400 |}}
====Arbres binaires de recherche====
Un arbre binaire de recherche est un cas particulier d'arbre binaire. 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é.