Classe arbre

Voici une classe Python complète pour représenter un arbre binaire. La classe est construite à partir d'une liste donnée en paramètre. Elle inclut plusieurs méthodes utiles pour manipuler et parcourir l'arbre.

class Noeud:
    def __init__(self, valeur):
        """Initialise un nœud avec une valeur et des enfants gauche et droit."""
        self.valeur = valeur
        self.gauche = None
        self.droite = None


class ArbreBinaire:
    def __init__(self, liste):
        """
        Construit un arbre binaire à partir d'une liste donnée.
        La liste est interprétée comme un arbre en parcours préfixe : [racine, gauche, droite].
        """
        self.racine = self._construire_arbre(liste)

    def _construire_arbre(self, liste):
        """
        Fonction récursive pour construire l'arbre binaire.
        La liste est consommée au fur et à mesure de la construction.
        """
        if not liste:
            return None
        valeur = liste.pop(0)
        if valeur is None:  # Si la valeur est None, on retourne un nœud vide
            return None
        noeud = Noeud(valeur)
        noeud.gauche = self._construire_arbre(liste)
        noeud.droite = self._construire_arbre(liste)
        return noeud

    def parcours_prefixe(self):
        """Parcourt l'arbre en préfixe et renvoie une liste des valeurs."""
        resultat = []
        self._parcours_prefixe(self.racine, resultat)
        return resultat

    def _parcours_prefixe(self, noeud, resultat):
        if noeud:
            resultat.append(noeud.valeur)
            self._parcours_prefixe(noeud.gauche, resultat)
            self._parcours_prefixe(noeud.droite, resultat)

    def parcours_infixe(self):
        """Parcourt l'arbre en infixe et renvoie une liste des valeurs."""
        resultat = []
        self._parcours_infixe(self.racine, resultat)
        return resultat

    def _parcours_infixe(self, noeud, resultat):
        if noeud:
            self._parcours_infixe(noeud.gauche, resultat)
            resultat.append(noeud.valeur)
            self._parcours_infixe(noeud.droite, resultat)

    def parcours_postfixe(self):
        """Parcourt l'arbre en postfixe et renvoie une liste des valeurs."""
        resultat = []
        self._parcours_postfixe(self.racine, resultat)
        return resultat

    def _parcours_postfixe(self, noeud, resultat):
        if noeud:
            self._parcours_postfixe(noeud.gauche, resultat)
            self._parcours_postfixe(noeud.droite, resultat)
            resultat.append(noeud.valeur)

    def hauteur(self):
        """Renvoie la hauteur de l'arbre."""
        return self._hauteur(self.racine)

    def _hauteur(self, noeud):
        if not noeud:
            return 0
        gauche = self._hauteur(noeud.gauche)
        droite = self._hauteur(noeud.droite)
        return max(gauche, droite) + 1

    def inserer(self, valeur):
        """Insère une valeur dans l'arbre binaire de recherche."""
        self.racine = self._inserer(self.racine, valeur)

    def _inserer(self, noeud, valeur):
        if not noeud:
            return Noeud(valeur)
        if valeur < noeud.valeur:
            noeud.gauche = self._inserer(noeud.gauche, valeur)
        else:
            noeud.droite = self._inserer(noeud.droite, valeur)
        return noeud

    def rechercher(self, valeur):
        """Recherche une valeur dans l'arbre."""
        return self._rechercher(self.racine, valeur)

    def _rechercher(self, noeud, valeur):
        if not noeud:
            return False
        if noeud.valeur == valeur:
            return True
        if valeur < noeud.valeur:
            return self._rechercher(noeud.gauche, valeur)
        return self._rechercher(noeud.droite, valeur)

    def afficher(self):
        """Affiche l'arbre niveau par niveau (parcours en largeur)."""
        if not self.racine:
            print("Arbre vide")
            return
        queue = [self.racine]
        while queue:
            noeud = queue.pop(0)
            if noeud:
                print(noeud.valeur, end=" ")
                queue.append(noeud.gauche)
                queue.append(noeud.droite)
            else:
                print("None", end=" ")
        print()


# Exemple d'utilisation
liste_arbre = [10, 5, 3, None, None, 7, None, None, 15, None, 20]
arbre = ArbreBinaire(liste_arbre)

# Affichage des parcours
print("Parcours préfixe :", arbre.parcours_prefixe())
print("Parcours infixe :", arbre.parcours_infixe())
print("Parcours postfixe :", arbre.parcours_postfixe())

# Afficher l'arbre
print("Arbre (parcours en largeur) :")
arbre.afficher()

# Autres opérations
print("Hauteur de l'arbre :", arbre.hauteur())
arbre.inserer(8)
print("Parcours infixe après insertion :", arbre.parcours_infixe())
print("Recherche de 8 dans l'arbre :", arbre.rechercher(8))

Explications des méthodes

• Le constructeur initialise l'arbre en utilisant une liste en entrée.
• La méthode _construire_arbre est récursive et construit l'arbre en consommant la liste.
• Les méthodes de parcours (préfixe, infixe, postfixe) permettent d'explorer les nœuds dans différents ordres.
• Les méthodes inserer et rechercher permettent d'ajouter et de rechercher une valeur dans l'arbre.
• La méthode hauteur calcule la profondeur maximale de l'arbre.
• La méthode afficher montre la structure de l'arbre avec un parcours en largeur.

N'hésitez pas à demander des précisions ou des modifications !