Algorithmes sur les arbres binaires et sur les arbres binaires de recherche

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