TNSI : TD Arbres Binaires, `class Noeud`⚓︎

On donne ci-dessous, le début d'une implémentation d'une classe Noeud qui modélise un Arbre Binaire en POO. Dans la modélisation proposée, l'instance Noeud(valeur) de la classe Noeud modélise l'Arbre Binaire sous-jacent au noeud dont l'étiquette est valeur (l'Arbre Binaire dont la racine est -d'étiquette- valeur).

Un Exemple & Code minimal⚓︎

L'Arbre Binaire ci-dessous, peut être modélisé par le code minimal situé encore plus bas.

Les instructions sous le __name__ donnent quelques exemples/indications sur la manière dont on souhaite pouvoir instancier et utiliser la classe Noeud:

class Noeud:
  """Un Noeud d'un Arbre Binaire"""
  def __init__(self, valeur, gauche=None, droit=None):
    self.valeur = valeur
    self.gauche = gauche
    self.droit = droit

  def get_gauche(self):
    return self.gauche

  def set_gauche(self):
    # À Compléter

  def get_droit(self):
    return self.droit

  def set_droit(self):
    # À Compléter

  def get_valeur(self):
    return self.valeur

if __name__ == "__main__":
    F = Noeud("F")
    A = F.set_gauche("A")
    C = F.set_droit("C")
    D = C.set_droit("D")
    E = D.set_gauche("E")
    B = A.set_droit("B")
    H = C.set_gauche("H")

Noeud Vide

Remarquer les valeurs par défaut des noeuds Gauche (gauche=None) et/ou Droit (droit=None). Ces conventions reviennent à implémenter un Noeud Vide par None, donc en particulier dans notre implémentation : un Noeud vide n'est PAS une instance de la classe Noeud mais un objet None dont le type est NoneType en Python.

Logique de l'Arbre Binaire avec une classe `Noeud`⚓︎

1°) Avec la classe Noeud proposée ci-dessus, quelle instruction python faut-il taper pour modéliser un noeud qui soit une feuille, d'étiquette 'F'? (les SAG et SAD sont donc égaux à None (donc vides)

2°) Créer une méthode set_gauche(self, valeur) qui :

Crée un noeud gauche dont l'étiquette vaut valeur
définit le noeud gauche en tant qu'enfant gauche du noeud self
renvoie le noeud nouvellement créé (gauche), càd renvoie une instance de la classe Noeud

3°) Créer une méthode set_droit(self, valeur) qui

Crée un noeud droit dont l'étiquette vaut valeur
définit le noeud droit en tant qu'enfant droit du noeud self
renvoie le noeud nouvellement créé (droit), càd renvoie une instance de la classe Noeud

4°) Créer une méthode vers_tuple(self) qui représente l'arbre Binaire comme un tuple
Exemple : La feuille 'F' pourra se représenter:

('F', None, None), ou bien, plus simplement
('F',) (idéalement)

5°) En déduire une méthode __repr__(self) pour représenter un arbre Binaire sous forme de tuple dans le Terminal

6°) Créer une méthode est_vide(self)->bool qui renvoie:

True si le noeud (self) est vide (None)
False sinon

7°) Créer une méthode est_feuille(self)->bool qui renvoie:

True si le noeud (self) est une feuille
False sinon

8°) Créer une méthode get_racine(self) qui renvoie la racine (absolue) de l'arbre auquel appartient le noeud self (en remontant tous les noeuds parents de self).
Remarque : La racine d'un arbre binaire est:

ou bien un noeud (non vide) si l'Arbre Binaire est non vide, càd une instance de la classe Noeud,
ou bien None, si l'Arbre Binaire est vide

Hint / Aide

On pourra pour cela, ajouter judicieusement un atttribut self.parent aux bons endroits (par ex. dans les méthodes get_gauche(), set_gauche(), get_droit(), set_droit(), etc..), pour être en mesure à tout instant de déterminer le noeud (/arbre binaire) parent de tout noeud (arbre binaire).

Paramètres de l'Arbre Binaire⚓︎

9°) Créer une méthode profondeur(self)->int qui renvoie la profondeur du noeud courant self (par rapport à la racine absolue de l'arbre obtenue par get_racine() )

10°) Créer une méthode hauteur(self)->int qui calcule la hauteur de l'arbre sous le noeud self

