xxxxxxxxxx
 
# Arbres : Cours - Partie 1 - Exercices​#### Exercice 1​- Donner la hauteur, la taille et les noms des feuilles de l'arbre binaire ci-dessous.​- Citer deux nœuds qui, si on les échange, modifient l'arbre binaire mais pas l'arborescence associée ?​<img src="https://progalgo.fr/images/arbres_exercices_1.png" style="width:250px;">

Arbres : Cours - Partie 1 - Exercices¶

Exercice 1¶

Donner la hauteur, la taille et les noms des feuilles de l'arbre binaire ci-dessous.
Citer deux nœuds qui, si on les échange, modifient l'arbre binaire mais pas l'arborescence associée ?

xxxxxxxxxx
 
<details><summary style="border:1pt solid slateblue; border-radius:5pt; width:15%; color:slateblue; padding:3px; background-color: lightcyan"> Solution </summary>      <div style="border:1pt solid slateblue; border-radius:5pt; color:slateblue; padding:3px; background-color: lightcyan"> ​    - Si on considère que la racine est de hauteur 1, la hauteur de cet arbre est 5. Cet arbre a pour taille 10 et ses feuilles sont les noeuds étiquetés G, E, I et J.        - Par exemple les noeuds D et E, ou les noeuds B et C ou encore les noeuds I et J. Si on effectue un de ces échanges, l'arbre binaire est modifié car on différencie sous-arbre gauche et sous-arbre droit. En revanche l'arborescence - qui ne prend pas en compte l'ordre dans lequel sont rangés les sous-arbres - ne serait pas modifiée par un de ces échanges.​​</div></details>

Solution

Si on considère que la racine est de hauteur 1, la hauteur de cet arbre est 5. Cet arbre a pour taille 10 et ses feuilles sont les noeuds étiquetés G, E, I et J.
Par exemple les noeuds D et E, ou les noeuds B et C ou encore les noeuds I et J. Si on effectue un de ces échanges, l'arbre binaire est modifié car on différencie sous-arbre gauche et sous-arbre droit. En revanche l'arborescence - qui ne prend pas en compte l'ordre dans lequel sont rangés les sous-arbres - ne serait pas modifiée par un de ces échanges.

xxxxxxxxxx
 
#### Exercice 2​On considère l'arborescence ci-dessous.​- 1) Quelle est sa taille ?​- 2) Quelle est l'étiquette de sa racine ?​- 3) Quelle est sa hauteur (en prenant la définition où la hauteur de la racine est 1) ?​- 4) Combien de sous-arborescences possède-t-elle ?​- 5) Combien de feuilles possède-t-elle ?​<img src="https://progalgo.fr/images/arbres_exercices_2.png" style="width:250px;">​

Exercice 2¶

On considère l'arborescence ci-dessous.

1. Quelle est sa taille ?
1. Quelle est l'étiquette de sa racine ?
1. Quelle est sa hauteur (en prenant la définition où la hauteur de la racine est 1) ?
1. Combien de sous-arborescences possède-t-elle ?
1. Combien de feuilles possède-t-elle ?

xxxxxxxxxx
 
<details><summary style="border:1pt solid slateblue; border-radius:5pt; width:15%; color:slateblue; padding:3px; background-color: lightcyan"> Solution </summary>      <div style="border:1pt solid slateblue; border-radius:5pt; color:slateblue; padding:3px; background-color: lightcyan"> ​- 1) 18        - 2) A        - 3) 5        - 4) 4        - 5) 9​</div></details>

Solution

1. 18
1. A
1. 5
1. 4
1. 9

xxxxxxxxxx
 
#### Exercice 3​On considère l'arbre binaire représenté ci-dessous.​- 1) Quelle est sa taille ?- 2) Quelle est l'étiquette de sa racine ?- 3) Quelle est sa hauteur (en prenant la définition où la hauteur de la racine est 1) ?- 4) Combien de feuilles possède-t-il ?- 5) Combien d'arbres vides sont intégrés dans cet arbre binaire ?- 6) Vérifier que les inégalités faisant le lien entre taille et hauteur sont bien vérifiées.​<img src="https://progalgo.fr/images/arbres_exercices_3.png" style="width:250px;">​

Exercice 3¶

On considère l'arbre binaire représenté ci-dessous.

1. Quelle est sa taille ?
1. Quelle est l'étiquette de sa racine ?
1. Quelle est sa hauteur (en prenant la définition où la hauteur de la racine est 1) ?
1. Combien de feuilles possède-t-il ?
1. Combien d'arbres vides sont intégrés dans cet arbre binaire ?
1. Vérifier que les inégalités faisant le lien entre taille et hauteur sont bien vérifiées.

