Problème d'occurrence dans un arbre de recherche python

Résolu/Fermé
momo9213 Messages postés 16 Date d'inscription mardi 26 avril 2022 Statut Membre Dernière intervention 27 novembre 2022 - 27 nov. 2022 à 14:16
mamiemando Messages postés 33419 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 9 décembre 2024 - 1 déc. 2022 à 15:57
import classe_file

class Noeud:
    def __init__(self, valeur):
        '''Méthode constructeur pour la classe Noeud.
        Paramètre d'entrée : valeur
        valeur : int ou str'''
        self.occurrance = 1
        self.valeur = valeur
        self.gauche = None
        self.droit = None
   
    def getValeur(self):
        '''Méthode accesseur pour obtenir la valeur du noeud
        Aucun paramètre en entrée'''
        return self.valeur
    def getValeurs(self):
        '''Méthode accesseur pour obtenir la valeur du noeud
        Aucun paramètre en entrée'''
        return self.valeur,self.occurrence
    def incrOccurrence(self):
        

    def droitExiste(self):
        '''Méthode renvoyant True si l'enfant droit existe
        Aucun paramètre en entrée'''
        return (self.droit is not None)
   
    def gaucheExiste(self):
        '''Méthode renvoyant True si l'enfant gauche existe
        Aucun paramètre en entrée'''
        return (self.gauche is not None)

    def inserer(self,cle):
        '''Méthode d'insertion de clé dans un arbre binaire de recherche
        Paramètre d'entrée : valeur
        valeur : int ou str'''
        if cle < self.valeur:
            # on insère à gauche
            if self.gaucheExiste():
                # on descend à gauche et on recommence le test initial
                self.gauche.inserer(cle)
            else:
                # on crée un fils gauche
                self.gauche = Noeud(cle)
        elif cle > self.valeur:
            # on insère à droite
            if self.droitExiste():
                # on descend à droite et on recommence le test initial
                self.droit.inserer(cle)
            else:
                # on crée un fils droit
                self.droit = Noeud(cle)

    def recherche(self,cle):
        '''Méthode de recherche de clé dans un arbre binaire de recherche
        Paramètre d'entrée : valeur
        valeur : int ou str'''
        if cle == self.valeur:
            # la clé est la valeur de la racine
            return True
        elif cle < self.valeur:
            # on recherche à gauche si l'enfant gauche existe
            if self.gaucheExiste():
                # on descend à gauche et on recommence la recherche
                return self.gauche.recherche(cle)
            else:
                # la clé n'est pas dans l'arbre
                return False
        elif cle > self.valeur:
            # on recherche à droite si l'enfant droit existe
            if self.droitExiste():
                # on descend à droite et on recommence la recherche
                return self.droit.recherche(cle)
            else:
                # la clé n'est pas dans l'arbre
                return False

    def __str__(self):
        """Méthode récursive pour obtenir une représentation lisible
        d'un arbre.
        Aucun paramètre en entrée
        Syntaxe :
            >>> print(arbre)"""
        # Keep a list of lines
        lines = list()
        lines.append(str(self.valeur))
        # Get left and right sub-trees
        l = str(self.gauche).split('\n')
        r = str(self.droit).split('\n')
        # Append first left, then right trees
        for branch in r, l:
            # Suppress Pipe on right branch
            alt = '| ' if branch is r else '  '
            for line in branch:
                # Special prefix for first line (child)
                prefix = '+-' if line is branch[0] else alt
                lines.append(prefix + line)
        # Collapse lines
        return '\n'.join(lines)
   
    def taille(self):
        """Méthode récursive pour calculer la taille de l'arbre.
        Aucun paramètre en entrée
        En sortie : un entier"""
        if self.gaucheExiste() and self.droitExiste():
            return 1 + self.gauche.taille() + self.droit.taille()
        elif self.gaucheExiste():
            return 1 + self.gauche.taille()
        elif self.droitExiste():
            return 1 + self.droit.taille()
        else:
            return 1

    def hauteur(self):
        """Méthode récursive pour calculer la hauteur de l'arbre.
        Aucun paramètre en entrée
        En sortie : un entier"""
        if self.gaucheExiste() and self.droitExiste():
            return 1 + max(self.gauche.hauteur(), self.droit.hauteur())
        elif self.gaucheExiste():
            return 1 + self.gauche.hauteur()
        elif self.droitExiste():
            return 1 + self.droit.hauteur()
        else:
            return 1
       
       
       
       
       
        # getValeurs() : renvoie la valeur du nœud et son occurrence.
        # incrOccurrence() : incrémente l’occurrence d’un nœud.
        # donnerOccurrence(cle) : renvoie l’occurrence d’une clé.
        # totalOccurrence() : renvoie le nombre total d’occurrences du texte.
   
    def prefixe(self, liste_noeuds_pre):
        """Méthode récursive pour parcourir l'arbre de façon préfixe :
           Racine, Enfant gauche, Enfant droit.
           Entrée : une liste vide
           Sortie : la liste des noeuds parcourus"""
        if self == None:
            return
        else:
            # ajout de la racine
            liste_noeuds_pre.append(self.getValeur())
            # on descend dans le sous-arbre gauche
            if self.gaucheExiste():
                self.gauche.prefixe(liste_noeuds_pre)
            # on descend dans le sous-arbre droit
            if self.droitExiste():
                self.droit.prefixe(liste_noeuds_pre)

    def infixe(self, liste_noeuds_inf):
        """Méthode récursive pour parcourir l'arbre de façon infixe :
           Enfant gauche, Racine, Enfant droit.
           Entrée : une liste vide
           Sortie : la liste des noeuds parcourus"""
        if self == None:
            return
        else:
            # on descend dans le sous-arbre gauche
            if self.gaucheExiste():
                self.gauche.infixe(liste_noeuds_inf)
            # ajout de la racine
            liste_noeuds_inf.append(self.getValeur())
            # on descend dans le sous-arbre droit
            if self.droitExiste():
                self.droit.infixe(liste_noeuds_inf)

    def suffixe(self, liste_noeuds_suf):
        """Méthode récursive pour parcourir l'arbre de façon suffixe :
           Enfant gauche, Enfant droit, Racine.
           Entrée : une liste vide
           Sortie : la liste des noeuds parcourus"""
        if self == None:
            return
        else:
            # on descend dans le sous-arbre gauche
            if self.gaucheExiste():
                self.gauche.suffixe(liste_noeuds_suf)
            # on descend dans le sous-arbre droit
            if self.droitExiste():
                self.droit.suffixe(liste_noeuds_suf)
            # ajout de la racine
            liste_noeuds_suf.append(self.getValeur())

    def largeur(self):
        """Méthode itérative pour parcourir l'arbre en largeur :
           Entrée : rien
           Sortie : la liste des noeuds parcourus"""
        # initialisation de la liste de noeuds parcourus et de la file
        liste_noeuds_largeur = []
        ma_file = classe_file.File()
        # on ajoute le noeud actuel dans la file
        ma_file.ajouter(self)
        # tant que la file n'est pas vide
        while not(ma_file.fileVide()):
            noeud = ma_file.retirer()
            liste_noeuds_largeur.append(noeud.getValeur())
            # si l'enfant gauche existe, on l'ajoute à la file
            if (noeud.gaucheExiste()):
                ma_file.ajouter(noeud.gauche)
            # si l'enfant droit existe, on l'ajoute à la file
            if (noeud.droitExiste()):
                ma_file.ajouter(noeud.droit)
        # on renvoie la liste des noeuds parcourus
        return liste_noeuds_largeur

