11 KiB
Les arbres binaires
Parmi la forêt d'arbres possibles, on s'intéressera essentiellement aux arbres dit binaires. Ceux ci sont principalement utilisés pour les bases de données (indexation), les moteurs de recherche, et les compilateurs.
Définition:
Un arbre binaire est un arbre de degré 2 (dont lesnoeuds sont de degré 2 au plus).
Les enfants d'un noeud sont lus de gauche à droite et sont appelés fils gauche et fils droit.
Exercice 1:
Parmi les arbres du cours précédent, lesquels sont binaires ?
Réponse
Remarque:
Les arbres binaires forment une structure de données qui peut se définir de façon récursive.
Un arbre binaire est:
- soit vide
- soit composé d'une racine portant une étiquette (clé) et d'une paire d'arbres binaires, appelés sous-arbre gauche et sous-arbre droit.
Les arbres binaires sont utilisés dans de très nombreuses activités informatiques, nous allons étudier et implanter cette structure de données.
Comment représenter un arbre binaire... à la main...
L'idée est de représenter l'arbre avec un tableau.
[r, a, b] La racine r suivie de ses fils gauche et droit.
Puis on rajoute dans l'ordre les fils gauche et droit de a, puis ceux de b.
[r, a, b, c, d, e, f]
Remarque:
Chaque noeud se repère par son indice n dans la liste, son fils gauche se trouvant alors à l'indice 2n + 1 et son fils droit à l'indice 2n + 2.
Exemple: b est d'indice 2, son fils gauche se trouve alors à l'indice 5 et son fils droit à l'indice 6.
Si un noeud n'a pas de fils, on le précise en mettant None à sa place. Notre arbre est alors représenté par le tableau:
[r, a, b, c, d, e, f, None, None, None, None, None, None, None, None]
Quelle taille doit avoir le tableau ?
Cet arbre est complet (tous les noeuds internes ont deux fils).
Il possède 3 niveaux, sa hauteur ou profondeur est donc de 2. La taille du tableau sera de: 2^0 + 2^1 + 2^2 + 2^3 = 2^4 -1 = 15
Il faut compter le nombre de noeuds, y compris les noeuds "fantômes" des feuilles.
Exercice :
- Quelle est la taille du tableau qui permet de représenter cet arbre ?
-
Ecrire le tableau représentant cet arbre et le stocker dans une variable t
-
Quelle propriété ont les indices des fils gauches et droits ?
-
Voici un tableau représentant un arbre binaire:
['*','-',5,2,6,None,None,None,None,None,None,None,None,None,None]
Le dessiner. Que peut-il représenter ?
Voici un code python Python qui crée la liste représentant l'arbre de l'exercice 2
def creation_arbre(r,profondeur):
"""r : la racine (str ou int). la profondeur de l’arbre (int)"""
Arbre = [r]+[None for i in range(2**(profondeur+1)-2)]
return Arbre
def insertion_noeud(arbre,n,fg,fd):
"""Insére les noeuds et leurs enfants dans l’arbre"""
indice = arbre.index(n)
arbre[2*indice+1] = fg
arbre[2*indice+2] = fd
# création de l’arbre
arbre = creation_arbre("r",5)
# ajout des noeuds par niveau de gauche à droite
insertion_noeud(arbre,"r","a","b")
insertion_noeud(arbre,"a","c","d")
insertion_noeud(arbre,"b","e","f")
insertion_noeud(arbre,"c",None,"h")
insertion_noeud(arbre,"d","i","j")
insertion_noeud(arbre,"e","k",None)
insertion_noeud(arbre,"f",None,None)
insertion_noeud(arbre,"h",None,None)
insertion_noeud(arbre,"i",None,None)
insertion_noeud(arbre,"j","m",None)
insertion_noeud(arbre,"k",None,None)
insertion_noeud(arbre,"m",None,None)
#pour vérifier
print(len(arbre))
print(arbre)
63
['r', 'a', 'b', 'c', 'd', 'e', 'f', None, 'h', 'i', 'j', 'k', None, None, None, None, None, None, None, None, None, 'm', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
Exercice 3:
- Ecrire une fonction qui retourne le parent d'un noeud s'il est dans l'arbre et None sinon.
- Ecrire une fonction qui retourne True si l'arbre est vide
- Ecrire une fonction qui retourne les enfants d'un noeud.
- Un fonction qui renvoie le fils gauche d'un noeud s'il existe et None sinon
- Même question pour le fils droit
- Ecrire une fonction qui renvoie True si le noeud est la racine de l'arbre
- Ecrire une fonction qui renvoie True si le noeud est une feuille
- Ecrire une fonction qui renvoie true si le noeud comporte un frère gauche ou droit.
Rappel : dans un tableau, si on note i l'indice d'un noeud, alors ses fils auront comme indice 2i +1 et 2i +2.
Inversement, pour trouver le parent d'un noeud, il faut vérifier : i - 1 //2
Une seconde façon de faire...
Comme vous l'avez sans doute constaté, il est assez fastidieux de représenter un arbre avec un unique tableau surtout pour un arbre très profond.
L'idée est de représenter l'arbre ave cun tableau contenant des tableaux
Cet arbre se représente par le tableau:
['r', ['a', [ ], [ ]], ['b', [ ], [ ]]]
Exercice :
Ecrire le tableau représentant l'arbre ci-dessous et le stocker dans une variable t
Le code Python ci-dessous, construit l'arbre de l'exercice 1 de manière récursive.
- Les noeuds sont représentés par un dictionnaire.
- L'arbre se construit depuis la racine en construisant les sous-arbres des fils gauche et droit.
def noeud(nom, fg =None, fd =None):
return{'racine': nom, 'fg' : fg, 'fd': fd}
# création des noeuds
k = noeud('k')
f = noeud('f')
e = noeud('e', k,None)
b = noeud('b', e, f)
m = noeud('m')
j = noeud('j', m,None)
i = noeud('i')
d = noeud('d', i, j)
h = noeud('h')
c = noeud('c',None, h)
a = noeud('a', c, d)
racine = noeud('r', a, b)
# création de l’arbre
def construit(arbre):
if arbre is None:
return [ ]
else:
return [arbre['racine'],construit(arbre['fg']),construit(arbre['fd'])]
arbre1 = construit(racine)
print(arbre1)
['r', ['a', ['c', [], ['h', [], []]], ['d', ['i', [], []], ['j', ['m', [], []], []]]], ['b', ['e', ['k', [], []], []], ['f', [], []]]]
Exercice :
Ecrire toutes les fonctions de l'exercice 3 dans le cas de cette implémentation de l'arbre.
Nous allons maintenant nous intéresser à la hauteur de l'arbre, ainsi qu'aux différentes façons de le parcourir:
- Le parcours en largeur
- Le parcours en profondeur (parcours fixe, parcours infixe et parcours suffixe).
Calcul de la hauteur de l'arbre: L'idée ets la suivante:
- Si l'arbre est vide, la hauteur vaut -1
- Sinon la hauteur vaut 1 auquel il faut ajouter le maximum entre les hauteurs des sous arbres gauche et droit.
- Ces sous-arbres sont eux même des arbres dont il faut calculer la hauteur.
Une méthode récursive semble donc tout à fait adaptée à la situation.
Voici l'algorithme:
Exercice :
- Ecrire cette fonction pour l'arbre précédent et vérifier que sa profondeur est de 4.
Les parcours
Le parcours en largeur: Le parcours en largeur d'un arbre consiste à partir de la racine. On visite ensuite son fils gauche puis sont fils droit, puis le fils gauche du fils gauche etc... Comme le montre le schéma ci-dessous:
L'idée est la suivante:
On utilise une File.
- On met l'arbre dans la file.
- Puis tant que la file n'est pas vide:
- On défile la file
- On récupère sa racine
- On enfile son fils gauche s'il existe
- on enfile son fils droit s'il existe
Voici l'algorithme:
Exercice 7
- Rappeler les fonction permettant de définir une structure de file en python.
- Implémenter alors cette fonction et l'essayer sur l'arbre précédent.
Les parcours en profondeur On se balade autour de l'arbre en suivant les pointillés
Voici un algorithme permettant de réaliser ce parcours:
Exercice
- Proposer une fonction permettant de réaliser le parcours en profondeur d'un arbre
Dans le schéma ci-dessus, on a rajouté des "noeuds fantômes" pour montrer que l'on peut considérer que chaque noeud est visité trois fois:
- une fois par la gauche
- une fois par en dessous
- une fois par la droite
Definition:
Dans un parcours prefixe, on liste le noeud la première fois qu'on le rencontre.
Exercice
- Ecrire les sommets dans l'ordre d'un parcours préfixe
Definition:
Dans un parcours infixe, on liste le noeud la seconde fois qu'on le rencontre.
Ce qui correspond à:
- On liste chaque noeud ayant un fils gauche la seconde fois qu'on le voit
- on liste chaque noeud sans fils gauche la première fois qu'on le voit
Exercice
- Ecrire les sommets dans l'ordre d'un parcours infixe
Definition:
Dans un parcours suffixe, on note le noeud la dernière fois qu'on le rencontre.
Exercice 11
- Ecrire les sommets dans l'ordre d'un parcours suffixe
Exercice
- Voici trois algorithmes récursifs, dire pour chacun d'entre eux à quel parcours il correspond.
- Implémenter ces trois fonctions en python et confirmer les réponses des questions précédentes
Une troisième façon de faire.... en programmation objet
Nous allons créer une classe Noeud dont les attributs d'instances seront:
- le nom (ou valeur) de la racine
- son fils gauche (None par défaut) ou de type Noeud
- son fils droit (None par défaut) ou de type Noeud
Exercice
- Implémentez cette classe Noeud
- Stocker l'arbre comme étant l'objet de type "Noeud" correspondant à la racine.
- Ecrire une méthode estFeuille qui renvoie True si le noeud est une feuille et False sinon
- Définir une fonction hauteur prenant comme argument un arbre permettant de renvoyer la hauteur de cet arbre
- Ecrire une méthode hauteur dans la classe Noeud permettant de faire la même chose
- Proposer des fonctions pour le parcours infixe, prefixe et suffixe pour cette façon de coder un arbre.
- Transformer alors vos fonctions en méthodes de la classe Noeud