Arbre en Python

Bonjour tout le monde,
Je veux développer un arbre2-3 en python, si vous pouvez me donnez une idée sur l 'architecture

voilà ce que j'ai commence à faire

ps dans un arbre 2 3 chaque noeud a soit deux clefs( donc trois fils (noeud)) ou une clef est donc deux fils
Node.py

Code:

---

1 2 3 4 5 6 7 8

class Node(object):     def __init__(self):   //premiere clef self.First=0 self.secondCle=0

---

Tree.py

Code:

---

1 2 3 4 5 6 7 8 9 10

import Node class Tree(object):   def __init__(self):   self.root=Node.Node() self.fg=Node.Node() self.fd=Node.Node() self.fm=Node.Node()

---

donc là j'essaye de faire une méthode fin(clef) qui cherche la cle donnée en paramètre dans l arbre

si quelqu'un peut me donner une idée sur l'implémentation de l algorithme?
et si vous pouvez me dire ce que vous pensez par rapport à mes deux classes?

Merci d'avance

Bonjour,
Je ne comprend pas tout :
:
1°) Peux tu confirmer cette correction

Citation:

---

ps dans un arbre 2 3 chaque noeud a soit deux clefs( donc trois fils (noeud)) ou une clef est et donc deux fils

---

2°) Peux tu confirmer cette correction

Code:

---

1 2 3 4

//premiere clef self.FirstCle=0 //seconde clef self.secondCle=0

---

3°) Le but d'une classe est d'encapsuler toutes les méthodes liés à un objet, il me semble dommage de créer deux classes (node + tree), autant tout mettre dans une classe arbre (d'ailleur un node fait partie d'un arbre)
4°) Pourrais tu donner un exemple complet avec des nodes des clefs et un exemple de recherche car il est difficile de comprendre ce code:

Code:

---

1 2 3 4

self.root=Node.Node() self.fg=Node.Node() self.fd=Node.Node() self.fm=Node.Node()

---

5°) Tu pourrais utiliser une lib du style de xml.dom (sauf si tu veux créer quelque chose, ce que je comprends très bien).

Bon courage

Alex

Salut,

En cherchant sur Google, on trouve 2-3 Tree qui donne une idée d'architecture et de quantité de code à écrire.

Bon courage,
- W

Je ne suis pas un spécialiste des arbres et n’ai pas le temps de chercher comment sont organisés (“triés”) les nœuds d’un arbre 2 3 en fonction de leurs clés, donc je ne peux pas vous aider pour la fonction de recherche…

Par contre, s’il faut évidemment deux classes (une pour l’arbre, l’autre pour ses nœuds), il me semble que les membres fg/fd/fm doivent appartenir à Node, pas à Tree*! Sinon, comment voulez-vous obtenir une arborescence*?

Combien faut-il de classes ? On peut choisir différentes représentations:

Une classe "Tree" ou pas

La classe Tree n'est pas strictement nécessaire. Sans elle, l'arbre sera simplement représenté par son Noeud racine. La valeur None peut indiquer un arbre vide. C'est simple, mais cela nécessite une API de type fonctionnelle, en tout cas pour les méthodes qui peuvent changer le noeud racine. Par fonctionnelle, je veux dire que ces méthodes doivent retourner la nouvelle racine et qu'il faut écrire arbre = arbre.insert(...) par exemple.

Cela peut sembler contraignant, mais en poussant un peu plus loin on peut envisager en faire une structure de données persistante(= non mutable). Cela signifie qu'on ne modifie jamais un arbre existant; on retourne un nouvel arbre à la place. Cela a certains avantages et ce n'est pas aussi lourd qu'il y parait (il ne faut pas recopier tout l'arbre à chaque opération, seulement les noeuds qui sont modifiés).

A l'opposé, la classe Tree permet de présenter une API plus classique pour une structure de donnée mutable. Mais j'éviterais de définir trop de choses dans la classe Tree; la plupart de ses méthodes devraient simplement déléguer à la classe Noeud. La classe Tree ne serait qu'une couche au-dessus de l'API décrite ci-dessus.

Une classe Noeud ou plusieurs

Indépendamment de la présence ou l'absence de la classe Tree, dans une optique plus orientée objet, on peut définir des classes séparées pour un noeud à 2 enfants, un noeud à 3 enfants, et une feuille. Dans d'autres langages OO, les 3 classes hériteraient d'une classe Noeud abstraite, mais en Python, grâce au "duck typing", c'est optionnel. Cela peut néanmoins servir pour éviter la duplication de code dans les sous-classes.

Fait correctement, cela donnera un code plus facile à étendre et maintenir que de tout regrouper dans une seule classe "Noeud".