bonjour j'essaye de faire un programme qui transforme un texte en arbre et j'essaye de faire une fonction qui recherche le mot et qui dis combien il est dans l'arbre (donc son occurence) 

merci d'avance

(ps:le premiere code est le code qui permet de le transforme et d'utiliser des fonction et le second permet de l'index (l'incrementer))

# importation de la classe Noeud d'un ABR
import arbre_binaire_recherche as abr

# importation de la bibliothèque Expressions Régulières
import re

def index_roman(file):
    ''' Cette fonction crée un arbre binaire de recherche à partir
    d'un fichier texte, en classant les mots par ordre alphabétique.
    Paramètre d'entrée : un fichier texte
    Sortie : un ABR'''
    # récupération du texte dans le fichier
    texte = open(file,'r',encoding='utf-8')
    tableau = texte.readlines()
    texte.close()
       
    # initialisation de l'arbre binaire de recherche
    arbre = None

    # Boucle : pour chaque ligne du texte
    for ligne in tableau:
        # formatage du fichier texte
        # passage en minuscule
        ligne = ligne.lower()
        # on récupère une liste de mots, en enlevant tous les séparateurs connus
        liste_mots = re.split('[;,.?!\"\'\-\%\n() `&]',ligne)
        # on enlève les mots vides dans la liste de mots
        while '' in liste_mots:
            liste_mots.remove('')
       
        # pour chaque mot dans la liste de mots
        for i in range(len(liste_mots)):
            if arbre == None:
                arbre = abr.Noeud(liste_mots[0])
            else:
                arbre.inserer(liste_mots[i])
    return arbre
A voir également:

3 réponses

yg_be Messages postés 23383 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 9 décembre 2024 Ambassadeur 1 556
27 nov. 2022 à 14:19

bonjour, ton code fonctionne bien?

0
momo9213 Messages postés 16 Date d'inscription mardi 26 avril 2022 Statut Membre Dernière intervention 27 novembre 2022
27 nov. 2022 à 14:31

oui mais il me manque la fonction qui me donne le nombre de fois qu'il y a le mot quand j'utilse la fonction recherche

0
yg_be Messages postés 23383 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 9 décembre 2024 1 556 > momo9213 Messages postés 16 Date d'inscription mardi 26 avril 2022 Statut Membre Dernière intervention 27 novembre 2022
27 nov. 2022 à 14:55

as-tu commencé à l'écrire?

0
momo9213 Messages postés 16 Date d'inscription mardi 26 avril 2022 Statut Membre Dernière intervention 27 novembre 2022 > yg_be Messages postés 23383 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 9 décembre 2024
27 nov. 2022 à 15:03

j'ai commence mais je suis bloque voici  ce que j'ai écris comme base :

    def incrOccurrence(self):
        for x in arbre :
            if (x== cle):
                self.occurence = self.occurrance + 1
        return self.occurence
0
Phil_1857 Messages postés 1872 Date d'inscription lundi 23 mars 2020 Statut Membre Dernière intervention 28 février 2024 168 > momo9213 Messages postés 16 Date d'inscription mardi 26 avril 2022 Statut Membre Dernière intervention 27 novembre 2022
Modifié le 28 nov. 2022 à 09:55

Bonjour,

Tu as écris:

self.occurence = self.occurrance + 1

0
Phil_1857 Messages postés 1872 Date d'inscription lundi 23 mars 2020 Statut Membre Dernière intervention 28 février 2024 168 > Phil_1857 Messages postés 1872 Date d'inscription lundi 23 mars 2020 Statut Membre Dernière intervention 28 février 2024
28 nov. 2022 à 12:56

à la limite, tu pourrais écrire

self.occurence += 1

0
PierrotLeFou
28 nov. 2022 à 01:47

Tu nous demandes de tester ton code?
Commences par placer un seul élément dans ton arbre et testes toutes les fonctions.
Ensuite, insères un second élément que tu choisira volontairement comme étant à la gauche, puis refais le test.
Refais le test en insérant plutôt à la droite.
Si ça marche jusque là, essaies d'en placer d'autres en contrôlant toujours la position attendue.

0
mamiemando Messages postés 33419 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 9 décembre 2024 7 809
1 déc. 2022 à 15:57

Bonjour,

Il suffit dans ton code de rajouter dans la fonction insérer le cas cle == self.valeur. Si ce cas est vrai, alors on incrémente le compteur. Le compteur est initialisé à 1 au moment où tu ajoutes le nœud dans ton arbre.

En terme de design :

  • je trouve que ta fonction d'insertion devrait idéalement retourner la feuille ajoutée
  • il est possible de factoriser la recherche et l'insertion. L'insertion consiste à faire une recherche en best effort. Soit le nœud trouvé est le bon, et dans ce cas il suffit d'incrémenter son compteur. Soit on a atteint une feuille (dont la valeur n'est pas la clé) et dans ce cas, on lui greffe la feuille correspondant au mot en cours d'insertion.
  • les méthodes gaucheExiste et droiteExiste sont correctes mais alourdissent le code, personnellement je m'en passerais
  • il serait plus propre de distinguer la notion d'arbre et de nœud en faisant deux classes séparées.

Ci-dessous, voici à quoi ça pourrait ressembler. Je te laisse le soin de retranscrire les marches préfixe / infixe / postfixe que je renommerais ces méthodes walk_prefix, walk_infix, walk_postfix et j'ajouterais une méthode walk qui appelle l'une des trois. Idem concernant le calcul du nombre de nœud (que je renommerais num_vertices ou num_nodes) et de la hauteur de l'arbre (que je renommerais height).

class Node:
    def __init__(self, key: str):
        self.n = 1         # Nombre d'occurrences
        self.key = key     # Clé
        self.left = None   # Fils gauche
        self.right = None  # Fils droit

    def find(self, key: str) -> tuple:
        if key < self.key:
            if self.left:
                return self.left.find(key)
            else:
                return (self, False)
        elif key > self.key:
            if self.right:
                return self.right.find(key)
            else:
                return (self, False)
        else:
            return (self, True)

    def insert(self, key: str):
        (node, found) = self.find(key)
        if found:
            assert key == node.key
            node.n += 1
            return node
        else:
            leaf = Node(key)
            if key < self.key:
                node.left = leaf
            elif key > self.key:
                node.right = leaf
            return leaf

    def __str__(self) -> str:
        return f"'{self.key}' ({self.n})"


class Tree:
    def __init__(self, words: iter = None):
        self.root = None
        if words:
            self.inserts(words)

    def inserts(self, words: iter):
        for word in words:
            self.insert(word)

    def insert(self, word: str) -> tuple:
        if self.root is None:
            self.root = Node(word)
            return self.root
        else:
            return self.root.insert(word)

    def __str__(self) -> str:
        def to_str(node, indent: int = 0) -> str:
            l = [" " * (indent * 4) + str(node)]
            if node.left:
                l.append(to_str(node.left, indent + 1))
            if node.right:
                l.append(to_str(node.right, indent + 1))
            return "\n".join(l)
        return to_str(self.root) if self.root else ""

tree = Tree()
tree.inserts(["abc", "aba", "abb", "abc", "aba", "xyz"])
print(tree)

Résultat :

'abc' (2)
    'aba' (2)
        'abb' (1)
    'xyz' (1)

Bonne chance

0