Devoir sur les arbres binaires

L'usage de la calculatrice n'est pas autorisé.

Durée : 1 heure

Dans tout le devoir, on utilisera la classe Noeud vue en classe:

class Noeud:
    def __init__(self, *args):
        if len(args) == 0:
            self.contenu = None
        else:
            self.contenu = (args[0], args[1], args[2])
    def etiquette (self):
        return(self.contenu[0])
    def gauche(self):
        return(self.contenu[1])
    def droit(self):
        return(self.contenu[2])
    def est_vide(self):
        return  self.contenu == None

Exercice 1

Soit l'arbre binaire suivant:

SujetCorrigé

Écrire une commande qui permet de déclarer cet arbre.

A=Noeud(1,Noeud(2,Noeud(3,Noeud(),Noeud()),Noeud(4,Noeud(),Noeud())),Noeud(5,Noeud(),Noeud()))

Exercice 2

SujetCorrigé

Donner 3 arbres de taille 3, différents, dont les noeuds contiennent les étiquettes 1, 2, 3 et pour lesquels la fonction parcours_postfixe affiche:

1
2
3

graphiques

Exercice 3

SujetCorrigé

Écrire une fonction récursive qui renvoie True si un arbre est filiforme et False sinon.

def est_filiforme(A):
    if A.est_vide():
        return True
    else:
        if A.gauche().est_vide():
            return est_filiforme(A.droit())
        if A.droit().est_vide():
            return est_filiforme(A.gauche())
        return False

Exercice 4

SujetCorrigé

On dit qu'un arbre est un peigne gauche si le fils droit de chaque noeud est vide. On définit de même les peignes droits.

Écrire une fonction peigne qui retourne le peigne gauche de taille \(n\) donnée. Pour les valeurs on prendra les entiers de \(1\) à \(n\).

def peigne(n):
    if n==1:
        return Noeud(1,Noeud(),Noeud())
    else:
        return Noeud(n,peigne(n-1),Noeud())

Exercice 5

SujetCorrigé

Écrire une fonction SommeInterne qui retourne la somme des étiquettes non feuilles dans l’arbre.

def SommeInterne(A):
    if A.est_vide():
        return 0
    if A.gauche().est_vide() and A.droit().est_vide():
        return 0
    else:
        return A.etiquette()+SommeInterne(A.gauche())+SommeInterne(A.droit())