Arbre binaire⚓︎
On rappelle qu'il existe parfois des variations dans les définitions des structures arborescentes, et que pendant un exercice, il faut suivre celles données dans l'énoncé.
On peut définir un arbre binaire par :
- Soit un arbre binaire vide (souvent appelé nil).
- Soit c'est un nœud qui possède une étiquette et deux sous-arbres binaires, un à gauche, un à droite, possiblement vides l'un et/ou l'autre.
Les arbres binaires sont ici modélisés dans Python avec un style POO (Programmation Orientée Objet), et on vous demande de compléter la classe ArbreBinaire pour disposer des méthodes taille et hauteur.
Dans cet exercice, la définition de la hauteur de l'arbre binaire vide est 0.
Exemple
graph TD
A2{N1} --> A1{N2}
A2 --> N3{N3}
A1 --> N1{N4}
A1 --> N2{N5}
N3 --> x3( )
N3 --> y3( )
N2 --> x2( )
N2 --> y2( )
N1 --> x1( )
N1 --> y1( )Un arbre binaire de hauteur 3 et de taille 5.
class ArbreBinaire:bksl-nl def py-undpy-undinitpy-undpy-und(self, gauche=None, etiquette=None, droite=None):bksl-nl self.gauche = gauchebksl-nl self.etiquette = etiquettebksl-nl self.droite = droitebksl-nlbksl-nl def estpy-undvide(self):bksl-nl return self.etiquette is Nonebksl-nlbksl-nl def hauteur(self):bksl-nl if self.estpy-undvide():bksl-nl return 0bksl-nl else:bksl-nl return ...bksl-nlbksl-nl def taille(self):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlnil = ArbreBinaire()bksl-nlassert nil.estpy-undvide()bksl-nlassert nil.taille() == 0bksl-nlassert nil.hauteur() == 0bksl-nlbksl-nlnoeudpy-und1 = ArbreBinaire(nil, "1", nil)bksl-nlassert not noeudpy-und1.estpy-undvide()bksl-nlassert noeudpy-und1.taille() == 1bksl-nlassert noeudpy-und1.hauteur() == 1bksl-nlbksl-nlnoeudpy-und2 = ArbreBinaire(nil, "2", nil)bksl-nlbksl-nlarbrepy-undA1 = ArbreBinaire(noeudpy-und1, "A1", noeudpy-und2)bksl-nlnoeudpy-und3 = ArbreBinaire(nil, "3", nil)bksl-nlarbrepy-undA2 = ArbreBinaire(arbrepy-undA1, "A2", noeudpy-und3)bksl-nlassert not arbrepy-undA2.estpy-undvide()bksl-nlbksl-nlassert arbrepy-undA1.taille() == 3, f"{arbrepy-undA1.taille()}"bksl-nlassert arbrepy-undA1.hauteur() == 2, f"{arbrepy-undA1.hauteur()}"bksl-nlbksl-nlassert arbrepy-undA2.taille() == 5, f"{arbrepy-undA2.taille()}"bksl-nlassert arbrepy-undA2.hauteur() == 3, f"{arbrepy-undA2.hauteur()}"bksl-nlbksl-nlclass ArbreBinaire:bksl-nl def py-undpy-undinitpy-undpy-und(self, gauche=None, etiquette=None, droite=None):bksl-nl self.gauche = gauchebksl-nl self.etiquette = etiquettebksl-nl self.droite = droitebksl-nlbksl-nl def estpy-undvide(self):bksl-nl return self.etiquette is Nonebksl-nlbksl-nl def hauteur(self):bksl-nl if self.estpy-undvide():bksl-nl return 0bksl-nl else:bksl-nl return 1 + max(self.gauche.hauteur(), self.droite.hauteur())bksl-nlbksl-nl def taille(self):bksl-nl if self.estpy-undvide():bksl-nl return 0bksl-nl else:bksl-nl return 1 + self.gauche.taille() + self.droite.taille()bksl-nlbksl-nl
A
Z