Chapitre 13 : Les arbres
1. Introduction : 1. Définition
La structure d'arbre est l'une des plus importantes et des plus
spécifiques de l'informatique. Elle est utilisée par exemple pour Un arbre binaire est un ensemble de nœuds qui est soit vide, soit
l’organisation des fichiers dans les systèmes d'exploitation, la composé d’une racine et de deux arbres binaires disjoints appelés
représentation d'une table des matières, d'un arbre généalogique, sous-arbre droit et sous-arbre gauche
etc.
Dans ce chapitre, l’accent sera mise sur les arbres binaires qui
sont un cas particulier des arbres généraux.
Une propriété intrinsèque de la structure d’arbre est la récursivité.
Figure 1: Structure d’un arbre binaire
1 2
2. Création d’un arbre binaire
•Le père du sommet x est le sommet p tel qu'il existe un arc entre Un arbre binaire peut être créé en définissant un type
p et x (seule la racine de l’arbre n’a pas de père). correspondant à un nœud de l’arbre. Soit par exemple :
•Le frère de x est un sommet qui a le même père.
•Le sous-arbre droit (resp. gauche) d'un arbre binaire B est le Types
sous-arbre qui a pour racine le fils droit (resp. gauche) de B. Nœud = Structure
•Un nœud interne est un sommet qui a au moins un fils (gauche Valeur : entier
ou droit ou les deux). Gauche : pointeur sur Nœud
•Une feuille est un sommet qui n'a pas de fils. Droite : pointeur sur Nœud
•La hauteur d'un sommet x est la longueur (en nombre d'arcs) du FinStructure
plus long chemin de x à une feuille. Arbre = pointeur sur Nœud
•La hauteur d'un arbre est égale à la hauteur de la racine.
3 4
, Algorithme ArbreBinaire
Une telle structure peut être utilisée pour ordonner des éléments, Types
en considérant que le sous-arbre gauche d’un nœud de valeur n Nœud = Structure
Valeur : entier
contient les éléments inférieurs à n, tandis que le sous-arbre droit
Gauche : pointeur sur Nœud
contient les éléments supérieurs à n. Droite : pointeur sur Nœud
12
FinStructure
Arbre = pointeur sur Nœud
Variables
15
4 racine : Arbre
x : Entier
1 6 14 20 Procédure Construire(Elt : Entier ; Var B : Arbre)
Début
Si (B = Nil) Alors
L’algorithme suivant permet de construire un arbre d’entiers à Allouer(B)
partir d’une suite de nombres entrés par l’utilisateur. B^.valeur Elt
B^.gauche Nil
5 6
B^.droiteNil
3. Parcours d’un arbre binaire
Sinon
Si (Elt < B^.valeur) Alors 1. Parcours préfixe (Racine Gauche Droit)
Construire(Elt,B^.gauche) le nœud racine est traité au premier passage avant le parcours
Sinon
des sous-arbres
Si (Elt > B^.valeur) Alors
Construire(Elt,B^.droite) 2. Parcours infixe ou symétrique (Gauche Racine Droit)
FinSi le nœud racine est traité au second passage après le parcours
FinSi
du sous-arbre gauche et avant le parcours du sous-arbre
FinSi
Fin droit
Début 3. Parcours postfixe (Gauche Droit Racine )
racine Nil le nœud racine est traité au dernier passage après le parcours
Ecrire(”Entrer un entier : ”) Lire(x)
TantQue (x # 0) Faire des sous-arbres
Construire(x,racine)
Ecrire(”Entrer un entier :”) Lire(x)
FinTQ
7 8
Fin.
1. Introduction : 1. Définition
La structure d'arbre est l'une des plus importantes et des plus
spécifiques de l'informatique. Elle est utilisée par exemple pour Un arbre binaire est un ensemble de nœuds qui est soit vide, soit
l’organisation des fichiers dans les systèmes d'exploitation, la composé d’une racine et de deux arbres binaires disjoints appelés
représentation d'une table des matières, d'un arbre généalogique, sous-arbre droit et sous-arbre gauche
etc.
Dans ce chapitre, l’accent sera mise sur les arbres binaires qui
sont un cas particulier des arbres généraux.
Une propriété intrinsèque de la structure d’arbre est la récursivité.
Figure 1: Structure d’un arbre binaire
1 2
2. Création d’un arbre binaire
•Le père du sommet x est le sommet p tel qu'il existe un arc entre Un arbre binaire peut être créé en définissant un type
p et x (seule la racine de l’arbre n’a pas de père). correspondant à un nœud de l’arbre. Soit par exemple :
•Le frère de x est un sommet qui a le même père.
•Le sous-arbre droit (resp. gauche) d'un arbre binaire B est le Types
sous-arbre qui a pour racine le fils droit (resp. gauche) de B. Nœud = Structure
•Un nœud interne est un sommet qui a au moins un fils (gauche Valeur : entier
ou droit ou les deux). Gauche : pointeur sur Nœud
•Une feuille est un sommet qui n'a pas de fils. Droite : pointeur sur Nœud
•La hauteur d'un sommet x est la longueur (en nombre d'arcs) du FinStructure
plus long chemin de x à une feuille. Arbre = pointeur sur Nœud
•La hauteur d'un arbre est égale à la hauteur de la racine.
3 4
, Algorithme ArbreBinaire
Une telle structure peut être utilisée pour ordonner des éléments, Types
en considérant que le sous-arbre gauche d’un nœud de valeur n Nœud = Structure
Valeur : entier
contient les éléments inférieurs à n, tandis que le sous-arbre droit
Gauche : pointeur sur Nœud
contient les éléments supérieurs à n. Droite : pointeur sur Nœud
12
FinStructure
Arbre = pointeur sur Nœud
Variables
15
4 racine : Arbre
x : Entier
1 6 14 20 Procédure Construire(Elt : Entier ; Var B : Arbre)
Début
Si (B = Nil) Alors
L’algorithme suivant permet de construire un arbre d’entiers à Allouer(B)
partir d’une suite de nombres entrés par l’utilisateur. B^.valeur Elt
B^.gauche Nil
5 6
B^.droiteNil
3. Parcours d’un arbre binaire
Sinon
Si (Elt < B^.valeur) Alors 1. Parcours préfixe (Racine Gauche Droit)
Construire(Elt,B^.gauche) le nœud racine est traité au premier passage avant le parcours
Sinon
des sous-arbres
Si (Elt > B^.valeur) Alors
Construire(Elt,B^.droite) 2. Parcours infixe ou symétrique (Gauche Racine Droit)
FinSi le nœud racine est traité au second passage après le parcours
FinSi
du sous-arbre gauche et avant le parcours du sous-arbre
FinSi
Fin droit
Début 3. Parcours postfixe (Gauche Droit Racine )
racine Nil le nœud racine est traité au dernier passage après le parcours
Ecrire(”Entrer un entier : ”) Lire(x)
TantQue (x # 0) Faire des sous-arbres
Construire(x,racine)
Ecrire(”Entrer un entier :”) Lire(x)
FinTQ
7 8
Fin.
