6.4. TP 1 sur les arbres#
Le but de ce TP est de manipuler des arbres dans des cas simples et d’écrire des algorithmes permettant de les parcourir.
#!pip install --user binarytree
6.4.1. Prise en main de binarytree.#
Créer un arbre avec binarytree.
Un arbre est représenté par une classe Node(), qui dispose d’attributs
left et right qui seront des Node().
Recopier et compléter le code suivant.
from binarytree import Node
root = Node(1)
Show code cell source
root.left = Node(2) # le fils gauche de la racine.
root.right = Node(4) # le fils droit de la racine.
root.left.right = Node(3) # le fils droit du fils gauche de la racine.
root.left.right.right = Node(5)
# le fils droit du fils droit du fils gauche de la …
# Permet de voir notre arbre racine.
print(root)
____1
/ \
2 4
\
3
\
5
On peut aussi créer l’arbre à partir d’une liste.
from binarytree import build
# Build a tree from list representation
values = [ 7 , 3 , 2 , 6 , 9 , None , 1 , 5 , None ,
10 , 8 , None , None , 11 , None , 12 , 13 , None , None ,14 ]
root = build(values)
print(root)
__________7
/ \
3______ 2___
/ \ \
___6 _9 _1
/ / \ /
_5 _10 8 11
/ \ /
12 13 14
6.4.2. Parcours d’arbre#
Il existe différentes façon de parcourir un arbre.
6.4.2.1. Parcours préfixe d’un arbre#
Observons un premier parcours, avec les fonctions «builtin» du module.
arbre2 = build(values)
print(arbre2,arbre2.preorder)
__________7
/ \
3______ 2___
/ \ \
___6 _9 _1
/ / \ /
_5 _10 8 11
/ \ /
12 13 14
[Node(7), Node(3), Node(6), Node(5), Node(12), Node(13), Node(9), Node(10), Node(14), Node(8), Node(2), Node(1), Node(11)]
Que peut-on dire de ce parcours ?
Écrire une fonction préfixe qui permet de parcourir un arbre de cette
façon.
Show code cell content
def prefixe(arbre, parcours = []):
parcours.append(arbre.value)
if arbre.left != None:
prefixe(arbre.left, parcours)
if arbre.right != None:
prefixe(arbre.right, parcours)
return parcours
L’appel de cette fonction sera le suivant :
prefixe(arbre2)
[7, 3, 6, 5, 12, 13, 9, 10, 14, 8, 2, 1, 11]
6.4.2.2. Parcours postfixe d’un arbre#
print(arbre2.postorder)
[Node(12), Node(13), Node(5), Node(6), Node(14), Node(10), Node(8), Node(9), Node(3), Node(11), Node(1), Node(2), Node(7)]
Que peut-on dire de ce parcours ?
Coder une fonction récursive postfixe.
Show code cell content
def postfixe(arbre, parcours = []):
if arbre.left != None:
postfixe(arbre.left, parcours)
if arbre.right != None:
postfixe(arbre.right, parcours)
parcours.append(arbre.value)
return parcours
L’appel de cette fonction sera le suivant :
postfixe(arbre2)
[12, 13, 5, 6, 14, 10, 8, 9, 3, 11, 1, 2, 7]
6.4.2.3. Parcours infixe d’un arbre#
arbre2.inorder
[Node(12),
Node(5),
Node(13),
Node(6),
Node(3),
Node(14),
Node(10),
Node(9),
Node(8),
Node(7),
Node(2),
Node(11),
Node(1)]
Que peut-on dire de ce parcours ?
Coder une fonction récursive infixe.
Show code cell content
def infixe(arbre, parcours = []):
if arbre.left != None:
infixe(arbre.left, parcours)
parcours.append(arbre.value)
if arbre.right != None:
infixe(arbre.right, parcours)
return parcours
L’appel de cette fonction sera le suivant :
infixe(arbre2)
[12, 5, 13, 6, 3, 14, 10, 9, 8, 7, 2, 11, 1]
6.4.2.4. Parcours par niveau#
arbre2.levelorder
[Node(7),
Node(3),
Node(2),
Node(6),
Node(9),
Node(1),
Node(5),
Node(10),
Node(8),
Node(11),
Node(12),
Node(13),
Node(14)]
Que peut-on dire de ce parcours ?
Coder une telle fonction. On peut utiliser une file.
Show code cell content
def parcours(arbre):
file = []
res = []
file.append(arbre)
while len(file) > 0:
voisin = file.pop(0)
res = res + [voisin]
if voisin.left is not None:
file.append(voisin.left)
if voisin.right is not None:
file.append(voisin.right)
return res
La fonction s’utilise ainsi.
parcours(arbre2)
[Node(7),
Node(3),
Node(2),
Node(6),
Node(9),
Node(1),
Node(5),
Node(10),
Node(8),
Node(11),
Node(12),
Node(13),
Node(14)]