Définitions (Bac 🎯)

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

• le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
• le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
• l'article sur les arbres en NSI de Sébastien Hoarau
• le cours de mon collègue Pierre Duclosson
• le cours de Gilles Lassus
• le cours de Franck Chambon

🔖 Synthèse de ce qu'il faut retenir pour le bac

Définitions

Point de cours 1 : arbre binaire

Un arbre binaire est un ensemble fini de noeuds. Cet ensemble peut être vide.

Un noeud d'arbre binaire est constitué de trois champs :

• un champ d'information contient un élément
• un premier champ enfant contient un lien appelé fils gauche vers un autre noeud ou une valeur représentant l'absence de noeud
• un second champ enfant contient un lien appelé fils droit vers un autre noeud ou une valeur représentant l'absence de noeud

Un noeud d'arbre binaire a toujours deux enfants

Un noeud d'arbre binaire est normalement toujours représenté avec ses deux enfants même s'ils sont vides.

On peut alors définir un arbre binaire de façon récursive :

• soit c'est l'arbre vide s'il ne contient aucun noeud
• soit il est constitué d'un noeud spécial appelé racine de l'arbre dont le fils droit et le fils gauche sont des arbres binaires

Le fils gauche non vide d'un arbre binaire non vide est appelé sous-arbre gauche.

Le fils droit non vide d'un arbre binaire non vide est appelé sous-arbre droit.

Distinction entre fils gauche et droit

Attention, il faut bien distinguer le fils gauche et le fils droit : il existe deux structures d'arbre binaire distinctes avec deux noeuds.

Arbres binaires homogènes ou pas

En général, comme pour les structures linéaires, nous construirons des arbres binaires stockant des éléments de même type. Mais ce ne sera pas le cas pour les arbres de calcul comme celui-présenté dans l'introduction des structures arborescentes.

Exercice 1

💻 Saisir ses réponses sur Capytale

énoncésolution

1. Représenter tous les arbres binaires ayant trois nœuds.
2. Représenter tous les arbres binaires ayant quatre nœuds.

On a cinq arbres binaires avec trois noeuds.

On a 14 arbres binaires avec quatre noeuds.

:

Le nombre d'arbres binaires à \(n\) noeuds est le \(n^{ième}\) nombre de Catalan. Retrouver la formule de récurrence est un bon exercice de dénombrement. Ci-dessous une fonction pour renvoyer un tableau contenant tous les arbres binaires de taille \(n\).

🐍 Script Python

def enumeration_arbres(n):
    if n == 0:
        return [None]
    preced = [enumeration_arbres(k) for k in range(n)]
    tab = []
    for k in range(n):
        for sag in preced[k]:
            for sad in preced[n - 1 - k]:
                tab.append(Noeud(sag, '', sad))
    return tab

Point de cours 2 : noeuds

L'accès aux éléments stockés dans un arbre binaire non vide s'effectue par le noeud spécial appelé racine.

Il existe une unique chaîne reliant par des liens de filiation, le noeud racine à un autre noeud.

Un noeud qui a au moins un enfant est appelé noeud interne.

Un noeud qui n'a aucun enfant (ni fils gauche, ni fils droit) est appelé feuille.

Exercice 2

💻 Saisir ses réponses sur Capytale

énoncésolution

1. Représenter tous les arbres binaires qui ont trois noeuds mais une seule feuille.
2. Représenter tous les arbres binaires qui ont quatre noeuds mais une seule feuille.
3. Combien existe-t-il d'arbres binaires qui ont \(n \geqslant 1\) noeuds mais une seule feuille.

1. On a \(1 \times 2 \times 2 = 4\) arbres binaires dégénérés avec trois noeuds et une seule feuille.
2. On a \(1 \times 2 \times 2 \times 2 = 8\) arbres binaires dégénérés avec trois noeuds et une seule feuille.
3. Pour \(n \geqslant 1\), on a \(2^{n-1}\) arbres binaires dégénérés avec \(n\) noeuds et une seule feuille. A chaque niveau supplémentaire on multiplie par \(2\) le nombre de possibilités.