• # wikipedia ?

    Posté par  (site web personnel, Mastodon) . Évalué à 2.

    http://fr.wikipedia.org/wiki/Arbre_binaire

    • [^] # Re: wikipedia ?

      Posté par  . Évalué à 1.

      Bonjour, j'ai déjà regardé ces choses, mais pas trop en profondeur. Merci beaucoup d'insister. J'ai fait une fonction qui me donne la profondeur de l'arbre et le nombre de noeuds :
      unsigned int node_count(huffman_tree * root)
{
    if(root->left!=NULL && root->right!=NULL)
    {
         return 1 + node_count(root->left) + node_count(root->right);
    }
    else
    {
         return 0 ;
    }
}

unsigned int depth(huffman_tree * root)
{
    if(root->left!=NULL && root->right!=NULL)
    {
        return 1+ ( (depth(root->left) > depth(root->right)) ? depth(root->left) : depth(root->right) ) ;
    }
    else
    {
        return 0;
    }
}
      Ce sont des choses qui marchent bien. Je devrai écrire ça de manière récursive, mais je ne vois pas trop comment procéder.

      • [^] # Re: wikipedia ?

        Posté par  . Évalué à 1.

        Bon voilà, en fait, j'ai fini par obtenir la profondeur max de l'arbre. Donc je connais les codes binaires disponibles pour indexer complétement l'arbre. Ça devrait me permettre de construire un index exhaustif de toutes les feuilles de l'abre. Le problème, c'est que je voudrai faire quelque chose de manière un peu plus sophistiquée, donc avec une version récursive si c'est possible...

        • [^] # Re: wikipedia ?

          Posté par  . Évalué à 2.

          Tu utilises déjà la récursivité dans ton code, tu veux quoi exactement ?

          • [^] # Re: wikipedia ?

            Posté par  . Évalué à 2.

            ... Je suis en voie de trouver une solution exhaustive, je vais la poster dèss que j'ai fini...

      • [^] # Re: wikipedia ?

        Posté par  . Évalué à 2.

        Ton code est buggé (sauf si tes arbres sont complets) :)

        • [^] # Re: wikipedia ?

          Posté par  . Évalué à 2.

          mon arbre est supposément complet.

          • [^] # Re: wikipedia ?

            Posté par  . Évalué à 2.

            Dans ce cas ton calcul de la hauteur est pas vraiment optimal.

            • [^] # Re: wikipedia ?

              Posté par  . Évalué à 2.

              Je ne cherche pas vraiment à être optimal, plutôt à avoir un truc propre qui marche. Finalement, la fonction que je voulais faire ressemble à ça : 
              void index_huffman_tree(unsigned int depth, unsigned int bit, huffman_tree * root, huffman_tree * huffman_index)
{
    unsigned int char_pos ;
    unsigned int bit_pos ;
    unsigned char bin_mask ;
    unsigned char index ;


    /* modification du noeud de l'arbre */
    root->bit_size = depth ; /* taille du mot en bits */

    char_pos = (depth/CHAR_BIT) ;
    bit_pos = (depth%CHAR_BIT) ;
    if (bit) {
        bin_mask = (unsigned char)(pow(2,bit_pos)) ;
    } else {
        bin_mask = 0 ;
    }
    root->bin_word[char_pos] = (root->bin_word[char_pos] | bin_mask) ;

    /* appel recursif sur les noeuds suivants */
    if( root->left!=NULL && root->right!=NULL )
    {
        index_huffman_tree(depth+1,0,root->left,huffman_index) ;
        index_huffman_tree(depth+1,1,root->right,huffman_index) ;
    }
    else
    {
        i_index = (unsigned char)(root->character) ;
        huffman_index[index] = *root ;
    }
}

            • [^] # Re: wikipedia ?

              Posté par  . Évalué à 2.

              PS : À moins que tu ne désigne arbre binaire entier comme arbre binaire parfait, tandis que pour moi il s'agit d'un arbre binaire entier. Dans mon cas, il s'agit simplement d'un arbre entier, il est non parfait.

              http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_tre(...)
              http://fr.wikipedia.org/wiki/Arbre_binaire#Types_d.27arbre_b(...)

            • [^] # Re: wikipedia ?

              Posté par  . Évalué à 2.

              Je reformule : à moins que tu n'assimile arbre complet à arbre binaire parfait, tandis que j'assimile arbre complet à arbre binaire entier.

  • # lis ton cours et fait des exos...

    Posté par  . Évalué à 4.

    car typiquement cela ressemble trop a un enoncé d'exercice...

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.