Cours 4 - Généralités sur les arbres

name: inverse
layout: true
class: center, middle, inverse
---

# INFORMATIQUE 3 - CM 4
## Inès de Courchelle
## 2024-2025

![image](../img/CY-tech.png)

---
layout: false
# Généralités sur les arbres
## Plan
1. Définition d'un arbre
2. Le vocabulaire
3. Le parcours
4. Des propriétés
5. Arbres binaires

---
# Généralités sur les arbres
## Plan
1. .under[Définition d'un arbre]
2. Le vocabulaire
3. Le parcours
4. Des propriétés
5. Arbres binaires

---
# Généralités sur les arbres
## Qu'est ce qu'un arbre ?
<img src="img/arbre.webp" width=200>

## De manière générale
- Structure de stockage des fichiers sur un disque dur
- Expression formelle de calculs
- Arbres de décision
- ...

---
# Généralités sur les arbres
## Des exemples
<img src="img/exempleRG.jpg" width=350>

---
# Généralités sur les arbres
## En Vrai
<img src="img/lol.jpg" width=125>

## En Info
<img src="img/lol3.jpg" width=125>

---
# Définition d'un arbre
## Définition (Théorie des graphes)
.otro-blockquote[Un arbre est un graphe (orienté ou non), connexe et sans cycle.]
## Définition (Récursive)
.otro-blockquote[Un arbre est un arbre qui possède des liens ou des pointeurs vers d'autres arbres.]

---
# Exemples
## Arbre non enraciné
.pull-left[
- Il n'y a pas d'ordre
- C'est l'anarchie !

]
.pull-right[
<img src="img/arbrenonenracine.svg" width=280>
]

---
# Exemples
## Arbre enraciné
- Il y a des niveaux
- C'est un graphe orienté !

---
# Généralités sur les arbres
## Plan
1. Définition d'un arbre
2. .under[Le vocabulaire]
3. Le parcours
4. Des propriétés
5. Arbres binaires

---
# Le vocabulaire
## Un arc
<img src="img/arc.png" width=400>

<img src="https://c.tenor.com/HCtlf7gyqDwAAAAd/robin-hood-shoot.gif" width=100>
---
# Le vocabulaire
## Un noeud
<img src="img/noeud.png" width=400>

---
# Le vocabulaire
## Noeud externe ou feuille
<img src="img/feuille.png" width=400>

C'est un noeud qui n'a pas d'arc sortant !

---
# Le vocabulaire
## Noeud interne
<img src="img/interne.png" width=400>

C'est un noeud qui n'est pas externe !

---
# Le vocabulaire
## La racine
<img src="img/racine.png" width=400>

Tout en haut quoi !

---
# Le vocabulaire
## Noeud frères ou soeurs
<img src="img/frere.png" width=400>

---
# Le vocabulaire
<img src="img/ancetre.png" width=400>
#### Noeud ancêtre
1 est l'ancêtre de 9
#### Noeud descendant
9 est le descendant de 1

---
# Le vocabulaire
<img src="img/arbreEnracine.png" width=400>
#### La taille
C'est le nombre de noeud dans l'arbre (ici de 10)
####  Le nombre de feuille
C'est le nombre de feuille ou noeud externe (ici de 6)

---
# Le vocabulaire
<img src="img/noeudDegre.png" width=400>

#### Le degré d'un noeud
- C'est le nombre de descendants d'un noeud.
- Ce n'est pas tous les descendants, mais juste les fils (descendants du 1er niveau, mais pas encore dessous).

#### Le degré d'un arbre
C'est le plus grand des degrés de ses noeuds (ici de 5)

---
# Le vocabulaire
<img src="img/profondeurArbre.png" width=400>

#### Profondeur d'un noeud
c’est la distance du chemin qui relie la racine au nœud.
#### La hauteur
c’est la profondeur maximale de ses nœuds (ici de 2)

---
# Le vocabulaire
## Arbre ordonné
Un arbre ordonné est un arbre dans lequel l’ensemble des enfants de chaque nœud est totalement ordonné.
Par exemple, un livre, structuré en chapitres, sections, etc., se présente comme un arbre ordonné.

## Arbre numéroté
Un arbre numéroté est un arbre ordonné dont la valeur des feuilles ne permettent pas de voir s'il est ordonné ou pas. C'est pourquoi, on rajoute une étiquette de numérotation.

---
# Le vocabulaire
## Le cheminement
#### Longueur
La longueur de cheminement d'un arbre correspond à la somme des hauteurs de chacun des noeuds.

#### Externe
La longueur de cheminement externe d'un arbre correspond à la somme des hauteurs de chacune des feuilles.

#### Interne
La longueur de cheminement interne d'un arbre correspond à la somme des hauteurs des nœuds internes de l'arbre.

---
# Le vocabulaire
## Le cheminement
.pull-left[
- Longueur de cheminement (LC) => 15
- Longueur de cheminement externe (LCE) => 12
- Longueur de cheminement interne (LCI) => 3
]
.pull-right[
<img src="img/cheminement.png" width=200>
]

---
# Généralités sur les arbres
## Plan
1. Définition d'un arbre
2. Le vocabulaire
3. .under[Le parcours]
4. Des propriétés
5. Arbres binaires

---
# Les parcours
## Définition

Algorithme qui permet de visiter tous les noeuds d’un arbre. Il appelle une méthode,fonction ou procédure, sur tous les noeuds (ou les sous arbres).

## Les différents types
- Parcours en profondeur
- Parcours en largeur

---
# Les parcours
## En profondeur
.otro-blockquote[Si l'arbre n'est pas vide, le parcours de l'un des deux sous-arbres est terminé avant que ne commence celui de l'autre. On explore jusqu’au bout une branche pour passer à la suivante (on va vers les fils avant d'aller vers les frères)]

## En Largeur
.otro-blockquote[On explore les noeuds un par un sur un même niveau. On passe ensuite sur le niveau suivant, et ainsi de suite (on va vers les frères avant de parcourir les fils)]

---
# Parcours en profondeur
## Type Préfixe
- Chaque noeud est visité avant leur fils
- La racine est traitée avant les appels récursifs sur les sous-arbres gauche et droit

---
# Parcours en profondeur
## Type Préfixe
<img src="img/exempleGraph.png" width=500>

[0,1,2,7,3,4,5,8,9,6,10,12,13,15,14,16]

---
# Parcours en profondeur
## Type Infixe
- On visite chaque noeud après son fils à gauche et avant son fils à droite
- La racine est traitée entre les appels sur les sous-arbres gauches et droits
- .underR[Attention] : Le type infixe n'est que pour les arbres binaires, alors que le préfixe et postfixe peut être pour tous les types d'arbres

---
# Parcours en profondeur
## Type Infixe
<img src="img/exempleGraph.png" width=500>

[7,2,1,4,3,5,8,0,12,10,13,6,9,14,15,16]

---
# Parcours en profondeur
## Type Postfixe (ou suffixe)
- on visite chaque noeud après avoir visité chacun de ses fils
- la racine est traitée après les appels récursifs sur les sous-arbres gauche et droit

---
# Parcours en profondeur
## Type Postfixe (ou suffixe)
<img src="img/exempleGraph.png" width=500>

[7,2,4,8,5,3,1,12,13,10,6,14,16,15,9,0]

---
# Parcours en largeur
## Définition
- On visite l'arbre niveau par niveau
- Les nœuds de niveau 0 sont sont d'abord parcourus puis les nœuds de niveau 1 et ainsi de suite
- Dans chaque niveau, les nœuds sont parcourus de la gauche vers la droite
<img src="img/exempleGraph.png" width=450>

---
# Parcours en largeur
<img src="img/exempleGraph.png" width=500>

[0,1,9,2,3,6,15,7,4,5,10,14,16,8,12,13]

---
# Généralités sur les arbres
## Plan
1. Définition d'un arbre
2. Le vocabulaire
3. Le parcours
4. .under[Des propriétés]
5. Arbres binaires

---
# Les propriétés
## Pour un arbre non vide
#### Arbre Localement complet
Pour tout nœud interne s de l'arbre A, on a deg(s) = deg (A)
#### Arbre complet
S’il est localement complet et si, pour toute feuille f de l'arbre A, on a hauteur(f)=hauteur(A)
#### Arbre parfait
Si l’arbre A’ obtenu en supprimant les feuilles du dernier niveau de A est complet et si les feuilles de l’arbre A sont regroupées le plus à gauche possible.
#### Arbre dégénéré
A est dégénéré s’il ne contient qu’une seule feuille.

---
# Généralités sur les arbres
## Plan
1. Définition d'un arbre
2. Le vocabulaire
3. Le parcours
4. Des propriétés
5. .under[Arbres binaires]

---
# Arbre binaire
## Définition
- Un arbre binaire est un arbre de degré 2
- Un arbre binaire est soit vide, soit constitué d’une racine contenant un élément et de deux arbres binaires disjoints, appelés respectivement : fils gauche et fils droit

---
# Arbre binaire
## Exemple

---
# Arbre binaire
## Fonctionnalités
- Fonction creerArbreBinaire(valeur : entier, filsG: arbre, filsD : arbre) : arbre
- Fonction avoirUnFG (a : arbre, filsG : arbre) : booleen
- Fonction avoirUnFD (a : arbre, filsD : arbre) : booleen
- Fonction recupererFilsG (a : arbre) : arbre
- Fonction recupererFfilsD (a : arbre) : arbre
- Fonction estFeuille (a : arbre) : booleen
- Fonction estVide (a : arbre) : booleen
- Fonction nbfeuilles (a : arbre) : entier
- Fonction taille (a : arbre) : entier

## Fonctions récursives
- Procédure afficherInfixe (a : arbre)
- Procédure afficherPrefixe (a : arbre)
- Procédure afficherPostfixe (a : arbre)

---
# Arbre binaire
## En C
```c
typedef struct noeud {
  int val;
  noeud* filsG;
  noeud* filsD;
}noeud;

typedef noeud* arbre;
```
---
# Arbre binaire
## En C
<img src="img/fichierSep.png" width=200>

---
# Bilan
## Où pouvons nous utiliser un arbre ?
- Dans les expressions mathématiques avec les opérateurs et les parenthèses
- Dans l'algo min max
- Pour représenter les possibilités de coup aux échecs

## Pourquoi ce cours ?
- Réfléchir pour des matières d'info dans votre cursus
- Se familiariser avec les structure récursive non lineaire
- Appréhender les arbres pour les design patern (cas composite) en ING 2 GSI
- Connaître la structure arbre pour l'IA en ING 2 - 3 INFO et MATH
- Comprendre la decidabilité => ING 2 MI
- Modèliser des données en tant qu'informaticien

.underR[Attention] : Le type infixe n'est que pour les arbres binaires, alors que le préfixe et postfixe peut être pour tous les types d'arbres

---
# Quelques liens utiles
## Cours sur les arbres
<a href="https://rmdiscala.developpez.com/cours/LesChapitres.html/Cours4/Chap4.7.htm" target="_blank"> cours 1</a>

<a href="https://www.irif.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/Tree/parcours.html" target="_blank"> cours 2</a>

## Subreddit
<a href="https://www.reddit.com/r/ProgrammerHumor/" target="_blank">subreddit</a>