11 février 2014 Cours d'algorithmique 3 - Intranet 1 Cours dAlgorithmique Arbres. Parcours darbres

11 février 201411 février 2014 Cours d'algorithmique 3 - IntranetCours d'algorithmique 3 - Intranet 11

Cours Cours d’Algorithmiqued’Algorithmique

Arbres.Arbres.

Parcours d’arbres.Parcours d’arbres.


Les arbres enracinésLes arbres enracinés------------------------------------------------------------------------------------------------------------------------------

----racineracine

Il y a un nœud qui est la racine .Il y a un nœud qui est la racine .

Il y a une orientation de laIl y a une orientation de laracine vers les autres.racine vers les autres.


Les arbres valuésLes arbres valués------------------------------------------------------------------------------------------------------------------------------

----racineracine

Les feuilles sont les extrémités de Les feuilles sont les extrémités de l’arbre.l’arbre.

Du point de vue de l’arbre, ellesDu point de vue de l’arbre, ellessont atomiques (sanssont atomiques (sans

successeur).successeur).

Concernant l’application,Concernant l’application,elles comportentelles comportent

souvent dessouvent desvaleurs.valeurs.

55 1313


Il y a des nœuds (internes)Il y a des nœuds (internes)qui ont des « fils » enqui ont des « fils » en

nombre variable.nombre variable.

Chaque fils est à sonChaque fils est à sontour un arbre.tour un arbre.

ConcernantConcernantl’application,l’application,

les nœudsles nœudspeuventpeuvent

comportercomporterdes valeurs,des valeurs,

que l’on appelleque l’on appelleaussi des étiquettes.aussi des étiquettes.

Les arbres valuésLes arbres valués------------------------------------------------------------------------------------------------------------------------------

----racineracine

xx

++


Des sous-arbresDes sous-arbres------------------------------------------------------------------------------------------------------------------------------

----racineracine

Sous-arbres !Sous-arbres !


L E S A R B R E SL E S A R B R E S

S O U S F O R M ES O U S F O R M E

D E A . D . T .D E A . D . T .


Un arbre estUn arbre est soit, simplement une feuille :soit, simplement une feuille :

racineracine

soit, un nœud (racine) avec un ou plusieurs fils qui soit, un nœud (racine) avec un ou plusieurs fils qui sont des arbres (enracinés) à leur tour :sont des arbres (enracinés) à leur tour :

racineracine

arbre arbre arbrearbre arbre arbre

Définition des arbres comme ADTDéfinition des arbres comme ADT------------------------------------------------------------------------------------------------------------------------------

----


Les arbres enracinés binaires comme ADTLes arbres enracinés binaires comme ADT------------------------------------------------------------------------------------------------------------------------------

---- Création d’une feuille :Création d’une feuille :

cree_feuille : void -> Acree_feuille : void -> A

cree_feuille : int -> Acree_feuille : int -> A

• pour créer une feuille qui comporte une valeur entière,pour créer une feuille qui comporte une valeur entière,

• ainsi que valeur_feuille : A -> intainsi que valeur_feuille : A -> int

Création d’un nœud binaire :Création d’un nœud binaire :

cree_arbre : A x A -> Acree_arbre : A x A -> A

cree_arbre : A x int x A -> Acree_arbre : A x int x A -> A

• pour créer un nœud qui comporte une étiquette entière,pour créer un nœud qui comporte une étiquette entière,

• ainsi que : etiquette_arbre : A -> intainsi que : etiquette_arbre : A -> int


Les arbres enracinés binaires comme ADTLes arbres enracinés binaires comme ADT------------------------------------------------------------------------------------------------------------------------------

---- Distinction entre feuilles et noeuds :Distinction entre feuilles et noeuds :

est_feuille : A -> BOOLest_feuille : A -> BOOL

est_feuille( cree_feuille( ) ) = Vraiest_feuille( cree_feuille( ) ) = Vrai

