Discussion :

[Invité]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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