Problème d'occurrence dans un arbre de recherche python
Résolu- Problème d'occurrence dans un arbre de recherche python
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Citizen code python avis - Accueil - Outils
- Recherche photo - Guide
- Moteur de recherche 1fichier ✓ - Forum Réseaux sociaux
- Probleme recherche chaine tv tcl - Forum TV & Vidéo
3 réponses
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.
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
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
as-tu commencé à l'écrire?
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.occurenceBonjour,
Tu as écris:
self.occurence = self.occurrance + 1
à la limite, tu pourrais écrire
self.occurence += 1