est_feuille( cree_noeud( x , y ) ) = Fauxest_feuille( cree_noeud( x , y ) ) = Faux

Décomposition d’un nœud binaire :Décomposition d’un nœud binaire :

fils_gauche : A -> Afils_gauche : A -> A

fils_droit : A -> Afils_droit : A -> A

fils_gauche ( cree_arbre ( g , d ) ) = gfils_gauche ( cree_arbre ( g , d ) ) = g

fils_droit ( cree_arbre ( g , d ) ) = dfils_droit ( cree_arbre ( g , d ) ) = d


arbre_un = cree_arbre ( cree_feuille(5) , cree_feuille(7) );arbre_un = cree_arbre ( cree_feuille(5) , cree_feuille(7) );

arbre_deux = cree_arbre ( cree_feuille(2) ,arbre_deux = cree_arbre ( cree_feuille(2) ,

cree_arbre ( cree_arbre ( arbre_unarbre_un , ,

cree_feuille(1) ) );cree_feuille(1) ) );

arbre_trois = cree_arbre ( cree_feuille(3) , cree_feuille(7) );arbre_trois = cree_arbre ( cree_feuille(3) , cree_feuille(7) );

arbre = cree_arbre ( arbre = cree_arbre ( arbre_deuxarbre_deux , , arbre_troisarbre_trois ); );

55 77

11

22

Exemple d’arbres enracinés binairesExemple d’arbres enracinés binaires------------------------------------------------------------------------------------------------------------------------------

----

33 77


L E S A R B R E SL E S A R B R E S

E NE N

L A N G A G E CL A N G A G E C


Les arbres en langage CLes arbres en langage C------------------------------------------------------------------------------------------------------------------------------

---- Un pointeur sur un arbre est :Un pointeur sur un arbre est :

soit, un pointeur sur une feuille,soit, un pointeur sur une feuille,

soit, un pointeur sur un nœud.soit, un pointeur sur un nœud.

Il faut donc une structure capable de contenir les deux :Il faut donc une structure capable de contenir les deux :

les champs d’une feuille,les champs d’une feuille,

les champs d’un nœud,les champs d’un nœud,

un indicateur booléen qui distingue les deux cas de figure.un indicateur booléen qui distingue les deux cas de figure.

Les expressions arithmétiques comme exemple :Les expressions arithmétiques comme exemple :

toute feuille est un entier,toute feuille est un entier,

chaque nœud comporte un opérateur et deux sous-chaque nœud comporte un opérateur et deux sous-expressions.expressions.



----

typedef struct moi_memetypedef struct moi_meme

{int est_feuille;{int est_feuille;

int valeur;int valeur;

char etiq;char etiq;

struct moi_meme *fg;struct moi_meme *fg;

struct moi_meme *fd;struct moi_meme *fd;

}}

t_arbre, *t_ptr_arbre;t_arbre, *t_ptr_arbre;



----

int est_feuille (t_ptr_arbre arbre)int est_feuille (t_ptr_arbre arbre)

{return( arbre->est_feuille );{return( arbre->est_feuille );

}}

t_ptr_arbre cree_feuille (int val)t_ptr_arbre cree_feuille (int val)

{t_ptr_arbre arbre;{t_ptr_arbre arbre;

arbre = (t_ptr_arbre)malloc( sizeof( t_arbre ) );arbre = (t_ptr_arbre)malloc( sizeof( t_arbre ) );

arbre->est_feuille = 1;arbre->est_feuille = 1;

arbre->valeur = val;arbre->valeur = val;

return( arbre );return( arbre );

}}



----

t_ptr_arbre cree_noeud (t_ptr_arbre fg, t_ptr_arbre fd, t_ptr_arbre cree_noeud (t_ptr_arbre fg, t_ptr_arbre fd,

char sym)char sym)

