Arbres - Généralités

I. Introduction⚓︎

arbres

Source Gilles Lassus

Arbre

Un arbre est une structure hiérarchique permettant de représenter de manière symbolique des informations structurées.

L'arborescence d'un disque dur

Les systèmes Unix (MacOS ou GNU/Linux) organisent leur disque dur suivant l'arborescence ci-dessous :

Unix

Un arbre généalogique des descendants ou des ascendants

graph TD
A(Vous)
B(Père)
C(Mère)
F(Grand-père paternel)
G(Grand-mère paternelle)
D(Grand-père maternel)
E(Grand-mère maternelle)
A --- B
A --- C
B --- F
B --- G
C --- D
C --- E

Organisation des matchs d'un tournoi de sport

graph TD
A(Vainqueur)
B(Finaliste 1)
C(Finaliste 2)
D(Demi-finaliste 1)
E(Demi-finaliste 2)
F(Demi-finaliste 3)
G(Demi-finaliste 4)
H(Quart-finaliste 1)
I(Quart-finaliste 2)
J(Quart-finaliste 3)
K(Quart-finaliste 4)
L(Quart-finaliste 5)
M(Quart-finaliste 6)
N(Quart-finaliste 7)
P(Quart-finaliste 8)
A --- B
A --- C
B --- D
B --- E
C --- F
C --- G
D --- H
D --- I
E --- J
E --- K
F --- L
F --- M
G --- N
G --- P

II. Terminologie⚓︎

Attention

l'analogie avec les arbres réels peut s'avérer trompeuse. Les arbres - en informatique - sont le plus souvent représentés avec la racine en haut, puis les nœuds, et les feuilles en bas.

racines envers

Un arbre

Un arbre est une structure hiérarchique de données, composée de nœuds.

terminologie

Source Gilles Lassus

Chaque nœud a exactement un seul nœud père, à l'exception du nœud racine qui est le seul nœud à ne pas avoir de père. (oui, la racine d'une arbre est en haut)
Chaque nœud peut avoir un nombre quelconque de fils, dont il est le père.
Les nœuds qui n'ont pas de fils sont appelés les feuilles (ou nœuds externes).
Les nœuds qui ne sont pas des feuilles sont des nœuds internes.
Le nom de chaque nœud est appelé son étiquette.

Exemple

graph TD
A(A)
B(B)
C(C)
D(D)
E(E)
F(F)
G(G)
H(H)
I(I)
A --- B
A --- C
B --- D
B --- E
B --- F
C --- G
E --- H
E --- I

