CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
INTRODUCTION A LA THÉORIE DES
ARBRES
53
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Les arbre sont très utilisés en informatique,
d’une part parce que les informations sont
souvent hiérarchisées, et peuvent être
représentées naturellement sous une forme
arborescente, et d’autre part, parce que les
structures de données arborescentes
permettent de stocker des données
volumineuses de façon que leur accès soit
efficace.
54
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Quelques exemples de données
arborescentes
Expressions arithmétiques. On
peut représenter les expressions
arithmétiques par des arbres
étiquetés par des opérateurs, des
constantes et des variables. La
structure de l’arbre rend compte
de la priorité des opérateurs et
rend inutile tout parenthèses.
55
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Arbre lexicographique. Un arbre lexicographique,
ou arbre en parties communes, ou dictionnaire,
représente un ensemble de mots. Les préfixes
communs à plusieurs mots apparaissent une
seule fois dans l’arbre, ce qui se traduit par un
gain d’espace mémoire. De plus la recherche d’un
mot est assez efficace, puisqu’il suffit de
parcourir une branche de l’arbre en partant de la
racine, en cherchant à chaque niveau parmi les
fils du nœud courant la lettre du mot de rang
correspondant.
56
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
57
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Définitions et terminologie
Définition.
Un arbre binaire (ou n-aire) est une structure
de données de type hiérarchique.
Un arbre est un ensemble organisé de nœuds
dans lequel chaque nœud a un père et un
seul, sauf un nœud que l’on appelle la racine.
58
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Définitions et terminologie
Définition d’un arbre binaire
Un arbre binaire est un ensemble fini de valeurs
qui est :
soit vide,
soit constitue d’une racine et des valeurs de
deux arbres binaires disjoints appelés sous-arbre
gauche et sous-arbre droit de la racine.
59
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Définitions et terminologie
Chaque élément est appelé nœud,
un nœud contient :
Une valeur ,
sous-arbre gauche,
sous-arbre droit.
le nœud initial étant appelé racine d’arbre
Une feuille est un nœud dont la sous-arbre
gauche et la sous-arbre droit sont vides.
60
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Définitions et terminologie
Vocabulaire
Ancêtre, descendant, père, fils
x descendant et fils (a droite) de y
y ancêtre et père de x
Tous les nœuds d'un arbre ont un et un seul parent, sauf la
racine.
Frère : Nœuds de même parent
Feuille : nœud sans fils
Racine : le seul nœud sans père
Degré d'un nœud : nombre de ses enfants
Profondeur d'un nœud : longueur du chemin entre la
racine et ce nœud
Hauteur d'un arbre : profondeur maximale de ses nœuds
Hauteur d'un nœud : longueur maximale du chemin entre
ce nœud et une feuille
61
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Définitions et terminologie
Taille d'un arbre = nombre de ses nœuds
Le nombre maximum de nœuds au niveau «l» d’un arbre binaire est
2l-1
Le nombre maximum de nœuds dans une arborescence binaire de
hauteur «h» est 2h - 1.
Hauteur = 4
Hauteur (x) = 2
Hauteur (y) = 3
Profondeur (y) = 2
Profondeur (x) = 3
Profondeur (r) = 1
Profondeur (z) = 4
62
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Parcours d’un arbre
Parcours en largeur
Dans un parcours en
largeur, on énumère les
nœuds par ordre croissant
de profondeur des nœuds
Autrement dit, de haut en
bas, niveau par niveau (et
de gauche a droite)
63
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Parcours d’un arbre
Parcours en profondeur
Parcours préfixe (NGD) :
tout Nœud est suivi des nœuds de son
sous-arbre Gauche puis des nœuds de
son sous-arbre Droit
Parcours infixe, ou symétrique (GND) :
tout Nœud est précédé des nœuds de
son sous-arbre Gauche et suivi des
nœuds de son sous-arbre Droit
Parcours suffixe, post-fixe (GDN) :
tout Nœud est précédé des nœuds de
son sous-arbre Gauche et des nœuds
de son sous-arbre Droit
64
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Parcours en profondeur : Exemple
Soit l'arbre binaire suivant :
Parcours préfixe
• Nœud, Gauche, Droite
• a, b, d, e, h, c, f, i, g, k
Parcours infixe
• Gauche, Nœud, Droite
• d, b, h, e, a, f, i, c, k, g
Parcours suffixe
• Gauche, Droite, Nœud
• d, h, e, b, i, f, k, g, c, a
65
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Il existe différentes manières de représenter un arbre
en machine. A l'aide :
d'une liste de listes
d'une matrice de taille optimale
d'un dictionnaire
Voici une représentation sous forme de listes
La liste sera sous la forme suivante:
[donnée, sous_arbre_gauche, sous_arbre_droite]
Une feuille est la racine d’un arbre binaire dont la
sous-arbre gauche et la sous-arbre droit sont égale à
None.
66
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
• Arb=[15, [7, [6, [None], [None]], [9,
[None],[None]]], [20, [None], [25, [None],
[None]]]]
67
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Avoir la sous-arbre gauche :
def get_left(arb):
return arb[1]
Avoir la sous-arbre droite :
def get_right(arb):
return arb[2]
68
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Parcours En Largeur ?
def parcoursEnLargeur(racine):
fifo = [racine]
while fifo:
arbre_courant = [Link](0)
sommet_courant = arbre_courant[0]
print(sommet_courant)
g=arbre_courant[1]
d=arbre_courant[2]
if g!=[None]:
[Link](g)
if d!=[None]:
[Link](d)
69
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Parcours En Profondeur ?
def prefixe(arb):
if(arb!=[None]):
print(arb[0],end=' ')
prefixe(get_left(arb))
prefixe(get_right(arb))
70
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Parcours En Profondeur ?
def infixe(arb):
if(arb!=[None]):
infixe(get_left(arb))
print(arb[0],end=' ')
infixe(get_right(arb))
71
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Parcours En Profondeur ?
def suffixe(arb):
if(arb!=[None]):
suffixe(get_left(arb))
suffixe(get_right(arb))
print(arb[0],end=' ')
72
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Déterminez les fonctions suivantes en python :
Hauteur_arb (arb) : qui calcule et retourne la
hauteur d'un arbre
Hauteur_nd (arb, nd ) : qui calcule et retourne
la hauteur d'un noeud nd de l'arbre arb
73
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Arbres binaires de recherche
Un arbre binaire de recherche (ABR) est un
arbre binaire dans lequel chaque nœud
possède une étiquette, telle que chaque
nœud du sous-arbre gauche possède une
étiquette inférieure ou égale à celle du nœud
considéré, et que chaque nœud du sous-arbre
droit possède une étiquette supérieure ou
égale à celle-ci
74
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Arbres binaires de recherche
La recherche d'un nœud
def recherche_element(arb,a):
if arb[0]==a:
return arb
elif a>arb[0]:
return recherche_element(get_right(arb),a)
else:
return recherche_element(get_left(arb),a)
75
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Arbres binaires de recherche
Insertion d'un nœud
def insert_element(arb,a):
if arb[0]==None :
arb[0]=a
[Link]([[None],[None]])
elif arb[0]>=a :
insert_element(get_left(arb),a)
else:
insert_element(get_right(arb),a)
76
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Arbres binaires de recherche
La recherche du maximum d'un arbre
def maximum(arb):
if arb[2]==[None]:
return arb
else:
return maximum(get_right(arb))
77
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Arbres binaires de recherche
Suppression d’un nœud
Plusieurs cas sont à considérer, une fois que le
nœud à supprimer a été trouvé :
Suppression d'une feuille
Il suffit de l'enlever de l'arbre étant donné
qu'elle n'a pas de fils.
78
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Arbres binaires de recherche
Suppression d'un nœud avec un seul fils
On l'enlève de l'arbre et on le remplace par
son fils.
79
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Arbres binaires de recherche
Suppression d'un nœud avec deux fils
Pour supprimer un nœud avec deux fils, on le
remplace par: soit le nœud le plus grand de son
sous-arbe gauche ou par le plus petit de son
sous-arbre droit, puis on supprime ce dernier
80
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Tri Par Tas
L'idée qui sous-tend cet algorithme consiste a
voir le tableau comme un arbre binaire.
Le premier élément est la racine, le deuxième
et le troisième sont les deux descendants du
premier élément, etc.
Ainsi le n élément a pour enfants les éléments
2n et 2n+1.
81
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
Tri Par Tas
Dans l'algorithme, on cherche a obtenir un tas, c'est-a-dire
un arbre binaire vérifiant les propriétés suivantes (les
deux premières propriétés découlent de la manière dont
on considère les éléments du tableau) :
la différence maximale de profondeur entre deux feuilles est de
1
les feuilles de profondeur maximale sont tassées sur la
gauche.
chaque nœud est de valeur supérieure (resp. inferieure) a celles
de ses deux fils, pour un tri ascendant (resp. descendant).
Il en découle que la racine du tas (le premier élément)
contient la valeur maximale (resp. minimale) de l'arbre. Le
tri est fonde sur cette propriété.
82
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
4 1 3 2 16 9 10 14 8 7
4 1 3 2 16 9 10 14 8 7
4
1
83
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
4 1 3 2 16 9 10 14 8 7
4
1 3
4 1 3 2 16 9 10 14 8 7
4
1 3
2 84
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
4 2 3 1 16 9 10 14 8 7
4
2 3
1
4 2 3 1 16 9 10 14 8 7
4
2 3
1 16
85
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
4 16 3 1 2 9 10 14 8 7
4
16 3
1 2
16 4 3 1 2 9 10 14 8 7
16
4 3
1 2 86
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
16 4 3 1 2 9 10 14 8 7
16
4 3
1 2 9
16 4 9 1 2 3 10 14 8 7
16
4 9
1 2 3
87
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
16 4 9 1 2 3 10 14 8 7
16
4 9
1 2 3 10
16 4 10 1 2 3 9 14 8 7
16
4 10
1 2 3 9
88
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
16 4 10 1 2 3 9 14 8 7
16
4 10
1 2 3 9
14
16 4 10 14 2 3 9 1 8 7
16
4 10
14 2 3 9
1
Prof: Yassine KHARCHACHI
89
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
16 14 10 4 2 3 9 1 8 7
16
14 10
4 2 3 9
1
16 14 10 4 2 3 9 1 8 7
16
14 10
4 2 3 9
1 8
Prof: Yassine KHARCHACHI
90
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
16 14 10 8 2 3 9 1 4 7
16
14 10
8 2 3 9
1 4
16 14 10 8 2 3 9 1 4 7
16
14 10
8 2 3 9
1 4 7 91
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
16 14 10 8 7 3 9 1 4 2
16
14 10
8 7 3 9
1 4 2
2 14 10 8 7 3 9 1 4 16
2
14 10
8 7 3 9
1 4
Prof: Yassine KHARCHACHI
92
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
14 2 10 8 7 3 9 1 4 16
14
2 10
8 7 3 9
1 4
14 8 10 2 7 3 9 1 4 16
14
8 10
2 7 3 9
1 4
Prof: Yassine KHARCHACHI
93
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
14 8 10 4 7 3 9 1 2 16
14
8 10
4 7 3 9
1 2
2 8 10 4 7 3 9 1 14 16
2
8 10
4 7 3 9
1
Prof: Yassine KHARCHACHI
94
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
10 8 2 4 7 3 9 1 14 16
10
8 2
4 7 3 9
1
10 8 9 4 7 3 2 1 14 16
10
8 9
4 7 3 2
1
Prof: Yassine KHARCHACHI
95
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
10 8 9 4 7 3 2 1 14 16
10
8 9
4 7 3 2
1
1 8 9 4 7 3 2 10 14 16
1
8 9
4 7 3 2
96
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
1 8 9 4 7 3 2 10 14 16
1
8 9
4 7 3 2
9 8 1 4 7 3 2 10 14 16
9
8 1
4 7 3 2
97
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
9 8 3 4 7 1 2 10 14 16
9
8 3
4 7 1 2
2 8 3 4 7 1 9 10 14 16
2
8 3
4 7 1
98
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
8 2 3 4 7 1 9 10 14 16
8
2 3
4 7 1
8 7 3 4 2 1 9 10 14 16
8
7 3
4 2 1
99
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
8 7 3 4 2 1 9 10 14 16
1
7 3
4 2
1 7 3 4 2 8 9 10 14 16
1
7 3
4 2
100
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
7 1 3 4 2 8 9 10 14 16
7
1 3
4 2
7 4 3 1 2 8 9 10 14 16
7
4 3
1 2
101
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
2 4 3 1 7 8 9 10 14 16
2
4 3
4 2 3 1 7 8 9 10 14 16
4
2 3
1
102
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
1 2 3 4 7 8 9 10 14 16
1
2 3
3 2 1 4 7 8 9 10 14 16
3
2 1
1 2 3 4 7 8 9 10 14 16
1
2
103
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
2 1 3 4 7 8 9 10 14 16
2
1
1 2 3 4 7 8 9 10 14 16
1 2 3 4 7 8 9 10 14 16
104
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021
def tamiser(t,noued,n):
for i in range(noued,int(n/2)):
if t[i*2+1]>t[i]:
j=2*i+1
while j>0 and t[j]>t[int((j-1)/2)]:
t[j],t[int((j-1)/2)]=t[int((j-1)/2)],t[j]
j=int((j-1)/2)
if (i*2+2)<n and t[i*2+2]>t[i]:
j=2*i+2
while t[j]>t[int((j-2)/2)] and j>0:
t[j],t[int((j-2)/2)]=t[int((j-2)/2)],t[j]
j=int((j-2)/2)
105
Prof: Yassine KHARCHACHI
