Problème d'occurrence dans un arbre de recherche python
Résolu/Fermémamiemando Messages postés 33333 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 31 octobre 2024 - 1 déc. 2022 à 15:57
- Problème d'occurrence dans un arbre de recherche python
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Citizen code python - Accueil - Outils
- Recherche musique - Guide
- Recherche adresse - Guide
3 réponses
27 nov. 2022 à 14:19
bonjour, ton code fonctionne bien?
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.
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
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
27 nov. 2022 à 14:55
as-tu commencé à l'écrire?
27 nov. 2022 à 15:03
j'ai commence mais je suis bloque voici ce que j'ai écris comme base :
Modifié le 28 nov. 2022 à 09:55
Bonjour,
Tu as écris:
self.occurence = self.occurrance + 1
28 nov. 2022 à 12:56
à la limite, tu pourrais écrire
self.occurence += 1