{t_ptr_arbre arbre;{t_ptr_arbre arbre;

arbre = (t_ptr_arbre)malloc( sizeof( t_arbre ) );arbre = (t_ptr_arbre)malloc( sizeof( t_arbre ) );

arbre->est_feuille = 0;arbre->est_feuille = 0;

arbre->etiq = sym;arbre->etiq = sym;

arbre->fg = fg;arbre->fg = fg;

arbre->fd = fd;arbre->fd = fd;

return( arbre );return( arbre );

}}



----

t_ptr_arbre fils_gauche (t_ptr_arbre arbre)t_ptr_arbre fils_gauche (t_ptr_arbre arbre)

{assert( !est_feuille( arbre ) );{assert( !est_feuille( arbre ) );

return( arbre->fg );return( arbre->fg );

}}

t_ptr_arbre fils_droit (t_ptr_arbre arbre)t_ptr_arbre fils_droit (t_ptr_arbre arbre)

{assert( !est_feuille( arbre ) );{assert( !est_feuille( arbre ) );

return( arbre->fd );return( arbre->fd );

}}


L I S T E SL I S T E S

A R B R E S E T L EA R B R E S E T L E

P O I N T E U R N U L LP O I N T E U R N U L L


Listes, arbres et le pointeur NULLListes, arbres et le pointeur NULL------------------------------------------------------------------------------------------------------------------------------

----

Une liste peut être vide !Une liste peut être vide !

Elle sera représentée par le pointeur NULL !Elle sera représentée par le pointeur NULL !

La raison profonde est le fait que l’opération de base estLa raison profonde est le fait que l’opération de base est

la concaténation,la concaténation,

qui est associativequi est associative

et possède et possède la liste videla liste vide comme élément neutre ! comme élément neutre !

Nous avons les fonctions suivantes :Nous avons les fonctions suivantes :

cree_vide , est_vide ,cree_vide , est_vide ,

ajout_liste , tete_liste , queue_liste , ...ajout_liste , tete_liste , queue_liste , ...



---- Un arbre n’est jamais NULL !Un arbre n’est jamais NULL !

La raison profonde est le fait que l’opération de base La raison profonde est le fait que l’opération de base estest

la construction d’arbrela construction d’arbre

qui n’est pas associativequi n’est pas associative

et la question de l’élément neutre ne se pose même et la question de l’élément neutre ne se pose même pas !pas !Arbre ( A , Arbre ( B , C ) )Arbre ( A , Arbre ( B , C ) ) == Arbre ( Arbre ( A , B ) , C )Arbre ( Arbre ( A , B ) , C )//

AA

BB CC

CC

AA BB



---- Un arbre n’est jamais NULL !Un arbre n’est jamais NULL !

La raison profonde est le fait que l’opération de base estLa raison profonde est le fait que l’opération de base est

la construction d’arbrela construction d’arbre

qui n’est pas associativequi n’est pas associative

et la question de l’élément neutre ne se pose même pas !et la question de l’élément neutre ne se pose même pas !

Nous avons les fonctions suivantes :Nous avons les fonctions suivantes :

cree_feuille , cree_noeud ,cree_feuille , cree_noeud ,

est_feuille ,est_feuille ,

fils_gauche et fils_droit .fils_gauche et fils_droit .


P A R C O U R SP A R C O U R S

D ‘ A R B R E SD ‘ A R B R E S


Fibonnacci et les arbresFibonnacci et les arbres------------------------------------------------------------------------------------------------------------------------------

----

t_ptr_arbre arbre_fibo (int n)t_ptr_arbre arbre_fibo (int n)

{if ( n == 0 ){if ( n == 0 )

return( return( cree_feuille( 0 )cree_feuille( 0 ) ); );

elseelse

if ( n == 1 )if ( n == 1 )

return( return( cree_feuille( 1 )cree_feuille( 1 ) ); );

elseelse

return( return( cree_noeudcree_noeud( ( arbre_fibo( n-1 )arbre_fibo( n-1 ),,

arbre_fibo( n-2 )arbre_fibo( n-2 ) ) ) ; } ) ) ; }