11°) Créer une méthode taille(self)->int qui renvoie la taille de l'arbre sous le noeud self

Parcours d'Arbres Binaires⚓︎

Parcours en Largeur⚓︎

Implémentation avec une procédure récursive `niveau()`⚓︎

12°) a°) Créer une procédure récursive niveau(self, niveau)->None qui :

reçoive en entrée un noeud self et le niveau souhaité (relatif au noeud self)
affiche dans le Terminal (les étiquettes des noeuds d') situés au niveau niveau depuis le noeud self (convention: la racine est située au niveau 0 et pas 1)

b°) Modifier la procédure récursive précédente niveau(self)->None de sorte que:

elle reçoive en entrée un noeud self
à la fin de son exécution, la variable de classe Noeud.niveau doit contenir la liste ordonnée des étiquettes des noeuds rencontrés dans l'ordre d'un parcours en largeur.

Col

Hint / Aide

On pourra par exemple (ou pas, si vous trouvez mieux..) définir une variable de classe, dans le constructeur __init__(), pour ensuite y stocker les (étiquettes des) noeuds rencontrés durant le parcours:

# Syntaxe variable de classe:
Noeud.niv = []

13°) a°) En déduire une méthode récursive get_niveau(self)->list telle que:

reçoit en entrée un noeud self
renvoie en sortie une liste des étiquettes des noeuds rencontrés lors d'un parcours en largeur depuis le noeud self

b°) Stocker une liste d'étiquettes plutôt qu'une liste de noeuds, lors d'un parcours, peut poser un problème dans un contexte général.

Pourquoi?
Comment résoudre ce problème? Faites-le

14°) En déduire une procédure (itérative) largeur(self)->None telle que:

elle reçoive en entrée un noeud self
à la fin de son exécution, la variable de classe Noeud.largeur contienne une liste des étiquettes des noeuds rencontrés dans l'ordre d'un parcours en largeur de l'arbre, depuis le noeud self

Col

Hint / Aide

# Syntaxe variable de classe:
Noeud.large = []

Question 15°)\(\rightarrow\) Exemples de Résultats Attendus

En déduire une méthode (itérative) get_largeur(self)->list telle que:

Elle reçoive en entrée un noeud self
Elle renvoie en sortie une liste des étiquettes des noeuds rencontrés lors d'un parcours en largeur depuis le noeud self

F.get_largeur() renvoie : ['F', 'A', 'C', 'B', 'H', 'D', 'E']
C.get_largeur() renvoie : ['C', 'H', 'D', 'E']

Implémentation avec une File⚓︎

16°) Créer une méthode itérative largeur(self) qui réalise un parcours en largeur de l'arbre depuis le noeud self

L'algorithme de parcours en largeur itératif peut s'implémenter grâce à des Files.

largeur(self) {
   f = FileVide
   f.enfiler(self.racine())
   Tant que (la File f n'est pas vide) {
       noeud = f.defiler()
       Visiter(noeud)                        //On choisit de faire une opération
       Si (noeud.gauche n'est pas vide) Alors
           f.enfiler(noeud.gauche)
       Si (noeud.droit n'est pas vide) Alors
           f.enfiler(noeud.droit)
   }
}

Parcours Préfixe (en Profondeur)⚓︎

17°) a°) Créer une procédure récursive prefixe(self)->None qui :

reçoive en entrée un noeud self
affiche dans le Terminal (les étiquettes des noeuds d') un parcours en profondeur préfixe de l'arbre depuis le noeud self

b°) Modifier la procédure (itérative) précédente prefixe(self)->None de sorte que:

elle reçoive en entrée un noeud self
à la fin de son exécution, la variable de classe Noeud.pref contienne une liste des étiquettes des noeuds rencontrés dans l'ordre d'un parcours préfixe, depuis le noeud self

Col

Hint / Aide

# Syntaxe variable de classe:
Noeud.pref = []

Question 18°)a°)\(\rightarrow\) Exemples de Résultats Attendus

En déduire une méthode récursive get_prefixe(self)->list qui:

reçoit en entrée un noeud self
renvoie en sortie la liste des étiquettes des noeuds rencontrés dans l'ordre d'un parcours préfixe, depuis le noeud self

