DecodeTree Huffman, interrogations et soucis
Bonsoir,
J'ai un petit projet pour l'école, et celui-ci nous emmène sur le terrain du cryptage d'Huffman. Néanmoins je me frotte à un gros soucis pour la dernière fonction à réaliser. Celle-ci consiste à "décoder" une string pour créer l'arbre binaire. Explications, on encode l'arbre et ses valeurs dans une string
( Encodes a huffman tree to its binary representation using a preOrder traversal:
* each leaf key is encoded into its binary representation on 8 bits preceded by '1'
* each time we go left we add a '0' to the result )
en utilisant un parcours préfixe de cet arbre. La fonction sur laquelle je butte doit prendre ce string et retourner l'arbre binaire correspondant.
Fonction telle qu'elle est fournie :
Code:
1
2
3
4
5
6
7
|
def decodetree(dataIN):
"""
Decodes a huffman tree from its binary representation:
* a '0' means we add a new internal node and go to its left node
* a '1' means the next 8 values are the encoded character of the current leaf
""" |
Pour l'utilisation des différentes classes on est autoriser à utiliser BinTree ( qui contient self.key, self.right, self.left uniquement ) et heap ( qui contient self.push, self.pop, self.isEmpty ) /!\ UNIQUEMENT /!\ pas de nodes ou ce genre de chose.
Du coup si vous pouvez m'aider à appréhender la chose ce ne serait pas de refus, j'ai du mal à visualiser comment créer un arbre à partir d'une telle string. Merci à tout ceux qui prendront le temps de m'aider ^^.
