Il est conseillé de lire le cours “Les Arbres” pour approfondir la notion d'arbre binaire.

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

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é

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