Huffman : arbre et chaine de binaire

Commenter

Contenu du snippet 

class Lettre{
    public Lettre(char l, int f){ this.l=l; this.f=f; }
    public char getL(){ return l; }
    public int getF(){ return f; }
    public String toString(){
        return this.l+" => "+this.f;
    }
    public void add(int i){ this.f+=i; }
    private char l;
    private int f; // le nombre d'apparitions
}
class HuffArbre /* un arbre binaire */{
    public HuffArbre(Lettre l){this.feuille=l;}
    public HuffArbre(HuffArbre droite, HuffArbre gauche){
        this.droite=droite; this.gauche=gauche;
    }
    public String toString(){
        if (this.feuille!=null){
            return "Feuille("+this.feuille+")";
        }else{
            return "Branche("+this.droite+", "+this.gauche+")\n";
        }
    }
    public void add(HuffArbre a){
        if (this.feuille!=null){
            this.feuille.add(a.count());
        }else{
            System.out.println("tey null");
        }
    }
    public char getL(){
        if (this.feuille!=null){
            return this.feuille.getL();
        }else{
            return this.droite.getL();
        }
    }
    public int count(){
        if (this.feuille!=null){
            return this.feuille.getF();
        }else{
            return this.droite.count()+this.gauche.count();
        }
    }
    public String getSeq(char c){
        if (this.feuille != null){
            if (this.feuille.getL() == c){
                return "";
            }else{
                return "ERR";
            }
        }else{
            String outb, outa = this.droite.getSeq(c);
            if (outa.equals("ERR")){
                outb=this.gauche.getSeq(c);
                if (outb.equals("ERR")){
                    return "ERR";
                }else{
                    return outb.concat("1");
                }
            }else
                return outa.concat("0");
        }
    }
    private Lettre feuille;
    private HuffArbre droite;
    private HuffArbre gauche;
}
class HuffArbreList extends java.util.LinkedList<HuffArbre>{
    public HuffArbreList(){
    }
    public HuffArbreList(String str){
        for (int i=0;i<str.length();i++){
            this.insertSorted(new HuffArbre(new Lettre(str.charAt(i), 1)));
        }
    }
    public void insertSorted(HuffArbre e){
        int i=0, s=this.size();
        while (i<s && cmp(this.get(i), e)) i++;
        this.add(i, e);
    }
    public boolean cmp(HuffArbre a, HuffArbre b){
        if (this.sortLetter){
            return a.getL() <= b.getL();
        }else{
            return a.count() <= b.count();
        }
    }
    public HuffArbreList grouper(){
        HuffArbre e1, e2;
        HuffArbreList l=new HuffArbreList();
        l.sortLetter=false;
        e1=this.removeFirst();
        int s=this.size();
        for (int i=0;i<s;i++){
            e2=this.removeFirst();
            if (e1.getL()==e2.getL()){
                e1.add(e2);
            }else{
                l.insertSorted(e1);
                e1=e2;
            }
        }
        l.add(e1);
        return l;
    }
    public void faireArbre(){
      if (this.size()==1) return;
      HuffArbre e1, e2;
      e1=this.removeFirst();
      e2=this.removeFirst();
      this.insertSorted(new HuffArbre(e1, e2));
      faireArbre();
    }
    public boolean sortLetter=true;
}
public class Main {
    public static void main(String[] args) {
        HuffArbreList liste=new HuffArbreList("test ok arbre test");
        liste=liste.grouper();
        liste.faireArbre();
        HuffArbre arbre=liste.removeFirst();
        System.out.println(arbre);
        System.out.println(arbre.getSeq('t'));
    }
}

Compatibilité : Java

Disponible dans d'autres langages :

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (coucou747)