0% ont trouvé ce document utile (0 vote)

6 vues74 pages

Parcours d'Arbres Binaires en Informatique

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

6 vues74 pages

Parcours d'Arbres Binaires en Informatique

Transféré par

chhed

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Cours réalisé par

NEFZI Mounir
Année universitaire
2023-2024

1
Plan

•Motivations
•Définition
•Terminologie et Arbres Binaires
•Insertion dans un ABR
•Parcours en profondeur d’un ABR
•Arbres Binaires de Recherche
•Insertion dans un ABR
•Parcours d'un ABR

2
Motivations

Les structures ( Tableaux, listes, piles et files) sont des structures linéaires:
Les données sont organisées de manière ordonnée les uns à la suite des autres

Pour chercher un élément, nous sommes obligés de parcourir toute la structure de donnée
jusqu’à le trouver.

La recherche d’un élément dans un arbre binaire de recherche est beaucoup plus rapide
que la recherche dans une structure de donnée linéaire.

3
Les Arbres

4
Définition
Un arbre est une structure de données composée d’un ensemble de nœuds.
Chaque nœud contient les données spécifiques de l’application et des pointeurs
vers d’autres nœuds (d’autres sous-arbres).
Plusieurs traitements en informatique sont de nature arborescente tel que:
• La représentation des expressions arithmétiques,.. Etc.
• La hiérarchie des répertoires et des fichiers

root

… Home

… Cours

Algo Programmation C 5
Terminologie et mesures

6
Terminologie(1)
Nœud Racine

▪ Le prédécesseur s’il existe s’appelle

A
père (père de C = A, père de L = H) Père

▪ Le successeur s’il existe s’appelle fils B C

(fils de A = { B,C }, fils de H= {L,M }) E F H I

▪ Le nœud qui n’a pas de prédécesseur Ses fils L M

s’appelle racine (A)

Sous Arbre

7
Terminologie(2)
▪ Le nœud qui n’a pas de successeur s’appelle feuille (Exemples: E,F,L,M,I)

▪ Un nœud descendant n d’un autre nœud X est tout nœud se trouvant dans
le chemin partant du nœud X jusqu’à une feuille ( y compris le nœud
feuille).

Exemple: Les descendants de C={H,I,L,M}, de B={E,F}

▪ Un nœud ascendant n d’un autre nœud X est tout nœud se trouvant dans le
chemin partant du nœud X jusqu’à la racine( y compris la racine).

Exemple: Les ascendants de L={H,C,A }, E={B,A}

8
Mesures sur les arbres(1)
Taille d’un arbre

▪ On appelle taille d’un arbre le nombre total de nœuds de cet arbre.

▪ Taille de l’arbre suivant = 9 Niveau 0 A

▪ Un arbre vide est de taille 0.

Niveau d’un nœud Niveau 1 B C

▪ Le niveau de la racine = 0
Niveau 2 E F H I
▪ Le niveau de chaque nœud = niveau

de son père + 1 Niveau 3 L M

▪ Niveau de {E,F,H,I} = 2

9
Mesures sur les arbres(2)
Profondeur (Hauteur) d’un arbre
A
▪ C’est le niveau maximum dans cet arbre.
Profondeur de l’arbre suivant = 3
B C
Degré d’un nœud
▪ Le degré d’un nœud est égal au nombre de ses fils. E F H I
▪ Degré de (A = 2, B =2, C = 2, E= 0, H=2)

L M
Degré d’un arbre
▪ C’est le degré maximum de ses nœuds.
Degré de l’arbre = 2
Le degré d’un arbre binaire est égal à 2.
Si le degré d’un arbre est égal à N, l’arbre est dit
N-aire.
10
Arbres Binaires

11
Définition (1)
Un arbre binaire est un arbre où chaque nœud a un fils gauche, un fils
droit ou les deux à la fois.

c’est un arbre ou le degré maximum d’un nœud est égal à 2.

12
Arbre binaire Arbre non binaire
Définition (2)
Si chaque nœud autre qu’une feuille admet deux descendants et si
toutes les feuilles sont au même niveau, on dit que l’arbre binaire
est complet.

Les arbres parfaits voient tous leurs niveaux remplis de gauche à

droite excepté le dernier.

13
Arbres Binaires de
Recherche

14
Définition
X racine
Un arbre binaire A de racine X est dit arbre binaire de
recherche (ABR) si et seulement si :

✔ Toute valeur associée à un nœud de son sous-arbre

principal gauche est <= X
Sous Sous
✔ Toute valeur associée à un nœud de son sous-arbre arbre arbre
gauche droite
principal droit est > X >X
<=X

