Enoncé 43.  Arbre de recherche binaire.   Corrigé 43

Problème : Exploration des niveaux d'un arbre de recherche binaire

Ecrire la fonction récursive Premier(x, R) qui donne le premier nœud, s'il existe, du niveau x de d'un arbre de recherche binaire R.

Soit n un nœud du niveau i. On définit les ascendants gauches du nœud n tout nœud se trouvant sur le chemin de n à la racine par lequel on remonte par la gauche. Ecrire le module Ascendant_gauche (n, i, n', i') qui détermine le plus jeune ascendant gauche n', s'il existe, du nœud n de niveau i qui a un fils droit. Ce module donne également le niveau i' du nœud n'. On utilisera le module PERE.

Utiliser Premier(x, R) et Ascendant_gauche (n, i, n', i') pour écrire la fonction Suiv(A, i) qui donne le prochain nœud du niveau i, s'il existe, à droite d'un nœud donné A de niveau i.

Ecrire le module Lister (P, Niv) qui liste tous les nœuds, s'ils existent, à droite de P du niveau Niv dans le même niveau.

Voici un exemple d'algorithme principal qui fait appel à tous les modules demandés

Soient
    A , P , Q, Pprime Des Arb ; Xprime, Niv Des Entiers ;
    Soient Premier, Suiv des Fonctions ( Arb ) ;
    Soient Ascendant_gauche, Lister des Action ;
Debut
    Creer_arb ( A , [ 30 , 20 , 60 , 15 , 18 , 12 , 19 , 17 , 80 , 70 , 74 , 76 , 78 , 92 ] ) ;
    Lire ( Niv ) ;
    P := Premier ( Niv , A ) ;
    Si P <> Nil
        Ecrire ( Info ( P ) ) ;
        Appel Ascendant_gauche ( P , Niv , Pprime , Xprime ) ;
        Si Pprime <> Nil
            Ecrire ( Info ( Pprime ) , Xprime )
        Sinon
            Ecrire ( 'Echec' ) ;
        Fsi ;
        Q := Suiv(P, Niv);
        Si Q <> Nil : Ecrire ( Info ( Q ) ) Sinon Ecrire ( 'Echec' ) ; Fsi ;        Appel Lister ( P, niv ) ;
    Sinon
        Ecrire ( 'Echec' )
    Fsi
Fin

Pour l'arbre généré, PREMIER(3, A) donne l'adresse du nœud 12. PREMIER(5, A) donne l'adresse du nœud 76. PREMIER(0, A) donne l'adresse du nœud 30. PREMIER(8, 0) donne le message 'Echec'. Le nœud avec la valeur 17 admet comme ascendant gauche les nœuds avec les valeurs 18, 20 et 30. 18 étant le plus jeune. Si n est l'adresse de 17 de niveau i =4 alors Ascendant(n, i, n', i') donne comme valeur n' : l'adresse de 18 et i' la valeur 3. Si n est l'adresse de 19 de niveau i =4 alors Ascendant(n, i, n', i') donne comme valeur n' : l'adresse de 30 et i' la valeur 0. Si n est l'adresse de 74 de niveau i =4 alors Ascendant(n, i, n', i') donne le message 'Echec'. Si n est l'adresse de 18 de niveau i =3 alors Suiv(n, 3) donne le nœud avec la valeur 70. Si n est le nœud avec la valeur 12, Lister(P, 3) donne 18, 70 et 92. Si n est le nœud avec la valeur 15, Lister(P, 2) donne 80.