Chapitre 17/19 : Arbres

$\text{Structure hiérarchique}$

$\text{Élément d'un arbre}$

$\text{Prédécesseur d'un noeud}$

$\text{Noeud qui n'a pas de prédécesseur}$

$\text{Successeurs d'un noeud}$

$\text{Donnée contenue dans un noeud}$

$\text{Noeud qui n'a pas d'enfants}$

$\text{Noeuds qui ne sont pas des feuilles}$

$\text{Noeud qu'on voit comme la racine d'un autre arbre}$

$\text{Arbre dont chaque noeud comporte au plus 2 enfants}$

$\text{Nombre de fils du noeud}$

$\text{Arbre qui ne contient aucun noeud}$

$\text{Nombre de noeuds dans l'arbre}$

$\text{Nombre de chemin maximal entre la racine et une feuille}$

$\text{Nombre de chemin entre la racine et le noeud}$

$\text{Le nombre de chemin maximal entre 2 noeud de l'arbre}$

$\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}$

$\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}$

$\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}$

$\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}$

$\text{Tous les "étages" de l'arbre sont remplis sauf le dernier qui est rempli de gauche à droite}$

$\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}$

$\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}$

$\text{On visite les noeuds par profondeur croissante}$

$\text{On traite l'étiquette de l'arbre courant puis récursivement celles à gauche puis à droite}$

$\text{On traite les étiquettes de l'arbre gauche puis celle de l'arbre courant puis celles à droite}$

$\text{On traite les étiquettes de l'arbre gauche puis celles à droite puis celle de l'arbre courant}$

$\text{Le parcours infixe d'un ABR liste ses étiquettes dans l'ordre croissant}$