Discussion :

[hbx360]

Bonjour,

Je cherche à implémenter l'algorithme de Huffman mais je me retrouve devant un problème : comment parcours t-on l'arbre ; parce qu'un moment ça coince

Voici un exemple :

j'ai cette phrase : "bac a sable"

Après comptage des occurrence on obtient : c:1 ; s:1 ; l:1 ; e:1 ; space:2 ; b:2 ; a:3

Ensuite je crée l'arbre et j'obtiens :



Maintenant c'est pour le parcours (pour créer le code binaire), j'ai le tableau suivant avec les index :



Donc si je le parcours pour le fils droit et gauche à partir de l'index 1 donc le nombre 7 :

2x1 +1 = 3 et 2x1+2 = 4 donc là ok je tombe bien sur les bonnes valeurs (4 et 3) comme indiqué sur l'arbre.

Si je prends l'index 4 (valeurs 3) là je trouve : 2x4+1 = 9 et 2x4+2=10 et là c'est pas bon puisque le nombre 3 est une feuille. En fait impossible de remonter l'arbre pour faire mon codage car les autres calcules sont faux.

Pourriez-vous m'indiquer comment faire pour parcourir mon arbre sans avoir ce type de problème je vois pas du tout ! Comment faut-il l'arranger car en fait mon arbre comme on le voit dans l'image ci-dessus n'est pas ordonné et ne peut pas l'être sinon je déstructure tout le codage binaire.

Merci.