STRUCTURES ET TABLEAUX

CPGE MohammediaMP/TSIInformatiqueSrie: Arbres binairesExercice 1.Soit arBin un arbre binaire dentiers non vide.1. Ecrire une fonction qui calcule la taille dun arbre binaire.2. Ecrire une fonction qui calcule la hauteur dun arbre binaire.3. Ecrire une fonction qui calcule le nombre de feuilles dun arbre binaire.4. Ecrire une fonction qui calcule le produit de tous les lments dun arbre binaire.5. Ecrire une fonction qui calcule la somme de tous les lments dun arbre binaire.6. Ecrire une fonction qui dtermine si un lment appartient un arbre binaire.7. Ecrire une fonction qui calcule le maximum dun arbre binaire.Exercice 2.Le niveau dun nud e dans un arbre est le nombre de nuds sur la branche qui conduit de la racine de larbre jusquau nud e inclus. La racine est donc de niveau 1.Soit e un nud de niveau n > 1 dans un arbre A alors il se situe soit dans la gauche, soit dans la droite. Le nud e est de niveau n 1 dans le sous-arbre (gauche ou droit) auquel il appartient.1. Dfinir la fonction nivElm(elm, A) qui donne le niveau dun lment dans un arbre.On conviendra que le niveau dun lment qui nest pas prsent dans larbre est 0.2. Dfinir la fonction nbfNiv(niv, A) qui donne le nombre de feuilles un niveau donn dans un arbre.Exercice 3.Arbres binaire de recherche (ABR). Un arbre binaire a est un arbre binaire de recherche si, pour tout nud s de a, les contenus des nuds du sous-arbre gauche de s sont strictement infrieurs au contenu de s, et que les contenus des nuds du sous-arbre droit de s sont strictement suprieurs au contenu de s.1. Ecrire une fonction abr qui vrifie si un arbre donn est bien un arbre binaire de recherche.2. Ecrire la fonction mem qui recherche si un lment donn appartient un arbre binaire de recherche donn.3. Ecrire une fonction ajout qui ajoute un lment donn un arbre binaire de recherche donn tout en garantissant que larbre reste un arbre binaire de recherche.Exercice 4.On dit que 2 arbres binaires de recherche sont quivalents sils possdent les mmes tiquettes. 1. Ecrire une fonction qui renvoie True si et seulement si deux ABR sont quivalents et False sinon.2. Ecrire une fonction qui prend un ABR et renvoie son minimum.3. Ecrire une fonction qui prend un ABR et renvoie son deuxime plus grand lment.4. Ecrire une fonction qui prend un ABR et calcule la mdiane de ses lments.

Exercice 5.1. On appelle arbre binaire complet un arbre binaire tel que chaque sommet interne a exactement deux fils. Ecrire une fonction qui teste si un arbre binaire est complet.2. On appelle arbre binaire parfait un arbre binaire complet dans lequel toutes les feuilles sont la mme hauteur dans larbre. Ecrire une fonction qui teste si un arbre binaire est parfait.3. On appelle arbre binaire quasi-parfait un arbre binaire parfait ventuellement grignot dun tage en bas droite. Ecrire une fonction qui teste si un arbre binaire est quasi-parfait.Exercice 6.Arbres binaires htrognes. Evaluation dexpressions arithmtiques.On suppose donn un arbre binaire reprsentant une expression arithmtique contenant des entiers et les deux oprateurs binaires + et *.Si lexpression est bien forme (correcte) alors larbre binaire est complet. Chaque feuille de cet arbre contient donc un entier et chaque nud interne un oprateur (lun des symboles + ou *).Ecrire une fonction valExpression(A) qui value la valeur de lexpression reprsente par un arbre binaire si larbre est complet. Sinon elle renvoie None.On veille visiter une et une seule fois tous les nuds de larbre (un seul parcours de larbre).1 / 2