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.
Partager