1$\text{Type de structure des arbres binaires}$
$\text{Structure hiérarchique}$
2$\text{Noeud}$
$\text{Élément d'un arbre}$
3$\text{Parent}$
$\text{Prédécesseur d'un noeud}$
4$\text{Racine}$
$\text{Noeud qui n'a pas de prédécesseur}$
5$\text{Enfants}$
$\text{Successeurs d'un noeud}$
6$\text{Étiquette}$
$\text{Donnée contenue dans un noeud}$
7$\text{Feuille}$
$\text{Noeud qui n'a pas d'enfants}$
8$\text{Noeuds internes}$
$\text{Noeuds qui ne sont pas des feuilles}$
9$\text{Sous-arbre}$
$\text{Noeud qu'on voit comme la racine d'un autre arbre}$
10$\text{Arbre binaire}$
$\text{Arbre dont chaque noeud comporte au plus 2 enfants}$
11$\text{Arité d'un noeud}$
$\text{Nombre de fils du noeud}$
12$\text{Arbre vide}$
$\text{Arbre qui ne contient aucun noeud}$
13$\text{Taille d'un arbre}$
$\text{Nombre de noeuds dans l'arbre}$
14$\text{Hauteur d'un arbre}$
$\text{Nombre de chemin maximal entre la racine et une feuille}$
15$\text{Profondeur d'un noeud}$
$\text{Nombre de chemin entre la racine et le noeud}$
16$\text{Diamètre d'un arbre}$
$\text{Le nombre de chemin maximal entre 2 noeud de l'arbre}$
17$\text{Défintition par induction de l'ensemble des arbres binaires } \mathcal A_E$
$\begin{cases}Vide \in \mathcal A_E \\ \forall (A_g, A_d, x) \in \mathcal A^2 \times E \quad Noeud(A_g, x, A_d) \in \mathcal A_E\end{cases}$
18$\text{Arbre binaire de recherche }$
$\text{Si } A = Noeud(A_g, x, A_d) \quad \begin{cases}\forall x' \in A_g \quad x' < x \\ \forall x' \in A_d \quad x' > x\end{cases}$
19$\text{Définition par induction de l'ensemble des arbre binaire de recherche } \mathcal A_R$
$\begin{cases}\forall x \in E \quad Vide \in \mathcal A_R\\ \forall (A_g, A_d, x) \in \mathcal A_R^2 \times E \quad max(A_g) \le x < min(A_d) \implies Noeud(A_g, x, A_d) \in \mathcal A_R\end{cases}$
20$\text{Définition par induction de l'ensemble des arbre binaire stricts } \mathcal A_S$
$\begin{cases}\forall x \in E \quad Noeud(Vide, x, Vide) \in \mathcal A_S \\ \forall (A_g, A_d, x) \in \mathcal A_S^2 \times E \quad (A_g, x, A_d) \in \mathcal A_S\end{cases}$
21$\text{Arbre parfait}$
$\text{Tous les "étages" de l'arbre sont remplis sauf le dernier qui est rempli de gauche à droite}$
22$\text{Tas max}$
$\text{Arbre binaire } A = Noeud(A_g, x, A_d) \text{ vérifiant : } \begin{cases} A \text{ est parfait} \\ \text{Sous réserve d'existence, \quad } \begin{cases} x_g < x \\ x_d < x \end{cases}\end{cases}$
23$\text{Tas min}$
$\text{Arbre binaire } A = Noeud(A_g, x, A_d) \text{ vérifiant : } \begin{cases} A \text{ est parfait} \\ \text{Sous réserve d'existence, \quad } \begin{cases} x_g > x \\ x_d > x \end{cases}\end{cases}$
24$\text{Parcours en largeur d'un arbre}$
$\text{On visite les noeuds par profondeur croissante}$
25$\text{Parcours préfixe d'un arbre}$
$\text{On traite l'étiquette de l'arbre courant puis récursivement celles à gauche puis à droite}$
26$\text{Parcours infixe d'un arbre}$
$\text{On traite les étiquettes de l'arbre gauche puis celle de l'arbre courant puis celles à droite}$
27$\text{Parcours suffixe / postfixe d'un arbre}$
$\text{On traite les étiquettes de l'arbre gauche puis celles à droite puis celle de l'arbre courant}$
28$\text{Propriété du parcours infixe d'un arbre binaire}$
$\text{Le parcours infixe d'un ABR liste ses étiquettes dans l'ordre croissant}$