Fibonnacci et les arbresFibonnacci et les arbres------------------------------------------------------------------------------------------------------------------------------

----

11 00

22

11 00

22 11

33

44

11 00

22 11

33

55

Nous observons aussi que de nombreux calculs sont répétés !Nous observons aussi que de nombreux calculs sont répétés !

arbre_fibo( 5 )arbre_fibo( 5 )


L A S O M M EL A S O M M E

D E S F E U I L L E SD E S F E U I L L E S

D E L ’ A R B R ED E L ’ A R B R E


Calcul de la somme des feuillesCalcul de la somme des feuilles------------------------------------------------------------------------------------------------------------------------------

----

int somme_arbre_fibo (t_ptr_arbre arbre)int somme_arbre_fibo (t_ptr_arbre arbre)

{if ( est_feuille(arbre) ){if ( est_feuille(arbre) )

return( return( valeur_feuille( arbre )valeur_feuille( arbre ) ); );

elseelse

return( return( somme_arbre_fibo( fils_gauche( arbre ) ) somme_arbre_fibo( fils_gauche( arbre ) )

++ somme_arbre_fibo( fils_droit( arbre ) )somme_arbre_fibo( fils_droit( arbre ) ) ) ; } ) ; }

Pour tout entier naturel n :Pour tout entier naturel n :

fibonnacci( n ) = somme_arbre_fibo o arbre_fibo ( n )fibonnacci( n ) = somme_arbre_fibo o arbre_fibo ( n )



----

11 00

22

11 00

22 11

33

44

11 00

22 11

33

55

sommme_sommme_arbre_fibo( arbre_fibo( 5 )5 )

11 00

1111

22 11

33

11

22

55= 5= 5



----

int somme_arbre_fibo (ptr_arbre arbre)int somme_arbre_fibo (ptr_arbre arbre)

{return( somme_acc( arbre , {return( somme_acc( arbre , 00 ) ) ; } ) ) ; }

int somme_acc(ptr_arbre arbre , int somme_acc(ptr_arbre arbre , int accumuleint accumule))

{if ( est_feuille( arbre ) ){if ( est_feuille( arbre ) )

return( return( accumuleaccumule + + valeur_feuille( arbre )valeur_feuille( arbre ) ); );

elseelse

return( somme_acc( return( somme_acc( fils_droit( arbre )fils_droit( arbre ) , ,

somme_acc( fils_gauche( arbre ) ,somme_acc( fils_gauche( arbre ) ,

accumule )accumule ) ) ) ; } ) ) ; }

Nous rajoutons unNous rajoutons unparamètreparamètre

d’accumulationd’accumulationinitialisé à 0 !initialisé à 0 !

La valeur de la feuille est ajoutée à l’accumulateur !La valeur de la feuille est ajoutée à l’accumulateur !

L’accumulateur ainsiL’accumulateur ainsi

enrichi est ensuite passé à la fonctionenrichi est ensuite passé à la fonction

qui explore le fils droit pour y rajouter les valeurs !qui explore le fils droit pour y rajouter les valeurs !



----

11 00

22

11 00

22 11

33

44

11 00

22 11

33

55

somme_somme_arbre_fibo( 5 arbre_fibo( 5 ))

11

accumule = 0accumule = 0

11

22 . . .. . .

accumule = 5accumule = 5= 5= 5

Tout se passe comme si les feuilles étaientTout se passe comme si les feuilles étaientrangées dans un tableau ou une liste !rangées dans un tableau ou une liste !


L EL E


E N P R O F O N D E U RE N P R O F O N D E U R

P R E F I X EP R E F I X E


Parcours en profondeurParcours en profondeuret préfixe !et préfixe !

res_fgres_fg = = appel ( fg(a) );appel ( fg(a) );

res_fdres_fd = = appel ( fd(a) );appel ( fd(a) );

return( ... return( ... res_fgres_fg ... ... res_fdres_fd ... ); ... );

