Construction d'arbres binaires

D'après 2022, Polynésie, J1, Ex. 5

On manipule ici les arbres binaires avec trois fonctions :

  • est_vide(A) renvoie True si l'arbre binaire A est vide, False s'il ne l'est pas ;

  • Pour un arbre binaire A non vide :

    • sous_arbre_gauche(A) renvoie le sous-arbre à gauche de A ;
    • sous_arbre_droite(A) renvoie le sous-arbre à droite de A.

L'arbre binaire renvoyé par les fonctions sous_arbre_gauche et sous_arbre_droite peut éventuellement être l'arbre vide.

On définit la hauteur d'un arbre binaire de la façon suivante :

  • la hauteur de l'arbre vide est \(0\) ;
  • sinon, la hauteur est égale à \(1 + M\), où \(M\) est la plus grande des hauteurs de ses sous-arbres (à gauche et à droite).

1.a. Donner la hauteur de l'arbre ci-dessous.

graph TD
    N0( ) --> N2( )
    N0   --> N1( )
    N2  --> N5( )
    N2  --> N6( )
    linkStyle 3 stroke-width:0px;
    style N6 opacity:0;
Réponse

Avec cette définition, la hauteur de cet arbre binaire est 3.

1.b. Dessiner sur la copie un arbre binaire de hauteur \(5\).

Réponse

Avec cette définition, voici un arbre binaire de hauteur \(5\).

graph TD
    N0( ) --> N1( )
    N0   --> N2( )
    N1  --> N3( )
    N1  --> N4( )
    N2  --> N5( )
    N2  --> N6( )
    N4  --> N7( )
    N4  --> N8( )
    N7  --> N9( )
    N7  --> N10( )
    linkStyle 7 stroke-width:0px;
    style N8 opacity:0;
    linkStyle 4 stroke-width:0px;
    style N5 opacity:0;

La hauteur d'un arbre est calculée par l'algorithme récursif suivant :

Pseudo Code
1
2
3
4
5
6
7
8
Algorithme hauteur(A) :
    si A vide :
        renvoyer ...
    sinon:
        renvoyer 1 + max(
            hauteur(sous_arbre_gauche(A)),
            ...
        )

2. Recopier sur la copie les lignes 3 et 7 en complétant les points de suspension.

Réponse
Pseudo Code
1
2
3
4
5
6
7
8
Algorithme hauteur(A) :
    si A vide :
        renvoyer 0
    sinon:
        renvoyer 1 + max(
            hauteur(sous_arbre_gauche(A)),
            hauteur(sous_arbre_droite(A)),
        )

On considère un arbre binaire R dont on note G le sous-arbre à gauche et D le sous-arbre à droite. On suppose que R est de hauteur \(5\) et G de hauteur \(3\).

3.a. Justifier le fait que D n'est pas l'arbre vide et déterminer sa hauteur.

Réponse

Si D est égal à l'arbre vide, alors la hauteur de R est égale à 1 + hauteur(G) qui est égal à \(1+3=4\), or R est de hauteur \(5\). Contradiction.

Ainsi D n'est pas l'arbre vide.

Dans ce cas 1 + max(hauteur(G), hauteur(D)) est égal à \(4\). D'où

  • 1 + max(3, hauteur(D)) est égal à \(5\).
  • max(3, hauteur(D)) est égal à \(4\).
  • hauteur(D) est égal à \(4\).

3.b. Illustrer cette situation par un dessin.

Réponse
  • Cet arbre est de hauteur \(5\),
  • son sous arbre à gauche est de hauteur \(3\),
  • son sous arbre à droite est de hauteur \(4\).
graph TD
    N0( ) --> N1( )
    N0   --> N2( )
    N1  --> N3( )
    N1  --> N4( )
    N2  --> N5( )
    N2  --> N6( )
    N4  --> N7( )
    N4  --> N8( )
    N6  --> N9( )
    N6  --> N10( )
    N9  --> N11( )
    N9  --> N12( )
    linkStyle 7 stroke-width:0px;
    style N8 opacity:0;
    linkStyle 4 stroke-width:0px;
    style N5 opacity:0;

Soit un arbre binaire non vide de hauteur h. On note n le nombre de nœuds de cet arbre. On admet que \(h \leqslant n \leqslant 2^h - 1\).

4.a. Vérifier ces inégalités sur l'arbre binaire de la question 1.a..

Réponse

Dans la question 1.a., l'arbre binaire possède \(n = 4\) nœuds et a une hauteur \(h = 3\).

