Discussion :

[Goundy]

Bonjour,

Alors voilà, je suis en train de coder l'algorithme de huffman mais j'ai un problème avec l'arbre, j'ai pas la méthode si on veut. Car pour construire un arbre à partir de la racine c'est pas méchant, mais dans le sens inverse je ne m'y retrouve pas.
Donc je sollicite votre chère intervention pour me donner un petit coup de pieds aux fesses pour bien décoller lol
Plus directe, quelle est la méthode générale utilisée pour construire un arbre en commencant par les fils?

Merci

[mathk]

il faut que tu ai une referrence sur le pére dans ta structur d'arbre

[Goundy]

ah!
Donc je dois faire mes noeud du style:
Noeud{
type donné;
pointeur gauche, droite, pere;
}
c'est ca?

[mathk]

oui c une solution qui me parait acceptable
Non?

[Goundy]

Ouais je vais procéder ainsi
Merci

[Matthieu Brucher]

De toute manière, ça peut toujours être pratique d'avoir le père
L'autre solution, c'est d'utiliser une map dans laquelle on stocke les clés et leur poids. En fait, on stocke pas les clés, on stocke un pointeur vers un noeud. Puis on prends les 2 premiers, on les "fusionne" et on met dans la map le nouvel élément. Là, pas besoin de pointeurs vers le père. A la fin, il n'y aura plus qu'un seul élément dans la map.