Types de parcoursTypes de parcours------------------------------------------------------------------------------------------------------------------------------

----


L EL E



S U F F I X ES U F F I X E


Parcours en profondeurParcours en profondeuret suffixe ( postfixe ) !et suffixe ( postfixe ) !

res_fd = appel ( res_fd = appel ( fd(a)fd(a) ); );

res_fg = appel ( res_fg = appel ( fg(a)fg(a) ); );

return( ... res_fg ... res_fd ... );return( ... res_fg ... res_fd ... );


----

Nous parcourons d’abordNous parcourons d’abordle fils droit et ensuitele fils droit et ensuite

le fils gauche !le fils gauche !


L EL E




Parcours avec un opérateur commutatif :Parcours avec un opérateur commutatif :

L’ordre de parcours est sans importance !L’ordre de parcours est sans importance !

... oper_commute ( ... oper_commute ( fgfg(a) , (a) , fdfd(a) ) ...(a) ) ...

... oper_commute ( ... oper_commute ( fdfd(a) , (a) , fgfg(a) ) ...(a) ) ...


----


L E P A R C O U R SL E P A R C O U R S


A V E CA V E C

E T I Q U E T T EE T I Q U E T T E


Traitement de l’étiquette, soit Traitement de l’étiquette, soit avantavant , soit après , soit pendant ! , soit après , soit pendant !

11 55

++ 33

**

Types de parcours avec étiquettesTypes de parcours avec étiquettes------------------------------------------------------------------------------------------------------------------------------

----

Impression préfixe de Impression préfixe de l’arbre :l’arbre :

** ++ 1 1 55 33


Traitement de l’étiquette, soit Traitement de l’étiquette, soit avantavant , soit , soit aprèsaprès , soit pendant ! , soit pendant !

11 55

++ 33

**


----

Impression préfixe de l’arbre :Impression préfixe de l’arbre :

** ++ 1 1 55 33

Impression postfixe de l’arbre Impression postfixe de l’arbre ::

1 1 55 ++ 3 3 **


Traitement de l’étiquette, soit Traitement de l’étiquette, soit avantavant , soit , soit aprèsaprès , soit , soit pendantpendant ! !

11 55

++ 33

**


----

Impression préfixe de l’arbre :Impression préfixe de l’arbre :

** ++ 1 1 55 33

Impression postfixe de l’arbre :Impression postfixe de l’arbre :

1 1 55 ++ 3 3 **

Impression infixe parenthésée :Impression infixe parenthésée :

( ( ( ( 1 1 ++ 55 ) ) * * 3 3 ))

