Parcours en largeur d'un arbre binaire

Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un nœud représenté par un triplet (g, x, d) où x est l’étiquette du nœud et g et d sont les sous-arbres gauche et droit.

On souhaite écrire une fonction parcours_largeur qui prend en paramètre un arbre binaire et qui renvoie la liste des étiquettes des nœuds de l’arbre parcourus en largeur.

Exemple

🐍 Console Python

>>> arbre = ( ( (None, 1, None), 2, (None, 3, None) ), 4, ( (None, 5, None), 6, (None, 7, None) ) )
>>> parcours_largeur(arbre)
[4, 2, 6, 1, 3, 5, 7]

Compléter le code ci-dessous

###

Lancer # Testsbksl-nlarbre = ( ( (None, 1, None), 2, (None, 3, None) ), 4, ( (None, 5, None), 6, (None, 7, None) ) )bksl-nlassert parcourspy-undlargeur(arbre) == [4, 2, 6, 1, 3, 5, 7]bksl-nlbksl-nl# Autres testsbksl-nl arbrepy-und2 = ( ( (None, 11, None), 12, (None, 13, None) ), 4, ( (None, 15, None), 16, (None, 17, None) ) )bksl-nlparcourspy-undlargeur(arbrepy-und2) == [4, 12, 16, 11, 13, 15, 17]bksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def parcourspy-undlargeur(arbre):bksl-nl ...bksl-nlbksl-nl# Testsbksl-nlbksl-nlarbre = ( ( (None, 1, None), 2, (None, 3, None) ), 4, ( (None, 5, None), 6, (None, 7, None) ) )bksl-nlassert parcourspy-undlargeur(arbre) == [4, 2, 6, 1, 3, 5, 7]bksl-nlbksl-nldef parcourspy-undlargeur(arbre):bksl-nl parcours = []bksl-nl file = [arbre]bksl-nl while file != []:bksl-nl a = file.pop(0)bksl-nl parcours.append(a[1])bksl-nl if a[0] != None:bksl-nl file.append(a[0])bksl-nl if a[2] != None:bksl-nl file.append(a[2])bksl-nl return parcoursbksl-nl bksl-nl

---

---