SDD Question 3 Juin 2013

1) 4-2-1+8+5+7+1 = 22

2)
Entrée: Un arbre binaire T contenant des nombres entiers.
        Un naturel p représentant une profondeur.
        Un naturel c représentant la profondeur courante.
Sortie: La somme des entiers de l'arbre T dont la profondeur est >= p.
Effet : /

algo_in(T, p, c)
    si T est non vide alors
        si p <= c alors
            retourner T.data + algo_in(T.gauche, p, c+1) + algo_in(T.droit, p, c+1)
        sinon
            retourner algo_in(T.gauche, p, c+1) + algo_in(T.droit, p, c+1)
    sinon
        retourner 0

Entrée: Un arbre binaire T contenant des nombres entiers.
        Un naturel p représentant une profondeur.
Sortie: La somme des entiers de l'arbre T dont la profondeur est >= p.
Effet : /

algo(T, p)
    retourner algo_in(T, p, 0)

3)

Pour un noeud, la complexité est en O(1), pour une référence vide, la complexité est en O(1).
Soit n le nombre de noeuds de l'arbre T, on a vu au cours que l'arbre T a alors n+1 référence vide car
c'est un arbre binaire.
Par une formule vue au cours, la complexité de cet algorithme est donnée par:

n*O(1) + (n+1)*O(1) = O(n) par les régles de calcul sur les O.