(( ))

))((


L EL E


E N L A R G E U RE N L A R G E U R


Le parcours en largeur se fait à l’aide d’une file :Le parcours en largeur se fait à l’aide d’une file :

Le nœud à traiter est au début de la file !Le nœud à traiter est au début de la file !

Les nouveaux nœuds à traiter sont insérés en fin de file !Les nouveaux nœuds à traiter sont insérés en fin de file !


----

ddcc

.... bb

....

....

File : File : bb - c - d - c - d - e - f- e - f

ee ff

Nous retirons la tête de file etNous retirons la tête de file et

insérons ses fils en fin de file !insérons ses fils en fin de file !




E NE N

P S E U D O - C O D EP S E U D O - C O D E


Parcours en profondeur se fait à l’aide d’une pile !Parcours en profondeur se fait à l’aide d’une pile !

cree_pile_vide();cree_pile_vide();empile( racine );empile( racine );while while ( ! pile_vide() )( ! pile_vide() ) { { traiter = top();traiter = top(); depile();depile(); if if ( est_feuille( traiter ) )( est_feuille( traiter ) ) traite( traiter );traite( traiter ); elseelse {{empile( fils_droit( traiter ) );empile( fils_droit( traiter ) ); empile( fils_gauche( traiter ) );empile( fils_gauche( traiter ) ); }}


----

Nous empilons la seule racine !Nous empilons la seule racine !

Tantqu’il reste desTantqu’il reste destraitements à faire ...traitements à faire ...

Une feuille estUne feuille esttraitée de suite !traitée de suite !

Nous empilons les deux fils d’unNous empilons les deux fils d’unnœud interne pour traitement !nœud interne pour traitement !



E N L A R G E U RE N L A R G E U R

E NE N

P S E U D O - C O D EP S E U D O - C O D E


Parcours en largeur se fait à l’aide d’une file !Parcours en largeur se fait à l’aide d’une file !

cree_file_videcree_file_vide();();enfileenfile( racine );( racine );while ( ! while ( ! file_videfile_vide() )() ) { traiter = { traiter = tetetete();(); defiledefile();(); if ( est_feuille( traiter ) )if ( est_feuille( traiter ) ) traite( traiter );traite( traiter ); elseelse {{enfileenfile( ( fils_droitfils_droit( traiter ) );( traiter ) ); enfileenfile( ( fils_gauchefils_gauche( traiter ) );( traiter ) ); }}


----

Les seules différences !Les seules différences !

C’est un parcours en largeur suffixe !C’est un parcours en largeur suffixe !


M O D I F I C A T I O NM O D I F I C A T I O N

D ’ U ND ’ U N

A R B R EA R B R E


En reconstruisant :En reconstruisant :

33 55 77

22

44 66

Partie qui doit êtrePartie qui doit êtrereconstruite.reconstruite.

cree_noeud(cree_noeud( fg(arbre)fg(arbre) ,, cree_noeud(cree_noeud( fg(fd(arbre))fg(fd(arbre)) ,, cree_noeud(cree_noeud( cree_noeud(cree_feuille(4) ,cree_noeud(cree_feuille(4) , cree_feuille(6))cree_feuille(6)) ,, fd(fd(fd(arbre)))fd(fd(fd(arbre))) ) ) ) ;) ) ) ;

Modification d’un arbreModification d’un arbre------------------------------------------------------------------------------------------------------------------------------

----


En modifiant :En modifiant :

33 55 77

22

44 66

Le pointeur quiLe pointeur qui

est modifié !est modifié !

modifie_fg_noeud(modifie_fg_noeud( fd(fd(arbre))fd(fd(arbre)) ,, cree_noeud( cree_feuille(4) ,cree_noeud( cree_feuille(4) , cree_feuille(6) )cree_feuille(6) ) ) ;) ;


----


Attention aux Attention aux partages de structure partages de structure avec avec modifications modifications physiques !physiques !

sous_arbre_a = cree_noeud(cree_feuille(3) , cree_feuille(5));sous_arbre_a = cree_noeud(cree_feuille(3) , cree_feuille(5));sous_arbre_b = cree_noeud(cree_feuille(3) , cree_feuille(5));sous_arbre_b = cree_noeud(cree_feuille(3) , cree_feuille(5));sous_arbre_c = cree_noeud(cree_feuille(3) , cree_feuille(5));sous_arbre_c = cree_noeud(cree_feuille(3) , cree_feuille(5));arbre_part = cree_noeud( arbre_part = cree_noeud( sous_arbre_asous_arbre_a , , sous_arbre_asous_arbre_a ); );arbre_copie = cree_noeud( arbre_copie = cree_noeud( sous_arbre_bsous_arbre_b , , sous_arbre_csous_arbre_c ); );

33

ReprésentationsReprésentationsphysiques !physiques !


----

33 33 5577 77

modifie_fd_noeud( fg(arbre_part) , modifie_fd_noeud( fg(arbre_part) , 77 ) ; ) ;modifie_fd_noeud( fg(arbre_copie) , modifie_fd_noeud( fg(arbre_copie) , 77 ) ; ) ;

Documents

11 février 2014 Cours d'algorithmique 3 - Intranet 1 Cours dAlgorithmique Arbres. Parcours darbres