Salut!

J'ai un devoir  ou je dois implémenter un Huffman Code tree mais a partir d'une séquence binaire in-order. Par exemple si l'on rentre ds le programme ça, 001011, l'arbre va ressembler a ceci:

(juste sans la valeur des frequences.)

Le programme requérit aussi à l'utilisateur au tt début d'entrer:

- le nombre de lettres différentes (4 ici)

- quelles sont les lettres ds l'ordre qu'elles apparaissent ds l'arbre (acdb)

- la séquence binaire inorder de l'arbre où 0=left et 1=right

- le string a decoder mais ça c pr un autre truc.

j'ai écrit une fonction récursive qui créée l'arbre mais le dernier node manque.

la fonction en question:

    void createEmptyTree(HuffmanNode* ptr, string s) //créer un arbre a partir d'une séquence binaire
    {
        char whatev = '_';
        int whatevs = -1;

        if (s.size() != NULL) //continue d'ajouter des nodes tant le string s existe
        {
            if (s[0] == '0') //si le premier char du string est 0, ajouter une valeur au left
            {
                ptr->left = new HuffmanNode(whatev, whatevs);
                s.erase(0, 1); //effacer le premier char pr avancer

                if (s[0] == '0') // si le nouveau premier char est 0, on continue la fonction a partir du nouveau node créer
                    createEmptyTree(ptr->left, s);
                if (s[0] == '1')//si le nouveau premier char est 1, on continue la fonction du mm node présent
                    createEmptyTree(ptr, s);
            }

            if (s[0] == '1')// si le premier char du string est 1, on ajoute right au node
            {
                ptr->right = new HuffmanNode(whatev, whatevs);
                s.erase(0, 1);//effacer le premier char pr avancer
                if (s[0] == '0') // si le nouveau premier char est 0, on continue la fonction a partir du nouveau node créer
                    createEmptyTree(ptr->right, s);
                if (s[0] == '1')//si le nouveau premier char est 1, on return pr revenir au node précédent libre
                    return;

            }
        }

        else
            return;
    }

expected output: 001011

ce que je reçois plutôt: 00101

Qu'est-ce que je peux faire pr remédier à ce problème svp?

*aussi voilà la fonction qui imprime la séquence binaire inorder de l'arbre-- au cas ou que ça servent à savoir:

void HuffmanTree::printSequence(HuffmanNode* ptr)
{
	if (!ptr)
		return;

	if (!ptr->left && !ptr->right)
		return;

	if (ptr->left)
	{
		//q.push(0);
		cout << 0;
		printSequence(ptr->left);
	}

	if (ptr->right)
	{
		cout << 1;
		//q.push(1);
		printSequence(ptr->right);
	}
}

-
Edité par NessyaNakache 5 janvier 2021 à 9:42:02

Salut,

Non seulement en effet le debuggueur te donnera des informations, mais il est également intéressant de jouer de l'assert.

Par exemple, un arbre de Huffman est un arbre binaire, donc chaque noeud a 0 ou 2 fils, jamais 1.

Donc ta fonction printsequence pourrait etre :

void HuffmanTree::printSequence(HuffmanNode* ptr)
{
    assert(ptr);
    if (ptr->left)
    {
    	assert(ptr->right);
    	cout << 0;
      printSequence(ptr->left);
      cout << 1;
      printSequence(ptr->right);
    }
}

Déjà, voir si ton arbre est correct en rentrant dans cette fonction, en voyant si tu ne te prends pas un assert

-
Edité par Fvirtman 5 janvier 2021 à 10:45:54

merci bcp pr l'indice que tt node a soit 0 ou 2 nodes!

j'ai simplement creer une fonction qui repasse sur l'arbre et rempli ou il manquerait des nodes

En tout cas, j'aime beaucoup cette façon compacte de définir un arbre binaire. Je dirais même qu'avec un seul bit de plus, on n'a pas besoin de savoir la taille de la chaine à encoder, le code peut être autosuffisant. Rend toi compte que ton arbre (sa structure) est codée sous 6 bits (7 si je rajoute un 1 qui terminerait la récursion -> 1 seul octet !! et on a même un bit en rab). 

J'aime beaucoup vraiment. Autant pour le reste du code de Huffman il n'y a pas de soucis, autant l'encodage d'un arbre binaire, ça je trouve ça classe.