typedef struct arbre *arbre; struct arbre { int info; arbre fg; arbre fd; }; /* ------------------- Afficher ------------------------ */ void afficher_rec(arbre a) { if ( a != NULL ) { afficher(a->fg); printf("%d ", a->info); afficher(a->fd); } } void afficher(arbre a) { pile p = pil_creer(a); while ( !pil_vide(p) ) { arbre a1 = pil_sommet(p); if ( a1->fg != NULL ) pil_empiler(p, a1->fg); else { printf("%d ", a1->info); /* On est sur une feuille de l'arbre */ /* On remonte jusqu'au premier ancetre ayant un fils droit */ /* non encore visite */ if ( a1->fd == NULL ) { arbre a2 = pil_depiler(p); a1 = pil_sommet(p); while ( !pil_vide(p) && ( (a1->fd == NULL) || (a1->fd == a2)) ) { if ( a2 == a1->fg ) printf("%d ", a1->info); a2 = pil_depiler(p); a1 = pil_sommet(p); } } if ( !pil_vide(p) ) pil_empiler(p, a1->fd); } } pil_liberer(p); } /* ------------------- Permutation ------------------------ */ static int Indice; int *arbre_vers_tableau_rec(arbre a, int n) { int *perm = (int *) malloc(n * sizeof(int)); assert( perm != NULL ); Indice = 0; arbre_vers_tableau_aux(a, perm); return perm; } void arbre_vers_tableau_aux_rec(arbre a, int *perm) { if ( a != NULL ) { arbre_vers_tableau_aux(a->fg); perm[Indice++] = a->info; arbre_vers_tableau_aux(a->fd); } } void arbre_vers_tableau_miroir_aux_rec(arbre a, int *perm) { if ( a != NULL ) { arbre_vers_tableau_aux(a->fd); perm[Indice++] = a->info; arbre_vers_tableau_aux(a->fg); } } int *arbre_vers_tableau(arbre a, int n) { int indice = 0; pile p = pil_creer(a); int *perm = (int *) malloc(n * sizeof(int)); assert( perm != NULL ); while ( !pil_vide(p) ) { arbre a1 = pil_sommet(p); if ( a1->fg != NULL ) pil_empiler(p, a1->fg); else { perm[indice++] = a1->info; /* On est sur une feuille de l'arbre */ /* On remonte jusqu'au premier ancetre ayant un fils droit */ /* non encore visite */ if ( a1->fd == NULL ) { arbre a2 = pil_depiler(p); a1 = pil_sommet(p); while ( !pil_vide(p) && ( (a1->fd == NULL) || (a1->fd == a2)) ) { if ( a2 == a1->fg ) perm[indice++] = a1->info; a2 = pil_depiler(p); a1 = pil_sommet(p); } } if ( !pil_vide(p) ) pil_empiler(p, a1->fd); } } pil_liberer(p); return perm; } /* ------------------- Recherche ------------------------ */ /* Version 1 : 2 variables statiques */ static int Rechercher_indice1; static arbre Rechercher_resultat1; arbre rechercher_rec1(arbre a, int i) { Rechercher_indice1 = 0; Rechercher_resultat1 = NULL; rechercher_rec_aux1(a, i); return Rechercher_resultat1; } void rechercher_rec_aux1(arbre a, int i) { if ( a->fg != NULL ) rechercher_rec_aux1(a->fg); if ( ++Rechercher_indice1 == i ) Rechercher_resultat1 = a; else { if ( Rechercher_resultat1 == NULL ) { assert( a->fd != NULL ); rechercher_rec_aux1(a->fd, i); } } } /* Version 2 : sans variable statique */ arbre rechercher_rec3(arbre a, int i) { int indice = 0; return rechercher_rec_aux3(a, i, &indice); } void rechercher_rec_aux3(arbre a, int i, int *indice) { int resultat; if ( (a == NULL) || (a->fg == NULL) ) return a; resultat = rechercher_rec_aux3(a->fg, i, j); if ( resultat == NULL ) { if ( ++(* indice) == i) return a; assert( a->fd != NULL ); return rechercher_rec_aux3(a->fd, i, j); } else return resultat; } /* Version 3 : non récursive */ arbre rechercher(arbre a, int n) { arbre resultat; int indice = 0; pile p = pil_creer(a); while ( indice < i ) { arbre a1 = pil_sommet(p); if ( a1->fg != NULL ) pil_empiler(p, a1->fg); else { indice++; /* On est sur une feuille de l'arbre */ /* On remonte jusqu'au premier ancetre ayant un fils droit */ /* non encore visite */ if ( a1->fd == NULL ) { arbre a2 = pil_depiler(p); a1 = pil_sommet(p); while ( !pil_vide(p) && (indice < i) && ( (a1->fd == NULL) || (a1->fd == a2)) ) { if ( a2 == a1->fg ) indice++; a2 = pil_depiler(p); a1 = pil_sommet(p); } } if ( (indice < i) && (!pil_vide(p)) ) pil_empiler(p, a1->fd); } } resultat = pil_sommet(p); pil_liberer(p); return resultat; }