Arbre binaire de recherche

On donne une partie de la classe ABR pour implémenter les arbres binaires de recherche sans doublon : un ensemble fini de nœuds, éventuellement vide, organisés de manière hiérarchique. C'est une arborescence d'éléments comparables.

Un ABR est une structure de nature récursive :

• soit c'est un ABR vide,
• soit il possède un nœud racine qui a les attributs :
  • gauche : un sous-ABR à gauche
  • element : un élément comparable aux autres
  • droite : un sous-ABR à droite
  • l'élément de la racine est strictement supérieur à celui du sous-ABR gauche (s'il est non vide)
  • l'élément de la racine est strictement inférieur à celui du sous-ABR droite (s'il est non vide)

Dans l'implémentation suivante :

• Noeud est une classe qui possède trois attributs :

  • gauche
  • element
  • droite
  • On aurait pu utiliser aussi un tuple nommé...

• ABR() initialise un ABR vide.

• Un ABR, vide ou non, possède les méthodes dont le nom est explicite :
  • est_vide(self) qui renvoie un booléen
  • insere(self, element) qui agit sur l'ABR
  • est_present(self, element) qui renvoie un booléen
  • affichage_infixe(self) qui renvoie une chaine de caractère composée des affichages des éléments et du séparateur |, suite à un parcours infixe.

Exemples

🐍 Console Python

>>> nombres = ABR()
>>> nombres.est_vide()
True
>>> for x in [1, 3, 7, 9, 9]: nombres.insere(x)
>>> not nombres.est_vide()
True
>>> nombres.affichage_infixe()
'|1|3|7|9|'
>>> nombres.est_present(7)
True
>>> nombres.est_present(8)
False

🐍 Console Python

>>> fruits_ranges = ABR()
>>> fruits_ranges.est_vide()
True
>>> panier = ["kiwi", "pomme", "abricot", "mangue", "poire"]
>>> for fruit in panier: fruits_ranges.insere(fruit)
>>> fruits_ranges.est_vide()
False
>>> fruits_ranges.affichage_infixe()
'|abricot|kiwi|mangue|poire|pomme|'
>>> fruits_ranges.est_present("pomme")
True
>>> fruits_ranges.est_present("cerise")
False

Code à compléter :

###

Lancer# testsbksl-nlbksl-nl#1bksl-nlnombres = ABR()bksl-nlassert nombres.estpy-undvide()bksl-nlfor x in [1, 3, 7, 9, 9]:bksl-nl nombres.insere(x)bksl-nlassert not nombres.estpy-undvide()bksl-nlbksl-nlassert nombres.affichagepy-undinfixe() == '|1|3|7|9|'bksl-nlbksl-nlassert nombres.estpy-undpresent(7)bksl-nlassert not nombres.estpy-undpresent(8)bksl-nlbksl-nl#2bksl-nlfruitspy-undranges = ABR()bksl-nlassert fruitspy-undranges.estpy-undvide()bksl-nlbksl-nlpanier = ["kiwi", "pomme", "abricot", "mangue", "poire"]bksl-nlfor fruit in panier:bksl-nl fruitspy-undranges.insere(fruit)bksl-nlassert not fruitspy-undranges.estpy-undvide()bksl-nlbksl-nlassert fruitspy-undranges.affichagepy-undinfixe() == '|abricot|kiwi|mangue|poire|pomme|'bksl-nlbksl-nlassert fruitspy-undranges.estpy-undpresent("pomme")bksl-nlassert not fruitspy-undranges.estpy-undpresent("cerise")bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nldef permutations(objets):bksl-nl n = len(objets)bksl-nl if n == 0:bksl-nl return [[]]bksl-nl resultat = []bksl-nl for i in range(n):bksl-nl objetspy-undsanspy-undi = [objets[j] for j in range(n) if i != j]bksl-nl for perm in permutations(objetspy-undsanspy-undi):bksl-nl perm.append(objets[i])bksl-nl resultat.append(perm)bksl-nl return resultatbksl-nlbksl-nlbksl-nlfor perm in permutations([1, 2, 3, 4, 5]):bksl-nl abr = ABR()bksl-nl assert abr.estpy-undvide()bksl-nl for x in perm: abr.insere(x)bksl-nl for x in range(-5, 10):bksl-nl attendu = 1 <= x < 6bksl-nl assert abr.estpy-undpresent(x) == attendubksl-nl assert abr.affichagepy-undinfixe() == '|1|2|3|4|5|'bksl-nlbksl-nl Valider 5/5 TéléchargerTéléverser RechargerSauvegarder