La racine est le nœud A.
Le nœud B possède 3 fils (les nœuds D, E et F), le noeud C possède un fils (le nœud G), le nœud F ne possède aucun fils.
Le nœud B a pour père le nœud A.
Les feuilles sont les nœuds D, H, I, F et G (ceux qui n'ont pas de fils).

Attention

Attention : il faut bien repérer dans les définitions suivantes, si on compte les nœuds, ou si on regarde la longueur d'une branche.

Il y a en effet un décalage de 1 entre ces deux nombres.

Conventions retenues dans ce cours

⚠️Un arbre ne contenant qu'un élément à une hauteur de 1.
La profondeur de la racine est 0

Définitions

La taille d'un arbre est le nombre de nœuds qu'il possède.
La profondeur d'un nœud ou d'une feuille d'un arbre est la longueur du chemin le plus court vers la racine .
- La profondeur d’un nœud est égale à la profondeur de son père plus 1
- Si un nœud est à une profondeur $p$, tous ses fils sont à une profondeur $p+1$
Il existe plusieurs méthode pour déterminer la profondeur d'un nœud :
- La profondeur d'un nœud est le nombre d'arêtes entre la racine et ce nœud (c'est la convention retenue dans ce cours)
- La profondeur d’un nœud est le nombre de nœuds du chemin qui va de la racine à ce nœud sans compter la racine
- 🤿 on peut imaginer que la racine est à la surface de l'eau, donc à une profondeur 0, et que les nœuds sont à des profondeurs 1, 2, 3, etc.
  Dans l'arbre précédent :
  - profondeur de B = 1
  - profondeur de I = 3 .
La hauteur d’un arbre est le nombre de nœuds du plus long chemin de la racine aux feuilles en comptant la racine et la feuille.

Dans l'arbre précédent : hauteur de l'arbre = 4

Autres définitions

Attention : On trouve aussi dans la littérature, que la profondeur de la racine est égale à 1, ce qui modifie la hauteur de l'arbre également puisqu'alors l'arbre réduit à la racine a pour hauteur 0 et l'arbre vide a pour hauteur -1. Les deux définitions se valent, il faut donc bien lire celle qui est donnée.

Exemple

graph TD
A(A)
B(B)
C(C)
D(D)
E(E)
F(F)
G(G)
H(H)
I(I)
A --- B
A --- C
B --- D
B --- E
B --- F
C --- G
E --- H
E --- I

La taille de l'arbre est égale à 9 (il possède 9 nœuds : 4 nœuds internes et 5 feuilles).
Le nœud E a une profondeur égale à 2 (le chemin A-B-E est de longueur 2).
La hauteur de l'arbre est égale à 4 car la branche A-B-E-H possède 4 nœuds (la profondeur maximale est égale à 3, c'est celle des nœuds les plus profonds : H et I. On a bien profondeur + 1 = hauteur).

III. Arbres binaires⚓︎

👉 Dans la suite, on ne s'intéressera qu'aux arbres dont les nœuds ont au plus deux fils.

Les arbres binaires sont des cas particuliers d'arbre : l'arbre du tournoi sportif et l'arbre "père, mère..." sont des arbres binaires, en revanche, l'arbre représentant la structure du système de fichier n'est pas un arbre binaire.

Arbre binaire

Un arbre binaire est un arbre dont tous les nœuds ont au plus deux fils.

Exemple

L'arbre vu dans le paragraphe précédent n'est pas binaire car le nœud B possède 3 fils. En revanche, l'arbre ci-dessous est lui un arbre binaire.

graph TD
A(A)
B(B)
C(C)
D(D)
F(F)
M( )
G(G)
E(E)
H(H)
I(I)
L( )
J(J)
K(K)


A --- B
A --- C
B --- D
B --- F
C --- M
C --- G
D --- E
D --- H
F --- I
F --- L
G --- J
G --- K
linkStyle 4 stroke-width:0px;
linkStyle 9 stroke-width:0px;
style L opacity:0;
style M opacity:0;

Définition et vocabulaire spécifique aux arbres binaire (A connaître par ❤️)

Les définitions vues précédemment pour des arbres quelconques restent valables pour les arbres binaires. Pour les arbres binaires :

chaque nœud possède deux sous-arbres, éventuellement vides, que l'on appelle sous-arbre gauche et sous-arbre droit.
les nœuds qui ne sont pas des feuilles peuvent avoir une fils gauche et/ou un fils droit.

Les sous-arbres gauche et droit de A sont eux-mêmes des arbres dont les racines sont respectivement B et C. B et C possèdent eux-même des sous-arbres gauche et droit.

le nœud C possède un sous-arbre gauche, qui est vide, et un sous-arbre droit qui est l'arbre dont la racine est G,
le nœud B possède un sous-arbre gauche, qui est l'arbre dont la racine est D, et un sous-arbre droit qui est l'arbre dont la racine est F.
et ainsi de suite.

Fils gauche et fils droit

Il ne faut pas confondre fils gauche et fils droit, ainsi les arbres suivants ne sont pas les mêmes :

4 arbres

Structure récursive

Il est aussi important de bien noter que l'on peut aussi voir les arbres comme des structures récursives : les fils d'un nœud sont des arbres (sous-arbre gauche et un sous-arbre droite dans le cas d'un arbre binaire), ces arbres sont eux mêmes constitués d'arbres...

A vos crayons 😊

Tracez tous les arbres binaires possibles avec 3 nœuds puis quelques-uns avec 4 nœuds.

IV. Visualiser un arbre binaire⚓︎

La bibliothèque binarytree

Par curiosité, vous pouvez exécuter les lignes suivantes :

La documentation est très détaillée.

Ne vous inquiétez pas, grâce aux exemples, vous comprendrez très vite comment utiliser ce module.

Un premier exemple

Exécuter :

À vous de jouer : créer un autre arbre

Nous allons créer un arbre particulier : La racine est 20.
Ensuite, nous allons ajouter les noeuds suivants 5, 25, 3, 12, 21, 8, 28, 13, 6 en respectant une certaine règle :
On part de la racine. Si le noeud est plus petit, on le met à gauche, sinon à droite.

5 est donc à gauche de 20
25 est à droite de 20
3 est à gauche de 20, à gauche de 5
12 est à gauche de 20, à droite de 5
21 est à droite de 20, à gauche de 25
Ainsi de suite...

Voici le début de l'arbre que l'on doit obtenir

Compléter ci-dessous pour obtenir l'arbre complété : avec les nœuds suivants 5, 25, 3, 12, 21, 8, 28, 13, 6

Solution

from binarytree import Node

# Créer un arbre
arbre = Node(20)
arbre.left = Node(5)
arbre.right = Node(25)
arbre.left.left = Node(3)
arbre.left.right = Node(12)
arbre.right.left = Node(21)
arbre.left.right.left = Node(8)
arbre.right.right = Node(28)
arbre.left.right.right = Node(13)
arbre.left.right.left.left = Node(6)

print(arbre)

Résumé

Nous venons de créer un arbre binaire de recherche souvent noté ABR.

Nous reviendrons plus tard dans le cours sur l'étude des ABR

V. Taille d'un arbre binaire en fonction de sa hauteur.⚓︎

Les arbres binaires de hauteur 4

Les deux arbres binaires suivants sont de hauteur 4.
Nous prenons ici comme convention que la hauteur d'un arbre réduit à sa racine est 1.

hauteur 4

À gauche, nous avons un arbre filiforme, et à droite un arbre complet.

Parmi tous les arbres binaires de hauteur 4, celui de gauche est un exemple qui a le moins de nœuds possibles, et celui de droite un exemple où il y a le plus de nœuds possibles.
Nombre de nœuds de l'arbre 1 : 4
Nombre de nœuds de l'arbre 2 : 15
On peut remarquer que $15=2^4 - 1$

Les arbres binaires de hauteur 5

En procédant comme ci-dessus, on comprend aisément que le nombre minimal de nœuds pour un arbre de hauteur 5 est 5.
Le nombre maximal de nœuds est obtenu pour un arbre binaire complet :

hauteur 5

Source de l'image :

Il y a $1+2+4+8+16 = 31$ nœuds
On peut remarquer que $31=2^5 - 1$

Les arbres binaires de hauteur h

Soit $N$ la taille d'un arbre binaire (c'est à dire son nombre de nœuds) de hauteur $h$.

On peut démontrer que : $\boxed{ h \leq N \leq 2^{h}-1}$

😉 Pour les curieux : démonstration de $N \leq 2^{h}-1$

A chaque fois que l'on ajoute un niveau, le nombre de nœuds sur ce nouveau niveau est multiplié par 2.

(Voir le schéma pour l'arbre de hauteur 5).

Le nombre de nœuds d'un arbre binaire complet

de hauteur 4 est donc : $1+2+2^{2}+2^{3}$
de hauteur 5 est donc : $1+2+2^{2}+2^{3}+2^{4}$
de hauteur $h$ est donc : $1+2+2^{2}+...+2^{h-1}$

Première méthode en passant par le binaire

Le nombre $1+2+2^{2}+...+2^{h-1}$ s'écrit en binaire : $111...1$ avec $h$ termes 1.

Si on ajoute 1 à ce nombre, on obtient $100...0$ (1 suivi de $h$ fois $0$) qui est égal à $2^{h}$
Cela prouve que $1+2+2^{2}+...+2^{h-1}=2^{h}-1$

Deuxième méthode en passant par le calcul algébrique

Notons $S=1+2+2^{2}+...+2^{h-1}$. Une petite astuce est de calculer en développant $(2-1)S$.
On obtient $(2-1)S = 2+2^{2}+...+2^{h-1}+2^{h}-(1+2+2^{2}+...+2^{h-1} )$
Après simplification, on obtient donc :
$S=2^{h}-1$

Troisième méthode en utilisant le cours de maths sur les suites géométriques

Si vous avez suivi la spécialité mathématiques en première, vous allez ici en trouver une application.

Notons $S=1+2+2^{2}+...+2^{h-1}$.
On reconnait la somme des $h$ premiers termes d'une suite géométrique de raison $q=2$ et de premier terme $u_{0}=1$. (Terme général : $u_{n}=2^n)$
La formule est donc :
$S =\text{premier terme} \times \dfrac{1-q^{\text{nombre de termes}}}{1-q}=\text{premier terme} \times \dfrac{q^{\text{nombre de termes}}-1}{q-1}$
$S =1 \times \dfrac{2^h-1}{2-1}$
Après simplification, on obtient donc :
$S=2^{h}-1$

👉 A retenir

$\boxed{ h \leq N \leq 2^{h}-1}$

Attention

⚠️ Remarque, on trouve parfois une autre convention pour la hauteur : La hauteur d'un arbre réduit à sa racine est : 0
Avec cette définition, on a :
$\boxed{ h+1 \leq N \leq 2^{h+1}-1}$

VI. Taille d'un arbre binaire en fonction de sa hauteur.⚓︎

taille d'un arbre de hauteur 6

Comme nous l'avons vu au I. la hauteur d'un arbre de $N$ noeuds est maximale lorsque cet arbre est filiforme. Dans ce cas-là, $N=h$. D'une manière générale, on a donc : $h \leq N$.
Pour obtenir avec $N$ noeuds un arbre de hauteur la plus petite possible, il faut au contraire qu'il soit le plus équilibré possible.

hauteur 6

Nombre de noeuds	hauteur
1	1
2 ou 3	2
4 ou 5 ... ou 7	3
8 ou 9 ... ou 15	4
16 ou 17 ... ou 31	5
32 ou 33 ... ou 63	6

Utilisons le binaire

Nous pouvons écrire ce tableau en codant le nombre de noeuds en binaire. Nous obtenons :

Nombre de noeuds	hauteur
1	1
10 ou 11	2
100 ou 101 ... ou 111	3
1000 ou 1001 ... ou 1111	4
10000 ou 10001 ... ou 11111	5
100000 ou 100001 ... ou 111111	6

😊 Nous observons que la hauteur est exactement le nombre de bits nécessaires pour écrire le nombre de noeuds en binaire ...
Pour coder un entier en binaire, on peut procéder par divisions successives par deux, jusqu'à obtenir le quotient égal à $0$. Il suffit ensuite de lire les restes en partant du bas, comme indiqué sur cette figure.
Notre problème se résume donc à connaître le nombre de divisions nécessaires...

hauteur 6

Source de l'image :

🖐️ Pour 23 noeuds, on peut résoudre ce problème "à la main", en posant les divisions comme ci-dessus. 23 s'écrit en binaire sur 5 bits, il a fallu 5 divisions, la hauteur minimale est donc 5.

👉 A retenir

$\boxed{ \text{la hauteur est exactement le nombre de bits nécessaires pour écrire le nombre de noeuds en binaire}}$

Hauteur minimale de manière itérative

Compléter ci-dessous la fonction qui détermine la hauteur minimale de manière itérative.

Évaluations restantes : 5/5

.1280130ldCy14-ké/we!ibmc_:35qaPr+ 7=9of.gt28;6sSàh)(punv050d0n0K0y0p0c0P0C0s0c0y0P0P0E010K0p0V010406050P0W0r0r0y0A0f040Q0G0c0W0?0G0X050l0}0 11130{0V04051j1c1m0l1j0{0d0p0Y0+0-0/0;0S0p0J0S0c1A0S0K0_050$0q0c0n1v0.0:011z1B1D1B0K1J1L1H0K0A1k0K0S0+160P0V0y0X0;0L011N1x010H0(0n0X0y0r0n1H1*1,1;1P1@1L1`1|0_0a0C0z0A0G0V0G0P0p190X0C0!1(0A0A0n0s2h1c1 0X1k0l1$2u1Z1#1!1I0d210;1D0X1_2e1H1s1u0,1O2E0p2G0X0G2K1H0V2n1k2s2u2Y0|1+2i2M1=2R0A100c0_0C0g2r2$0`2#202(1P2*2,2.0L2;1,2?2s2D012{0y2-040C0v2 2t0{322_0;35370C0h3b312$333h2.0w3l3d3n3f340G2+362.0O3s2@2%1w2`3x2|380D3C3e3F3g3H3z380M3L3u3N3w3y3i0F3T2^3V3p040g0b3!3E2N3W3I0g2:1d2=1n2W1c2K2x0d1#2C3v0s2S1}1k3`1l3^2!3=3005400!2X3U3-0j0_0!0H3l0C3D3o0H0_0S0y180n0W0A0t0r2P3l4m3v0^040U4z3M3-0X0_0X0q2n0t2R4t0d0P4F4e1=4C0u4k4A3$0q0_2P0K4S3#3-4C0T4X4G1=0G0_0i020J0K0N4-4T2`4!044$4(3,4U0_4W483c4Y3-0m2.0C5b50330P0d0_020x0W0G4^5i5k5m5j5l4_553m4)1=5f5a5b0e0#0K1M0H1a2p0p1a0C2n0X0Y0G0p1M0-0C4q4s4u0C4x0X0p2,1M0d02030v0F0N0W2i114L1M0q2P0%2n0C0y0f1,0K0C4K4M4O0W4Q5|0G4P0P0I3+5e5g385b0C0e1a0Y1_2h0+0S5N2f1M0u0C5Q5S5C5U5#5%5)5+5@0A5.5J0k0d0W2g0C0R0C0P0y5J0y0s2P1M0n0P5{0g0I5n5r6U5p5o5s2Y06066b4l4.2`0_0s0V4%5t6(4{0;4:040E4`5v1P4x0_3*5t6$6b572)0_0x6_511P6?6^6/726*045}0n4N63604R6 6%7c0;4g040m1z1L763o747u3v6?0o7a2Y6:6`0;6|046~2!6)0;4V3s6%7m7K347w7b7Q797x3$7S7J6;016?0l0l5d3v7G2~7l7O5c7Q4I046,6.7C7n7#0_7B2=7D773g6+6-7W3-6?0B831=7G3;6!7P7!7p2n0K4u1b7T7!7;7?3C0l4b0n2u2V8q3_1t3{2x2A2v0y1K8t0l3`0{8D0#0%0)04.

Hauteur minimale de manière récursive

Compléter ci-dessous la fonction qui détermine la hauteur minimale de manière récursive.

Évaluations restantes : 5/5

.1280130ldCy14-ké/weibmc_:35qaPr+ 7=9of.gt28;6sSàh)(punv050d0n0J0x0o0c0O0B0r0c0x0O0O0D010J0o0U010406050O0V0q0q0x0z0f040P0F0c0V0=0F0W050l0|0~10120`0U04051i1b1l0l1i0`0d0o0X0*0,0.0:0R0o0I0R0c1z0R0J0^050#0p0c0n1u0-0/011y1A1C1A0J1I1K1G0J0z1j0J0R0*150O0U0x0W0:0K011M1w010G0%0n0W0x0q0n1G1)1+1:1O1?1K1_1{0^0a0B0y0z0F0U0F0O0o180W0B0Z1%0z0z0n0r2g1b1~0W1j0l1#2t1Y1!1Z1H0d200:1C0W1^2d1G1r1t0+1N2D0o2F0W0F2J1G0U2m1j2r2t2X0{1*2h2L1;2Q0z0 0c0^0B0g2q2#0_2!1 2%1O2)2+2-0K2:1+2=2r2C012`0x2,040B0u2~2s0`312^0:34360B0h3a302#323g2-0v3k3c3m3e330F2*352-0N3r2?2$1v2_3w2{370C3B3d3E3f3G3y370L3K3t3M3v3x3h0E3S2@3U3o040g0b3k1m2V1b2J2w0d1!2B3u0r2R1|1j3.1k3,2Z1c2;053@0Z2W3T2M010j0^0Z0G3k0B3C3n0G0^0R0x170n0V0z0s0q2O2}3 2 4e3u0@040T3*3L460W0^0W0p2m0s2Q4l0d0O4z451;4w0t4c4u3#0p0^2O0J4M3!464w0S4R4A1;0F0^0i020I0J0M4%4N2_4U044W4Y3D4!0^4Q4s3b4S460m2-0B554`320O0d0^020w0V0F4/5c5e5g5d5f4:4 3l4Z1;5954550e0!0J1L0G192o0o190B2m0W0X0F0o1L0,0B4i4k4m0B4p0W0o2+1L0d02030u0E0M0V2h104F1L0p2O0$2m0B0x0f1+0J0B4E4G4I0V4K5?0F4J0O0H3Z4{5q5a37550B0e190X1^2g0*0R5H2e1L0t0B5K5M5w5O5V5X5Z5#5.0z5(5D0k0d0V2f0B0Q0B0O0x5D0x0r2O1L0n0O5=0g605n063s5p1O5r65555h5l6X5j5i5m2X06664d4(1O484^4b5n6*4=3f4D5(4H5}5`4L6:514)0^0D0D4;6S0:4p0^2/5n6~1O4P3r6)6)7a0:6-2m0J4m1a6}6+750o777d667g470^0n0(0n574v4}7s7e6;747v047j7l73621O763%7L324*040A7Q3u4C046l4l4n5Q4r2Z7o014w4y797)7X5@0n6_5~7V3U7S0l0l7@467O7%407)4#3B0l420n2t2U863-1s3/2w2z2u0x1J890l3.0`8j0!0$0(04.

😉 On peut aussi faire des maths...

Le même tableau écrit avec les puissances de 2 donne :

Nombre de noeuds	hauteur minimale

$2^{0 }$	$0+ 1=1$
$2^{1 }$ ou ... $2^{2 }-1$	$1+1=2$
$2^{2 }$ ou ... $2^{3 }-1$	$2+1=3$
$2^{3 }$ ou ... $2^{4 }-1$	$3+1= 4$
$2^{4 }$ ou ... $2^{5 }-1$	$4+1= 5$
$2^{^5 }$ ou ... $2^{6 }-1$	$5+1=6$

On constate que pour trouver la hauteur, il faut "récupérer" la puissance, et y ajouter 1.
Par définition, $\log_{2}(2^{n})=n$
Ainsi, $\log_{2}(2^{2})=2$, $\log_{2}(2^{3})=3$, $\log_{2}(2^{0})=0$ etc...
Autre exemple : $\log_{2}(13)\approx 3,7$. Or la hauteur correspondant pour $13$ noeuds est $3+1=4$ (voir le schéma).
Pour un nombre $N$ de noeuds, la hauteur est au moins égale à la partie entière de $\log_{2}(N)$ à laquelle on ajoute 1, c'est à dire à l'arrondi à l'unité inférieure de $\log_{2}(N)$, à laquelle on ajoute 1.
On note $\left\lfloor \log_{2}(N)\right\rfloor+1$.
Les symboles $\left\lfloor \quad \right\rfloor$ signifient "partie entière".

👉 A retenir

$\boxed{ \left\lfloor \log_{2}(N)\right\rfloor+1 \leq h \leq N}$

Attention

⚠️ Remarque, on trouve parfois une autre convention pour la hauteur : La hauteur d'un arbre réduit à sa racine est : $0$.
Avec cette définition, on a :
$\boxed{ \left\lfloor \log_{2}(N)\right\rfloor \leq h \leq N -1}$

🤔 Comment obtenir $\log_{2}(N)$ avec la calculatrice ?

Deux méthodes permettent de déterminer $\log_{2}(13)$ par exemple :

En utilisant la touche ln: taper successivement ln 13 $\div$ ln 2
En utilisant la touche log : taper successivement log 13 $\div$ log 2

🤔 Comment obtenir $\log_{2}(N)$ en Python ?

Tester ci-dessous

Hauteur minimale en utilisant le logarithme

Compléter ci-dessous la fonction qui détermine la hauteur minimale, en utilisant le $\log_{2}$

Évaluations restantes : 5/5

.128013ldCy14-ké/weibmc_:35qaPr+ 7=9of.gt28;6sSàh)(punv050c0m0I0w0n0b0N0A0q0b0w0N0N0C010I0n0T010406050N0U0p0p0w0y0e040O0E0b0U0;0E0V050k0{0}0 110_0T04051h1a1k0k1h0_0c0n0W0)0+0-0/0Q0n0H0Q0b1y0Q0I0@050!0o0b0m1t0,0.011x1z1B1z0I1H1J1F0I0y1i0I0Q0)140N0T0w0V0/0J011L1v010F0$0m0V0w0p0m1F1(1*1/1N1=1J1^1`0@0a0A0x0y0E0T0E0N0n170V0A0Y1$0y0y0m0q2f1a1}0V1i0k1!2s1X1Z1Y1G0c1 0/1B0V1@2c1F1q1s0*1M2C0n2E0V0E2I1F0T2l1i2q2s2W0`1)2g2K1:2P0y0~0b0@0f2p2!0^2Z1~2$1N2(2*0@0J2.1*2:2q2B012^0w2+040t2|2r0_2 2?0/32340g372~2!303d0@0u3g393i3b310E2)330@0M3n2;2#1u2@3s2_040B3x3a3A3c3C3u040K3g1l2U1a2I2v0c1Z2A3q0q2Q1{1i3S1j3Q2Y1b2/053Y0Y2V3p3I010i0@0Y0F3g0A3y3j0F0@0Q0w160m0U0y0r0p2N2{3*2}3|3q0?040S3O3H2L310@0V0o2l0r2P430c0N4h3:4j4e0s3`4c3;4m0@2N0I4u2=3;4e0R4z4i1:0E0@0h020H0I0L4L4v2%0o4D0V4F4a2r4A4w0@4y4$3h4H4j0l0@0A4=3{4,4(1:0N0c0@020v0U0E4T4~50524 514U4,3o4.4`4|044?0A0d0Z0I1K0F182n0n180A2l0V0W0E0n1K0+0A4042440A470V0n2*1K0c02030t0D0L0U2g0 4n1K0o2N0#2l0A0w0e1*0I0A4m4o4q0U4s5$0E4r0N0G3G4W1N4{4;4?0d180W1@2f0)0Q5u2d1K0s0A5x5z5j5B5I5K5M5O5X0y5R5q0j0c0U2e0A0P0A0N0w5q0w0q2N1K0m0N5#0f5:594_5?5d5f53576G5554582W06065f6C3c3 462N4V5b1N4O040C6V3z4j4C044E4G6$1:4e4g4^4M2@0@0b0E0H492Y6;0/6.6+3j4l5R4p5-5*4t6:5=6}0@0R4K4,3{6|016Y0z6#30472,3n6P7f3?042l0I44197d6Q4k040Q6T7v6M1a3-0m2s2T7G3R1r3T2v2y2t0w1I7J0k3S0_7T0Z0#0%04.

VII. Implémentations⚓︎

Plusieurs possibilités

Il existe, comme toujours, plusieurs implémentations possibles d'un arbre binaire. Nous allons voir dans ce TP quelques possibilités qui s'offrent à nous.

Partie 1 : implémentation avec une seule classe

Télécharger les trois fichiers, et les enregistrer dans un même dossier.

Attention

Si les téléchargements ne fonctionnent pas, utiliser le navigateur Firefox.

🌐 Fichier à télécharger : Fichier visu_arbre_3.py : "Clic droit", puis "Enregistrer la cible du lien sous"

🌐 Fichier à télécharger : Fichier visu_tree.py : "Clic droit", puis "Enregistrer la cible du lien sous"

🌐 Notebook jupyter à télécharger : Fichier arbres_une_classe_sujet.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

Lien pour lire le notebook jupyter : Notebook Basthon

⏳ La correction viendra bientôt ...

Partie 2 : implémentation avec un dictionnaire

Après avoir téléchargé le fichier, vous pourrez le lire à partir de Basthon

Attention

Si les téléchargements ne fonctionnent pas, utiliser le navigateur Firefox.

🌐 TD à télécharger : Fichier arbre_dico_2022_sujet.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

⏳ La correction viendra bientôt ...

Crédits⚓︎

Gilles Lassus, Jean-Louis Thirot , Mireille Coilhac, Valérie Mousseaux, sur la base du travail de :

David ROCHE publié sur Pixees
Equipe éducative DIU EIL, Université de Nantes.
Ressource d'accompagnement Eduscol sur les structures de données.
Livre Prepabac NSI, Tle, G. Connan, V. Petrov, G. Rozsavolgyi, L. Signac, éditions HATIER.

Nombre de noeuds	hauteur minimale

\(2^{0 }\)	\(0+ 1=1\)
\(2^{1 }\) ou ... \(2^{2 }-1\)	\(1+1=2\)
\(2^{2 }\) ou ... \(2^{3 }-1\)	\(2+1=3\)
\(2^{3 }\) ou ... \(2^{4 }-1\)	\(3+1= 4\)
\(2^{4 }\) ou ... \(2^{5 }-1\)	\(4+1= 5\)
\(2^{^5 }\) ou ... \(2^{6 }-1\)	\(5+1=6\)