Exercice 3 · Bac Numérique et Sciences Informatiques Centres étrangers (Afrique) 2021 (jour 1)

Exercice 3

Notion abordée: les arbres binaires de recherche.

Un arbre binaire est soit vide, soit un nœud qui a une valeur et au plus deux fils (le sous-arbre gauche et le sous-arbre droit).

$X$ est un nœud, sa valeur est $X\text{.valeur}$

$G1$ est le fils gauche de $X$, noté $X\text{.fils\_gauche}$

$D1$ est le fils droit de $X$, noté $X\text{.fils\_droit}$

Un arbre binaire de recherche est ordonné de la manière suivante:

Pour chaque nœud $X$,

les valeurs de tous les nœuds du sous-arbre gauche sont strictement inférieures à la valeur du nœud $X$

les valeurs de tous les nœuds du sous-arbre droit sont supérieures ou égales à la valeur du nœud $X$

Ainsi, par exemple, toutes les valeurs des nœuds $G1$, $G2$ et $G3$ sont strictement inférieures à la valeur du nœud $X$ et toutes les valeurs des nœuds $D1$, $D2$ et $D3$ sont supérieures ou égales à la valeur du nœud $X$.

Voici un exemple d'arbre binaire de recherche dans lequel on a stocké dans cet ordre les valeurs:

$[26, 3, 42, 15, 29, 19, 13, 1, 32, 37, 30]$

L'étiquette d'un nœud indique la valeur du nœud suivie du nom du nœud.

Les nœuds ont été nommés dans l'ordre de leur insertion dans l'arbre ci-dessous.

'29, noeud04' signifie que le nœud nommé noeud04 possède la valeur 29.

1.

On insère la valeur 25 dans l'arbre, dans un nouveau nœud nommé noeud11.

Recopier l'arbre binaire de recherche étudié et placer la valeur 25 sur cet arbre en coloriant en rouge le chemin parcouru.

Préciser sous quel nœud la valeur 25 sera insérée et si elle est insérée en fils gauche ou en fils droit, et expliquer toutes les étapes de la décision.

2.

Préciser toutes les valeurs entières que l'on peut stocker dans le nœud fils gauche du nœud04 (vide pour l'instant), en respectant les règles sur les arbres binaires de recherche ?

3.

Voici un algorithme récursif permettant de parcourir et d'afficher les valeurs de l'arbre:

Parcours(A) # A est un arbre binaire de recherche

Afficher(A.valeur)

Parcours(A.fils_gauche)

Parcours(A.fils_droit)

3.a. Écrire la liste de toutes les valeurs dans l'ordre où elles seront affichées.

3.b. Choisir le type de parcours d'arbres binaires de recherche réalisé parmi les propositions suivantes: Préfixe, Suffixe ou Infixe

4.

En vous inspirant de l'algorithme précédent, écrire un algorithme Parcours2 permettant de parcourir et d'afficher les valeurs de l'arbre A dans l'ordre croissant.