xxxxxxxxxx
 
<details><summary style="border:1pt solid slateblue; border-radius:5pt; width:15%; color:slateblue; padding:3px; background-color: lightcyan"> Solution </summary>      <div style="border:1pt solid slateblue; border-radius:5pt; color:slateblue; padding:3px; background-color: lightcyan"> ​- 1) 9    - 2) 1    - 3) 5    - 4) 4    - 5) 10    - 6) En reprenant les notations du cours on a $N = 9$ et $h = 5$. On a alors $2^h = 32$. Or on a bien $5 \leq 9 < 32$ c'est à dire $h \leq N < 2^h$.​</div></details>

Solution

1. 9
1. 1
1. 5
1. 4
1. 10
1. En reprenant les notations du cours on a $N = 9$ et $h = 5$ . On a alors $2^h = 32$ . Or on a bien $5 \leq 9 < 32$ c'est à dire $h \leq N < 2^h$ .

xxxxxxxxxx
 
#### Exercice 4 :​- 1) Un arbre binaire est de taille N=1024. Donner un encadrement de sa hauteur h.- 2) Un arbre binaire est de hauteur h=8. Donner un encadrement de sa taille N.- 3) Dessiner un arbre binaire non étiqueté de taille 18 et de hauteur la plus petite possible.- 4) Dessiner un arbre binaire non étiqueté de taille 5 et de hauteur la plus grande possible.​

Exercice 4 :¶

1. Un arbre binaire est de taille N=1024. Donner un encadrement de sa hauteur h.
1. Un arbre binaire est de hauteur h=8. Donner un encadrement de sa taille N.
1. Dessiner un arbre binaire non étiqueté de taille 18 et de hauteur la plus petite possible.
1. Dessiner un arbre binaire non étiqueté de taille 5 et de hauteur la plus grande possible.

xxxxxxxxxx
 
<details><summary style="border:1pt solid slateblue; border-radius:5pt; width:15%; color:slateblue; padding:3px; background-color: lightcyan"> Solution </summary>      <div style="border:1pt solid slateblue; border-radius:5pt; color:slateblue; padding:3px; background-color: lightcyan"> ​- 1) $\log_2(1024) < h \leq 1024$ soit $10 < h \leq 1024$ soit finalement $11 \leq h \leq 1024$.        - 2) $8 \leq N < 2^8$ soit $8 \leq N < 256$ soit $8 \leq N \leq 255$.        - 3) 1 noeud à la racine (profondeur 1), 2 noeuds à la profondeur 2, 4 noeuds à la profondeur 3, 8 noeuds à la profondeur 4 et 3 noeuds à la profondeur 5.        - 4) 1 noeud à chaque profondeur de 1 à 5 (chaque noeud ne possède qu'un seul fils sauf le cinquième qui n'en possède pas).​</div></details>

Solution

1. $\log_2(1024) < h \leq 1024$ soit $10 < h \leq 1024$ soit finalement $11 \leq h \leq 1024$ .
1. $8 \leq N < 2^8$ soit $8 \leq N < 256$ soit $8 \leq N \leq 255$ .
1. 1 noeud à la racine (profondeur 1), 2 noeuds à la profondeur 2, 4 noeuds à la profondeur 3, 8 noeuds à la profondeur 4 et 3 noeuds à la profondeur 5.
1. 1 noeud à chaque profondeur de 1 à 5 (chaque noeud ne possède qu'un seul fils sauf le cinquième qui n'en possède pas).

xxxxxxxxxx
 
#### Exercice 5 :​Dessiner tous les arbres binaires non étiquetés possibles de taille 3.

Exercice 5 :¶

Dessiner tous les arbres binaires non étiquetés possibles de taille 3.

xxxxxxxxxx
 
<details><summary style="border:1pt solid slateblue; border-radius:5pt; width:15%; color:slateblue; padding:3px; background-color: lightcyan"> Solution </summary>      <div style="border:1pt solid slateblue; border-radius:5pt; color:slateblue; padding:3px; background-color: lightcyan"> ​Les noeuds sont représentés par $\ast$, on trouve 5 tels arbres binaires en tout.    ```    *        *          *         *        *   /        /          / \         \        \  *        *          *   *         *        * /          \                      /          \*            *                    *            *```​</div></details>

Solution

Les noeuds sont représentés par $\ast$ , on trouve 5 tels arbres binaires en tout.

    *        *          *         *        *
   /        /          / \         \        \
  *        *          *   *         *        *
 /          \                      /          \
*            *                    *            *