Arbre naire en C++

Bonjour,

J'ai actuellement besoin pour mon projet de pouvoir gérer des arbres n-aires.
Il n'y a pas dans la STL en standard de telle conteneur, j'ai vu sur internet qu'il existe de nombreuses librairies ou sources pour réaliser ces arbres.

Quelle est selon vous la meilleure solution ? Mes impératifs sont :
- gestion d'arbre n-aires (pas uniquement binaire)
- chaque noeud de l'arbre pourra contenir n'importe quelle type de données (une struct dans mon cas précisément)
- on devra naturellement trouver les fonctions usuels inhérentes aux arbres : ajout d'un fils ainé, d'un frère, parcours de l'arbre selon plusieurs méthodes, recherche d'une valeur particulière dans l'arbre
- j'aimerais de plus pouvoir visualiser (meme dans une console en mode texte) l'arbre crée.

Petit précision je suis linux ubuntu 6.10 & gcc .
merci par avance ;)

Salut,

Je pense qu'il y a plusieurs réponses possibles et correctes à ton probleme. Cependant tu devrais préciser quels sont tes désir du point de vu de la performance de la simplicité du code etc ....

Ensuite essayer de nous présenter une piste que tu emprunterais par toi même pour que la discussion soit constructive et non pas simplement un code tout craché.

@ ++
Seb ;)

J'ai besoin d'un code le plus épuré possible. Plus simplement je ne veux pas une classe faisant des tonnes de fonctions qui ne me serviront à rien.

Concernant les performances on va dire que j'aurais des arbres à environ 10 branches avec une profondeur total de 15, j'ai besoin de pouvoir parcourir cette arbre assez rapidement pour trouver précisement une valeur. Mon appli doit pouvoir tourner en temps réel.

Concernant les pistes je me suis orienté sur ceci pour le moment :
www.up.univ-mrs.fr/wcpp/V1/Lecons/L19.pdf

J'ai adapté ce code à mon programme il marche très bien mais il me manque plusieurs fonctions, notemment une fonction permettant de visualiser "graphiquement (le mode texte m'irait amplement) l'arbre construit.

Sinon il existe aussi cette classe :
http://stlplus.sourceforge.net/stlplus/docs/ntree.html

mais je pense qu'il y'à beaucoup de choses dont je n'aurais pas l'utilité.

merci

Salut,

Une des solutions les plus simples, c'est tout simplement une structure ou une classe sous la forme de

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

struct noeud { noeud(type& data,noeud* parent=NULL):m_parent(parent), m_data(data){} ~noeud() { //il faut détruire les enfants for(unsigned int i=0;i<m_enfants.size();i++) delete m_enfants[i]; //par acquit de conscience m_parent=NULL; m_enfants.clear(); } noeud * parent; std::vector<noeud*> m_enfants; type m_data; bool IsSheet()const{return m_enfant.size()==0;} bool IsRoot()const{return m_parent==NULL;} };

---

Evidemment, dans l'exemple tel que je te l'ai donné, il n'y a aucune encapsulation, et ce n'est pas forcément des plus conseillé en orienté objet...

Mais, si tu utilises une classe au lieu d'une struct, il te suffira de mettre les accesseurs/mutateurs qui vont bien ;)

Si tes noeud doivent être triés, rien ne t'empeche de te tourner vers une std::map ou tout autre conteneur associatif s'adaptant à tes besoins ;)

Il me semble qu'en informatique, lorsqu'on parle de feuille, on ne fait pas référence à celle sur laquelle on écrit :wink:, mais plutot à celle effectivement de l'arbre (leaf)
(monsieur tatillon aujourd'hui)

Citation:

---

Envoyé par NewbiZ

Il me semble qu'en informatique, lorsqu'on parle de feuille, on ne fait pas référence à celle sur laquelle on écrit :wink:, mais plutot à celle effectivement de l'arbre (leaf)
(monsieur tatillon aujourd'hui)

---

Et tu as raison... simplement, monsieur fatigué aujourd'hui a écrit le premier terme qui lui est passé par la tete en pensant "feuille" :oops:

Ca va encore, tu aurais pu tomber sur 3ème possibilité :mouarf:

Citation:

---

Envoyé par NewbiZ

Ca va encore, tu aurais pu tomber sur 3ème possibilité :mouarf:

---

euh... foil?

un tas? facile, bonne complexité ... un tableau simple pour stocker

Autre piste à étudier également c'est si tu doit gérer plusieurs arbre n-aires dont chacun gère des type de données différentes.

C'est une question à se poser assez tôt car selon les cas du devra t'orienter vers un écriture de code un peu différente.

PS : si j'ai bien compris tes besoins, tu penses que ton programme ne gèreras pas un arbre volumineux en mémoire. En revanche arriverais tu as préciser tes contraintes pour le temps réel ?

Opérations synchrones / asynchrones (oui, oui en temps réel c'est parfois possible) ?
Fréquence des opérations sur l'arbre trés élevées / faibles ?
...