Structures de données et de fichiers
|
Enoncé 39. Arbres de recherche binaire, Piles Corrigé 39
Problème : Image miroir d'un arbre de recherche binaire.
Soit A un arbre de recherche binaire d’entiers. On définit l’IMAGE MIROIR de A comme étant l’arbre avec la meme racine tel que toutes les informations dans le sous arbre gauche de tout nœud avec l’information x sont strictement supérieures à x et toutes les informations dans le sous droit de tout nœud avec l’information x soit strictement inférieures à x.1. Donner un algorithme RECURSIF qui transforme un arbre de recherche binaire en son image miroir sans création de nœuds.
2. Soit le module Z suivant NON RECURSIF AVEC PILE qui liste tous les éléments de A en Préordre :
{ Parcours préordre avec pile }
ACTION Preordre ( A ) ;
SOIT
A , P DES ARB ;
Pil UNE PILE DE ARB ;
Possible UN BOOLEEN ;
DEBUT
ECRIRE ( 'Parcour préordre ...' ) ;
CREERPILE ( Pil ) ;
P := A ;
Possible := VRAI ;
TQ Possible :
TQ P <> NIL :
ECRIRE
( INFO ( P ) ) ;
EMPILER
( Pil , P ) ;
P
:= FG ( P )
FTQ ;
SI NON PILEVIDE ( Pil )
:
DEPILER
( Pil , P ) ;
P
:= FD ( P )
SINON
Possible
:= FAUX
FSI
FTQ
FIN
Que faut-il rajouter à cet algorithme pour qu’il fournisse également la profondeur de l’arbre ?
Que faut-il rajouter à cet algorithme pour qu’il transforme également A en son image miroir ?
N.B
Formule du pré ordre : N T1 T2, c’est à dire visiter la racine, ensuite tous les nœuds du sous arbre gauche T1 en préordre, enfin tous les nœuds du sous arbre droit T2 en pré ordre.
La profondeur d’un arbre est le niveau maximal de ses feuilles.
3. L’algorithme qui suit ( module Z) donne tous les éléments de A se trouvant dans l’intervalle [V1, V2] en ORDRE CROISSANT ( V1 et V2 étant deux entiers données pouvant ne pas appartenir à l’arbre A. Complétez-le en remplaçant les … soit par des affectations soit par des conditionnelles ( ou alternatives). L’utilisation d’exemples est cruciale afin de compléter cet algorithme
/* Recherche de v1 */
P := A
Trouv := FAUX
TANTQUE ( P <> NIL ) ET NON Trouv :
Q := P
SI V1 = INFO ( P )
Trouv := VRAI
SINON
SI INFO ( P ) > V1
P
:= FG ( P )
SINON
P
:= FD ( P )
FSI
FSI
FTANTQUE
SI Trouv
ECRIRE ( V1 )
SINON
1. ...
2....
FSI
Continue := VRAI
TANTQUE Continue ET ( P <> NIL )
SI FD ( P ) <> NIL
3. ....
TANTQUE P <> NIL
Q
:= P
P
:= FG ( P )
FTANTQUE
SI INFO ( Q ) <= V2
ECRIRE
( INFO ( Q ) )
FSI
4. ...
SINON
Remonter := VRAI
TANTQUE Remonter ET
Continue
Q
:= PERE ( P )
SI
Q = NIL
5.
...
SINON
6.
...
FSI
FTANTQUE
SI Continue :
SI
INFO ( Q ) <= V2
ECRIRE
( INFO ( Q ) )
7.
...
SINON
Continue
:= FAUX
FSI
FSI
FSI
FTANTQUE
N.B. L’opération Pére(p) donne le père du nœud
référencé par n.