✔ Tout sous-arbre de A est lui-même un ABR.

15
Exemples:

16
Exemple: ABR d'entiers
12

5 15

17
Exemple: ABR d'entiers

5 15

21 12

18
Exemple: ABR d'entiers

35
21 12

19
Exemple: ABR d'entiers

35
12

8
21

30
5

20
Structure
3 types de données sont stockées dans un nœud. :
▪La donnée data
▪Un pointeur de type Nœud vers le sous arbre gauche
▪Un pointeur de type Nœud vers le sous arbre droit
Relations entre types: Structure récursive
▪Un arbre binaire est caractérisé par une racine qui est un nœud
▪Les descendants d’un nœud sont des arbres binaires
définition récursive de l'arbre en fonction d'elle-même.
Solution : les descendants d'un nœud sont des pointeurs vers
d'autres nœuds.
21
Structure

Struct Nœud
{
TYPE data; // data peut avoir n'importe quel type
Struct Nœud * FG; // FG et FD sont deux pointeur vers
d'autres noeuds */
Struct Nœud * FD;
};

Typedef Struct Nœud * Arbre;

22
Insertion dans un ABR

23
Insérer un Nœud (1)
Fonction récursive d’ajout d’un élément :

✔ soit nouv un pointeur sur le nouveau nœud à insérer.

✔ soit R un pointeur sur le nœud racine.
1. Si R == NULL alors la racine devient l'adresse du nouveau
nœud (nouv)
2. Si valeur de nouv < = valeur de la Racine ( R) alors
Ajouter l'élément dans le sous arbre gauche ayant pour racine
le fils gauche de l'ancienne racine

3. Si valeur de nouv > valeur de la Racine ( R) alors

Ajouter l'élément dans le sous arbre droit ayant pour racine le fils
droit de l'ancienne racine
24
Insérer un Nœud (2)
Ajout d’un nœud ayant la valeur 5 à l’arbre

25
Insérer un Nœud (3)

26
Insérer un Nœud (4)

27
Parcours d'un ABR

28
Définition
Le parcours d’un arbre consiste à passer par tous ses
nœuds pour en effectuer un traitement.

On distingue deux types de parcours :

✔ Parcours en profondeur
✔ Parcours en largeur

29
Parcours en profondeur

30
Parcours en Profondeur

Dans un parcours en profondeur, commençant par la racine:

1. On descend le plus profondément possible dans l’arbre puis

2. Une fois qu’une feuille est atteinte, on remonte pour explorer

les autres branches en commençant par la branche "la plus basse"
parmi celles non encore parcourues.

31
Parcours préfixé

32
Parcours Préfixé
La racine est traitée en premier

1 Traiter la racine
2 Parcours préfixé du SAG

3 Parcours préfixé du SAD

33
Parcours Préfixé
La racine est traitée en premier

1 Traiter la racine
2 Parcours préfixé du SAG

3 Parcours préfixé du SAD

34
Parcours Préfixé
La racine est traitée en premier

1 Traiter la racine
2 Parcours préfixé du SAG

3 Parcours préfixé du SAD

35
Parcours Préfixé
La racine est traitée en premier

1 Traiter la racine
2 Parcours préfixé du SAG

3 Parcours préfixé du SAD

36
Parcours Préfixé
La racine est traitée en premier

1 Traiter la racine
2 Parcours préfixé du SAG

3 Parcours préfixé du SAD

37
Parcours Préfixé
La racine est traitée en premier

1 Traiter la racine
2 Parcours préfixé du SAG

3 Parcours préfixé du SAD

38
Parcours Préfixé
La racine est traitée en premier

1 Traiter la racine
2 Parcours préfixé du SAG

3 Parcours préfixé du SAD

39
Parcours Préfixé
La racine est traitée en premier

1 Traiter la racine
2 Parcours préfixé du SAG

3 Parcours préfixé du SAD

40
Parcours Préfixé
La racine est traitée en premier

1 Traiter la racine
2 Parcours préfixé du SAG

3 Parcours préfixé du SAD

41
Parcours Préfixé
La racine est traitée en premier

1 Traiter la racine
2 Parcours préfixé du SAG

3 Parcours préfixé du SAD

42
Parcours Préfixé
La racine est traitée en premier

1 Traiter la racine
2 Parcours préfixé du SAG

3 Parcours préfixé du SAD

Parcours préfixé : A, B, E, H, L, D, F, G, M, N.

43
Parcours Préfixé

44
Parcours Infixé

45
Parcours Infixé
La racine est traitée entre les deux appels récursifs