class Noeud:bksl-nl def py-undpy-undinitpy-undpy-und(self, gauche, element, droite):bksl-nl self.gauche = gauchebksl-nl self.element = elementbksl-nl self.droite = droitebksl-nlbksl-nlclass ABR:bksl-nl "Classe ABR ; sans doublon"bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl "Initialiseur"bksl-nl self.racine = Nonebksl-nl bksl-nl def estpy-undvide(self):bksl-nl "Renvoie un booléen"bksl-nl return self.racine is Nonebksl-nl bksl-nl def insere(self, element):bksl-nl "Insère sans doublon un élément"bksl-nl if self.estpy-undvide():bksl-nl self.racine = Noeud(ABR(), element, ABR())bksl-nl elif element < self.racine.element:bksl-nl self.racine.gauche.insere(element)bksl-nl elif element > self.racine.element:bksl-nl ...bksl-nl else:bksl-nl # cas d'égalitébksl-nl pass # donc pas de doublon !bksl-nl bksl-nl def estpy-undpresent(self, element):bksl-nl "Renvoie un booléen"bksl-nl if self.estpy-undvide():bksl-nl return ...bksl-nl elif element < self.racine.element:bksl-nl return self.racine.gauche.estpy-undpresent(element)bksl-nl elif ...:bksl-nl ...bksl-nl else:bksl-nl # cas d'égalitébksl-nl return Truebksl-nl bksl-nl def affichagepy-undinfixe(self):bksl-nl "Renvoie une chaine à afficher"bksl-nl if self.estpy-undvide():bksl-nl return "|"bksl-nl else:bksl-nl return (bksl-nl self.racine.gauche.affichagepy-undinfixe()bksl-nl + str(self.racine. ...)bksl-nl + self.racine. ...bksl-nl )bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nl#1bksl-nlnombres = ABR()bksl-nlassert nombres.estpy-undvide()bksl-nlfor x in [1, 3, 7, 9, 9]:bksl-nl nombres.insere(x)bksl-nlassert not nombres.estpy-undvide()bksl-nlbksl-nlassert nombres.affichagepy-undinfixe() == '|1|3|7|9|'bksl-nlbksl-nlassert nombres.estpy-undpresent(7)bksl-nlassert not nombres.estpy-undpresent(8)bksl-nlbksl-nl#2bksl-nlfruitspy-undranges = ABR()bksl-nlassert fruitspy-undranges.estpy-undvide()bksl-nlbksl-nlpanier = ["kiwi", "pomme", "abricot", "mangue", "poire"]bksl-nlfor fruit in panier:bksl-nl fruitspy-undranges.insere(fruit)bksl-nlassert not fruitspy-undranges.estpy-undvide()bksl-nlbksl-nlassert fruitspy-undranges.affichagepy-undinfixe() == '|abricot|kiwi|mangue|poire|pomme|'bksl-nlbksl-nlassert fruitspy-undranges.estpy-undpresent("pomme")bksl-nlassert not fruitspy-undranges.estpy-undpresent("cerise")bksl-nlbksl-nlclass Noeud:bksl-nl def py-undpy-undinitpy-undpy-und(self, gauche, element, droite):bksl-nl self.gauche = gauchebksl-nl self.element = elementbksl-nl self.droite = droitebksl-nlbksl-nlclass ABR:bksl-nl "Classe ABR ; sans doublon"bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl "Initialiseur"bksl-nl self.racine = Nonebksl-nl bksl-nl def estpy-undvide(self):bksl-nl "Renvoie un booléen"bksl-nl return self.racine is Nonebksl-nl bksl-nl def insere(self, element):bksl-nl "Insère sans doublon un élément"bksl-nl if self.estpy-undvide():bksl-nl self.racine = Noeud(ABR(), element, ABR())bksl-nl elif element < self.racine.element:bksl-nl self.racine.gauche.insere(element)bksl-nl elif element > self.racine.element:bksl-nl self.racine.droite.insere(element)bksl-nl else:bksl-nl # cas d'égalitébksl-nl pass # donc pas de doublon !bksl-nl bksl-nl def estpy-undpresent(self, element):bksl-nl "Renvoie un booléen"bksl-nl if self.estpy-undvide():bksl-nl return Falsebksl-nl elif element < self.racine.element:bksl-nl return self.racine.gauche.estpy-undpresent(element)bksl-nl elif element > self.racine.element:bksl-nl return self.racine.droite.estpy-undpresent(element)bksl-nl else:bksl-nl # cas d'égalitébksl-nl return Truebksl-nl bksl-nl def affichagepy-undinfixe(self):bksl-nl "Renvoie une chaine à afficher"bksl-nl if self.estpy-undvide():bksl-nl return "|"bksl-nl else:bksl-nl return (bksl-nl self.racine.gauche.affichagepy-undinfixe()bksl-nl + str(self.racine.element)bksl-nl + self.racine.droite.affichagepy-undinfixe()bksl-nl )bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nl#1bksl-nlnombres = ABR()bksl-nlassert nombres.estpy-undvide()bksl-nlfor x in [1, 3, 7, 9, 9]:bksl-nl nombres.insere(x)bksl-nlassert not nombres.estpy-undvide()bksl-nlbksl-nlassert nombres.affichagepy-undinfixe() == '|1|3|7|9|'bksl-nlbksl-nlassert nombres.estpy-undpresent(7)bksl-nlassert not nombres.estpy-undpresent(8)bksl-nlbksl-nl#2bksl-nlfruitspy-undranges = ABR()bksl-nlassert fruitspy-undranges.estpy-undvide()bksl-nlbksl-nlpanier = ["kiwi", "pomme", "abricot", "mangue", "poire"]bksl-nlfor fruit in panier:bksl-nl fruitspy-undranges.insere(fruit)bksl-nlassert not fruitspy-undranges.estpy-undvide()bksl-nlbksl-nlassert fruitspy-undranges.affichagepy-undinfixe() == '|abricot|kiwi|mangue|poire|pomme|'bksl-nlbksl-nlassert fruitspy-undranges.estpy-undpresent("pomme")bksl-nlassert not fruitspy-undranges.estpy-undpresent("cerise")bksl-nlbksl-nl

A

Z