morissardj's Home Page

Langage C - Arbres binaires

Un arbre est un ensemble de noeuds (appelés aussi parfois sommets) reliés par des arêtes tel que chaque noeud (à part la racine qui en a 0) ait exactement une arête pointant vers lui. La racine est donc un noeud particulier puisqu'il n'a pas de prédécesseur. Les feuilles sont les noeuds sans sucesseurs.

Un arbre binaire est un arbre tel que chaque noeud a au plus deux fils (ou successeurs). Il peut donc se représenter à l'aide de la structure suivante:

#abr.h
#include <stdio.h>
#include <stdlib.h>

struct Noeud{
int valeur;
struct Noeud * abg;
struct Noeud * abd;
};

typedef struct Noeud* pNoeud;

pNoeud InsererDansABR(pNoeud arbre,int i);
int EstArbreVide(pNoeud arbre);
pNoeud CreerNoeud(int valeur);
void ParcourINFIXE(pNoeud arbre);
pNoeud InsererDansABR2(pNoeud arbre,int i);
int Max(int a,int b);
int Hauteur(pNoeud arbre);
pNoeud Equilibrer(pNoeud arbre);
pNoeud RotationGaucheDroite(pNoeud arbre);
pNoeud RotationDroiteGauche(pNoeud arbre);
pNoeud RotationDroite(pNoeud arbre);
pNoeud RotationGauche(pNoeud arbre);
void ParcourLargeurAffiche(pNoeud arbre);

#abr.h
#include "abr.h"
#include "file_liste.h"

/*************************************************/
pNoeud InsererDansABR(pNoeud arbre,int i){
       if(EstArbreVide(arbre)) return CreerNoeud(i);
       else {
            if(i<arbre->valeur){
            arbre->abg=InsererDansABR(arbre->abg,i);
            }
            if(i>arbre->valeur){
            arbre->abd=InsererDansABR(arbre->abd,i);
            }
       }
return arbre;
}

/*************************************************/
pNoeud InsererDansABR2(pNoeud arbre,int i){
       if(EstArbreVide(arbre)) return CreerNoeud(i);
       else {
            if(i<arbre->valeur){
            arbre->abg=InsererDansABR2(arbre->abg,i);
            }
            if(i>arbre->valeur){
            arbre->abd=InsererDansABR2(arbre->abd,i);
            }
       }

return Equilibrer(arbre);
}
/*************************************************/
pNoeud Equilibrer(pNoeud arbre){
       if( (Hauteur(arbre->abg)-Hauteur(arbre->abd)>=-1)&&(Hauteur(arbre->abg)-Hauteur(arbre->abd)<=1) )return arbre;

       if (Hauteur(arbre->abg)>Hauteur(arbre->abd)){
         // if(!Hauteur(arbre->abg))return RotationGaucheDroite(arbre);
         // if(!Hauteur(arbre->abd))return RotationDroite(arbre);
          if(Hauteur(arbre->abg->abg)>Hauteur(arbre->abg->abd)){
          return RotationDroite(arbre);
          }
          return RotationGaucheDroite(arbre);
       }

       if (Hauteur(arbre->abg)<Hauteur(arbre->abd)){
          //if(!Hauteur(arbre->abg))return RotationGauche(arbre);
          //if(!Hauteur(arbre->abd))return RotationDroiteGauche(arbre);

          if(Hauteur(arbre->abd->abg)>Hauteur(arbre->abd->abd)){
          return RotationDroiteGauche(arbre);
          }
          return RotationGauche(arbre);
       }
}

/*************************************************/
pNoeud RotationDroite(pNoeud arbre){
       pNoeud pivot=arbre;
       pNoeud NewAVL = arbre->abg;
       pivot->abg=NewAVL->abd;
       NewAVL->abd=pivot;
    return NewAVL;
}
/*************************************************/
pNoeud RotationGauche(pNoeud arbre){
       pNoeud pivot=arbre;
       pNoeud NewAVL = arbre->abd;
       pivot->abd=NewAVL->abg;
       NewAVL->abg=pivot;
    return NewAVL;
}
/*************************************************/
pNoeud RotationGaucheDroite(pNoeud arbre){
    arbre->abg=RotationGauche(arbre->abg);
    return RotationDroite(arbre);
}
/*************************************************/
pNoeud RotationDroiteGauche(pNoeud arbre){
    arbre->abd=RotationDroite(arbre->abd);
    return RotationGauche(arbre);
}
/*************************************************/
int EstArbreVide(pNoeud arbre){
    return (arbre==NULL);
}

/*************************************************/
int Hauteur(pNoeud arbre){
    if (arbre==NULL)return 0;
    return Max(1+Hauteur(arbre->abg),1+Hauteur(arbre->abd));
}
/*************************************************/
int Max(int a,int b){
    if (a>b)return a;
    return b;
}/*************************************************/
pNoeud CreerNoeud(int valeur){
       pNoeud arbre = (pNoeud)malloc(sizeof(struct Noeud));
       arbre->valeur=valeur;
       arbre->abg=NULL;
       arbre->abd=NULL;
return arbre;
}
/*************************************************/
void ParcourINFIXE(pNoeud arbre){
            if(!EstArbreVide(arbre)){
            ParcourINFIXE(arbre->abg);
            printf("%d",arbre->valeur);
            ParcourINFIXE(arbre->abd);
            }
}
/*************************************************/
void ParcourLargeur(pNoeud arbre){
           if(!EstArbreVide(arbre)){
             printf("%d",arbre->valeur);
             pFile File=NULL;
             File=Enfiler(arbre->abg,File);
             File=Enfiler(arbre->abd,File);

             while(!EstFileVide(File)){
             printf("%d",File->Tete->valeur->valeur);
             File=Enfiler(File->Tete->valeur->abg,File);
             File=Enfiler(File->Tete->valeur->abd,File);
             File=Defiler(File);
             }
           }
           printf("\n");
}

/*************************************************/

void ParcourLargeurAffiche(pNoeud arbre){
     int hauteur,i;
     hauteur=Hauteur(arbre);
           if(!EstArbreVide(arbre)){
             printf("%d",arbre->valeur);
             pFile File=NULL;
             File=Enfiler(arbre->abg,File);
             File=Enfiler(arbre->abd,File);

             while(!EstFileVide(File)){
               if(Hauteur(File->Tete->valeur)<hauteur){
               printf("\n");
               hauteur=Hauteur(File->Tete->valeur);
             }
             printf("%d",File->Tete->valeur->valeur);
             File=Enfiler(File->Tete->valeur->abg,File);
             File=Enfiler(File->Tete->valeur->abd,File);
             File=Defiler(File);
             }
           }
           printf("\n");
}

Source