On a bien \(3 \leqslant 4 \leqslant 2^3 - 1\) qui s'écrit aussi \(3 \leqslant 4 \leqslant 7\)

4.b. Expliquer comment construire un arbre binaire de hauteur h quelconque ayant h nœuds.

Réponse

Il suffit, par exemple, de construire un arbre binaire où pour chaque nœud, soit le sous arbre à gauche est vide, soit celui à droite.

  • Cela peut être toujours celui à gauche qui est vide, on parle alors d'arbre peigne à droite.
  • Cela peut être toujours celui à droite qui est vide, on parle alors d'arbre peigne à gauche.

4.c. Expliquer comment construire un arbre binaire de hauteur h quelconque ayant \(2^h - 1\) nœuds.

Indication : \(2^h - 1 = 1+2+4+...+2^{h-1}\).

Réponse

Il faut, dans ce cas, construire un arbre binaire complet ; les sous-arbres vides sont tous à la même profondeur.

L'objectif de la fin de l'exercice est d'écrire le code d'une fonction fabrique(h, n) qui prend comme paramètres deux nombres entiers positifs h et n tels que \(h < n < 2^h - 1\), et qui renvoie un arbre binaire de hauteur h à n nœuds.

Pour cela, on utilise les deux fonctions suivantes :

  • arbre_vide(), qui renvoie un arbre vide ;
  • arbre(gauche, droite) qui renvoie l'arbre de fils à gauche gauche et de fils à droite droite.

5. Recopier sur la copie l'arbre binaire ci-dessous et numéroter ses nœuds de 1 en 1 en commençant à 1, en effectuant un parcours en profondeur préfixe.

graph TD
    N0( ) --> N2( )
    N0   --> N1( )
    N1 --> N3( )
    N1 --> N4( )
    N2  --> N5( )
    N2  --> N6( )
    linkStyle 5 stroke-width:0px;
    style N6 opacity:0;
    N3 --> N7( )
    N3 --> N8( )
    N4 --> N9( )
    N4 --> N10( )
Réponse 
graph TD
    N0(1) --> N2(9)
    N0   --> N1(2)
    N1 --> N3(3)
    N1 --> N4(6)
    N2  --> N5(10)
    N2  --> N6( )
    linkStyle 5 stroke-width:0px;
    style N6 opacity:0;
    N3 --> N7(4)
    N3 --> N8(5)
    N4 --> N9(7)
    N4 --> N10(8)

La fonction fabrique ci-dessous a pour but de répondre au problème posé.

🐍 Script Python
def fabrique(h, n):
    if n == 0:
        return ...
    else:
        reste = n - 1                    # 1 pour la racine du sous-arbre
        n_gauche = min(reste, ...)       # le plus possible à gauche
        n_droite = reste - n_gauche      # la suite à droite
        return arbre(
            fabrique(..., n_gauche),
            ...
        )

6. Recopier sur la copie les lignes 3, 6 et 9 en complétant les points de suspension.

Réponse
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def arbre_vide():
    return []

def arbre(gauche, droite):
    return [gauche, droite]

def fabrique(h, n):
    if n == 0:
        return arbre_vide()
    else:
        reste = n - 1                        # 1 pour la racine du sous-arbre
        n_gauche = min(reste, 2**(h-1) - 1)  # le plus possible à gauche
        n_droite = reste - n_gauche          # la suite à droite
        return arbre(
            fabrique(h-1, n_gauche),
            fabrique(h-1, n_droite)
        )

def taille(arbre):
    if arbre == []:
        return 0
    else:
        gauche, droite = arbre
        return 1 + taille(gauche) + taille(droite)

def hauteur(arbre):
    if arbre == []:
        return 0
    else:
        gauche, droite = arbre
        return 1 + max(hauteur(gauche), hauteur(droite))


for h in range(4):
    print("Hauteur", h)
    for n in range(h, 2**h):
        n_sav = n
        arbre_hn = fabrique(h, n)
        print(arbre_hn)
        assert (h, n_sav) == (hauteur(arbre_hn), taille(arbre_hn))
    print()

On peut tester le code et obtenir

🐍 Console Python
>>> %Run fabrique_arbres.py
Hauteur 0
[]

Hauteur 1
[[], []]

Hauteur 2
[[[], []], []]
[[[], []], [[], []]]

Hauteur 3
[[[[], []], []], []]
[[[[], []], [[], []]], []]
[[[[], []], [[], []]], [[], []]]
[[[[], []], [[], []]], [[[], []], []]]
[[[[], []], [[], []]], [[[], []], [[], []]]]

>>>