58 lines
2.0 KiB
Markdown
58 lines
2.0 KiB
Markdown
# **Arbres binaires, arbres binaires de recherche, autres structures arborescentes**
|
|
|
|
Soit les 4 arbres binaires suivant :
|
|
|
|
<div style="display: flex; justify-content: space-around;">
|
|
<img src="assets/img2.png" alt="Méthodes_natives" style="zoom: 80%;" />
|
|
|
|
<img src="assets/img3.png" alt="Méthodes_natives" style="zoom: 80%;" />
|
|
|
|
<div style="display: flex; justify-content: space-around;">
|
|
<img src="assets/img4.png" alt="Méthodes_natives" style="zoom: 80%;" />
|
|
<img src="assets/img5.png" alt="Méthodes_natives" style="zoom: 80%;" />
|
|
</div>
|
|
|
|
|
|
|
|
Question 1 - Compléter le tableau :
|
|
|
|
|arbres |taille|hauteur|Profondeur de 4|profondeur de 5|profondeur de 6|
|
|
|:-----:|:----:|:-----:|:-------------:|:-------------:|:-------------:|
|
|
|arbre 1| | | | | |
|
|
|arbre 2| | | | | |
|
|
|arbre 3| | | | | |
|
|
|arbre 4| | | | | |
|
|
|
|
Question 2 - En utilisant la classe **BinnaryTree** du module ```arbres_binary_tree```, donner la définition :
|
|
|
|
- en plusieurs affectations (plusieurs lignes) de l'arbre ayant pour racine le noeud **4** ;
|
|
- en une seule affectation (une ligne) de l'arbre ayant pour racine le noeud **1**.
|
|
|
|
|
|
|
|
Question 3 - Dessiner les arbres de ces définitions :
|
|
|
|
```python
|
|
vide = BinaryTree()
|
|
|
|
# Premier arbre : F
|
|
A = BinaryTree("A", vide, vide)
|
|
E = BinaryTree("E", vide, vide)
|
|
I = BinaryTree("I", vide, vide)
|
|
|
|
B = BinaryTree("B", A, vide)
|
|
D = BinaryTree("D", vide, E)
|
|
H = BinaryTree("H", vide, I)
|
|
|
|
C = BinaryTree("C", B, D)
|
|
G = BinaryTree("G", vide, H)
|
|
|
|
F = BinaryTree("F", C, G)
|
|
|
|
# Deuxième arbre : J
|
|
J = BinaryTree("A", BinaryTree("B", vide, BinaryTree("F", vide, vide)), BinaryTree("D", BinaryTree("E", vide, vide), BinaryTree("C", vide, vide)))
|
|
```
|
|
|
|
Question 4 - Parmi les 5 arbres binaires ci-dessous, lesquels sont des ABR ?
|
|
|
|
 |