Inscription / Connexion Nouveau Sujet
Niveau calculatrices
Partager :

Algorithme

Posté par Morpheus75 (invité) 16-08-05 à 12:25

Exercice 2

Arbres feuillus
Les arbres considérés dans cet exercice sont des arbres binaires feuillus (complets) dont les noeuds sont des entiers . À un tel arbre A on associe le mot  
 Str(A)=\left\{\begin{matrix} 1 & \mbox{si }A\mbox{ est reduit a une feuille} \\ 0Str(G)Str(D) & \mbox{si }A=(r,G,D)\mbox \end{matrix}\right.                       

ou r est la racine de A, G son sous-srbre gauche et D son sous-abre droit.

1)Calculer Str((1,(2,(3),(4)),(5)))  et Str((1,(2),(3,(4),(5))))
Dessinez les arbres qui correspondent aux mots 0001111 et 0101011

2)Soit x = Str(A) et y = Str(B) pour 2 arbres A et B
Montrez que x = y si et seulement si A et B sont égaux  à la numérotaion près de leurs noeuds  (autrement dit, s'il existe une bijection entre les noeuds qui respecte la structure de l'arbre)

3)Indiquer comment mémoriser dans un fichier le code obtenu par la méthode de Huffman , en adaptant la fonction Str à appliquer à l'arbre de Huffman de codage

4)Ecrire une fonction C qui produit sur la sortie standart x = Str(A) pour un arbre A

5)Ecrire une fonction C qui, à partir d'un mot binaire Str(A) sur l'entée standart ,reconstruit l'arbre A

*** message déplacé ***

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !