Algorithme de Huffman : parcours de l'arbre

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 :

Pièce jointe 469666

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

Pièce jointe 469678

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.

Bonjour :coucou:

Citation:

---

2x1 +1 = 3

---

Mais que peut bien exprimer ce calcul ?

---

Tu pars de l'indice augmenté de 1.
Pour déterminer le chiffre : x%2
Pour passer au suivant : x/2 (division entière évidemment)
Et tu t'arrêtes en arrivant à 1.

Exemple : "a" d'indice 4
4+1=5
5%2 = 1 et 5/2 = 2
2%2 = 0 et 2/2 = 1
Codage du a: 0 1

Autre exemple : "c" d'indice 11
11+1=12
12%2 = 0 et 12/2 = 6
6%2 = 0 et 6/2 = 3
3%2 = 1 et 3/2 = 1
Codage du c: 1 0 0

NOTE: ton tableau est faux car il manque les indices non affectés (9 et 10)
"c" est à la place 9 alors qu'il devrait être à la place 11.
Si tu ne veux pas de trou dans ton tableau, alors tu ne peux pas travailler avec les indices.

Merci pour ta réponse. :P

Le 2x1 + 1 = 3 vient du tri par tas quand on cherche le fils gauche à partir de l'indice 1.

Tu as une règle pour trouver les 2 fils à partir d'un père. Si le père a le n° x, les 2 fils portent les n° 2x+1 et 2x+2.
Ok.
Mais cette règle marche dans 2 cas :
- cas 1 : si l'arbre est complet ( 1 élément au plus haut niveau, puis 2 au niveau suivant , et à chaque fois, on multiplie le nombre d'éléments par 2) ; Ici ce n'est pas le cas , l'un des éléments n'a pas 2 fils, alors que les autres éléments du même niveau ont 2 fils.
- cas 2 : si l'arbre est presque complet , et que les éléments manquants sont les derniers.
Ici sur l'avant dernière ligne, tu as 4 éléments. L'élément qui n'a pas de fils, c'est le 2ème. Pas bon. Si c'était le 4ème, ta formule marcherait.

Ton programme marche, il ne faut pas chercher à faire un programme qui marcherait dans le cas de cet arbre précis.
Il faut corriger la création de l'arbre, pour qu'il rentre dans un des 2 cas que j'ai décrits (le cas 2 en l'occurrence)

En tout cas, c'est ma vision de la chose.

Merci pour ta réponse.

Comme j'essaie de codé l'arbre de Huffman un certain moment tu as des feuilles qui on une profondeur n-1 (comme sur l'image de mon arbre) ; mais alors comment faut-on pour représenté cette arbre de Huffman (qui n'est pas complet) dans un tableau ?

L'indice 9 a une valeur 0.
L'indice 10 a une valeur 0.
Et l'indice maximum (14) a la valeur 1 et représente "e".

Ha ok merci. :)

Citation:

---

L'indice 9 a une valeur 0.
L'indice 10 a une valeur 0.
Et l'indice maximum (14) a la valeur 1 et représente "e".

---

Trop compliqué à mettre en oeuvre je vais revoir mon algo.