F.get_prefixe() renvoie ['F', 'A', 'B', 'C', 'H', 'D', 'E']
C.get_prefixe() renvoie ['C', 'H', 'D', 'E']

b°) Stocker une liste d'étiquettes plutôt qu'une liste de noeuds, lors d'un parcours, peut poser un problème dans un contexte général.

Pourquoi?
Comment résoudre ce problème? Faites-le

Parcours Infixe (en Profondeur)⚓︎

19°) a°) Créer une procédure récursive infixe(self)->None qui :

reçoive en entrée un noeud self
affiche dans le Terminal (les étiquettes des noeuds d') un parcours en profondeur infixe de l'arbre depuis le noeud self

b°) Modifier la procédure (itérative) précédente infixe(self)->None de sorte que:

elle reçoive en entrée un noeud self
à la fin de son exécution, la variable de classe Noeud.inf contienne une liste des étiquettes des noeuds rencontrés dans l'ordre d'un parcours infixe, depuis le noeud self

Col

Hint / Aide

On pourra par exemple (ou pas, si vous trouvez mieux..) définir une variable de classe, dans le constructeur __init__(), pour ensuite y stocker les (étiquettes des) noeuds rencontrés durant le parcours:

# Syntaxe variable de classe:
Noeud.inf = []

Question 20°)a°)\(\rightarrow\) Exemples de Résultats Attendus

En déduire une méthode récursive get_infixe(self)->list qui:

reçoit en entrée un noeud self
renvoie en sortie la liste des étiquettes des noeuds rencontrés dans l'ordre d'un parcours infixe, depuis le noeud self

F.get_infixe() renvoie ['A', 'B', 'F', 'H', 'C', 'E', 'D']
C.get_infixe() renvoie ['H', 'C', 'E', 'D']

b°) Stoker une liste d'étiquettes des noeuds plutôt qu'une liste de noeuds, lors d'un parcours, pose toujours le même problème que le parcours préfixe. Résolvez ce problème.

Parcours Postfixe (en Profondeur)⚓︎

21°) a°) Créer une procédure récursive postfixe(self)->None qui :

reçoive en entrée un noeud self
affiche dans le Terminal (les étiquettes des noeuds d') un parcours en profondeur postfixe de l'arbre depuis le noeud self

b°) Modifier la procédure (itérative) précédente postfixe(self)->None de sorte que:

elle reçoive en entrée un noeud self
à la fin de son exécution, la variable de classe Noeud.post contienne une liste des étiquettes des noeuds rencontrés dans l'ordre d'un parcours postfixe, depuis le noeud self

Col

Hint / Aide

# Syntaxe variable de classe:
Noeud.post = []

Question 22°)a°)\(\rightarrow\) Exemples de Résultats Attendus

En déduire une méthode récursive get_postfixe(self)->list qui:

reçoit en entrée un noeud self
renvoie en sortie la liste des étiquettes des noeuds rencontrés dans l'ordre d'un parcours postfixe, depuis le noeud self

F.get_postfixe() renvoie ['B', 'A', 'H', 'E', 'D', 'C', 'F']
C.get_postfixe() renvoie ['H', 'E', 'D', 'C']

b°) Stoker une liste d'étiquettes des noeuds plutôt qu'une liste de noeuds, lors d'un parcours, pose toujours les mêmes problèmes que les précédent parcours. Pourquoi? et Résolvez ce problème.

TNSI : TD Arbres Binaires, class Noeud⚓︎

Un Exemple & Code minimal⚓︎

Logique de l'Arbre Binaire avec une classe Noeud⚓︎

Paramètres de l'Arbre Binaire⚓︎

Parcours d'Arbres Binaires⚓︎

Parcours en Largeur⚓︎

Implémentation avec une procédure récursive niveau()⚓︎

Implémentation avec une File⚓︎

Parcours Préfixe (en Profondeur)⚓︎

Parcours Infixe (en Profondeur)⚓︎

Parcours Postfixe (en Profondeur)⚓︎

TNSI : TD Arbres Binaires, `class Noeud`⚓︎

Logique de l'Arbre Binaire avec une classe `Noeud`⚓︎

Implémentation avec une procédure récursive `niveau()`⚓︎