arbre binaire parfait

Bonjour à tous :)

J'essaie de créer un arbre binaire parfait en C++ et pour cela j'ai créer une classe "Noeud" et une classe "Arbre".
Afin de traiter chaque noeud un par un, je voudrais créer une file. Pour l'instant la seule syntaxe que j'ai est : std :: queue<Type> nom_de_la_file

Voici ma question : Est-il possible de créer une file de type "Noeud" ? Si oui, comment ?

Merci d'avance pour votre aide !

Heu, c'est quoi la question ???

Citation:

---

Est-il possible de créer une file de type "Noeud" ?

---

Heu, bin oui :

Code:

---

std :: queue<Noeud> nom_de_la_file;

---

:aie::weird::aie::weird:

@bacelar: ou bien :mrgreen:

Code:

---

1 2 3 4 5

class Noeud : public std::queue { // <- Or private or protected   // All stuffs here   };

---

Si on veut renommer un type, je ne suis pas fan d'hériter publiquement d'une classe dont le destructeur n'est pas virtuel (par principe) ; en hériter de façon privée en re-exposant l'interface n'est pas une solution élégante non plus.

using de C++11 permet de faire le travail :

Code:

---

1 2	template <class T> using noeud = std::queue<T>;

---

---

Pour le problème original, ta classe avec std::queue ressemblera à :

Code:

---

1 2 3 4 5 6 7 8 9

template <class T> class noeud { private: T m_data; std::queue<noeud<T>> m_children; public: // ... };

---

Et j'utiliserais probablement std::vector<T> au lieu de std::queue<T>.

---

Et comme c'est un arbre binaire, j'utiliserais plutôt un truc qui ressemble à :

Code:

---

1 2 3 4 5 6 7 8 9 10

template <class T> class noeud { private: T m_data; optional<noeud<T>> m_left; optional<noeud<T>> m_right; public: // ... };

---

Avec optional<T> une classe qui permet d'avoir un T ou pas. Et si le T est "vide", on a le pointeur nullptr. Personnellement j'appelle cette classe optional_ptr même si optional_in_ptr ou optional_with_minimal_size_if_not serait plus juste.
L'autre solution pour optional serait d'avoir le T serait d'avoir le T + un booléen. (Il me semble que c'est le différence entre boost::optional et std::optional.) Cette solution ici ne compilerait pas à cause de la récursivité.

Heu, bin oui :

Code:

---

std :: queue<Noeud> nom_de_la_file;

---

C'est exactement ce que j'avais fait justement, mais ça ne compilait pas. J'ai fini par me rendre compte que le problème ce n'était pas la file en elle même mais plutôt ce que je mettais dedans...


@Ehonn
"Et j'utiliserais probablement std::vector<T> au lieu de std::queue<T>."

J'aurais aussi préféré faire des vecteurs plutôt que des files mais ma prof a insisté pour qu'on fasse une file, elle disait que c'était plus adapté pour faire un arbre binaire... Mais je pense que dans tous les cas je serais obligée de faire des vecteurs quand même, sinon je ne vois pas comment je pourrais afficher mon arbre par la suite


En tout cas merci pour vos réponses

Avec un peu de code et le message d'erreur exact, on est meilleurs à trouver le problème.

Voici le code de ma fonction generer() et les messages d'erreurs

ligne 23 error : 'filsg' was not declared in this scope
ligne 24 error : 'filsd' was not declared in this scope

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

noeud* arbre :: generer() // cette méthode va générer l'arbre entier (la racine et les noeuds gauches et droits) { racine = creer(1);   int h; // profondeur (=hauteur) de l'arbre cout << "Entrer la profondeur (hauteur) de l'arbre binaire parfait : "; cin >> h;   std :: queue<noeud> file; // file de type "noeud"   while (nb_noeud < ((2^(h+1))-1)) { int i; int val_gauche = 2*i; int val_droit = 2*i+1;     file.push(*racine);   racine->filsg = creer(val_gauche); racine->filsd = creer(val_droit);   file.push(*filsg); file.push(*filsd);   file.pop();   }

---

- on sait pas d'où sort racine
- tu push une copie
- puis tu modifies l'original
ça fait déjà un paquet de problèmes avant de savoir par quelle magie tu essayes d'assigner une valeur à des variables membres filsg et filsd qui n'existent pas. :weird:

Salut,

De manière générale, un arbre binaire parfait est très difficile à obtenir, pour une raison bien simple : on ne peut l'obtenir qu'avec des nombres bien particuliers d'éléments (1, 3, 7, 15, ...). Le plus souvent, on a de la chance d'arriver à obtenir, c'est ce que l'on appelle un arbre équilibré : un arbre dans lequel il n'y a au maximum qu'un niveau d'écart entre la feuille "la plus basse" et la feuille "la plus haute" (ce qui se rapproche beaucoup plus du "cas général" ;) ).

Sinon, il n'y a pas vraiment de miracle: le plus sur moyen de parcourir un arbre binaire reste malgré tout d'avoir recours à la récursivité. Tu as alors trois solutions principales :

La solution prefixe : tu commence par traitrer le noeud sur lequel tu est avant d'aller voir chacun des noeuds enfants (s'ils existent), sous une forme proche de

Code:

---

1 2 3 4 5 6 7 8 9 10

void prefix(Noeud * actuel){ /* traiter la valeur du noeud actuelle */ if (gauche){ prefix(gauche); } if (droite){ prefix(droite); } }

---

la solution postfixe : tu commence par traiter les noeuds enfants (s'ils existent) avant de traiter le noeud actuel, sous une forme proche de

Code:

---

1 2 3 4 5 6 7 8 9 10

void postfix(Noeud * actuel){ if (gauche){ postfix(gauche); } if (droite){ postfix(droite); } /* traiter la valeur du noeud actuelle */ }

---

et enfin la solution infixe : tu traites d'abord l'un des noeuds enfant( s'il existe, bien sur), puis tu traites la valeurs du noeud courant, et enfin tu traite l'autre noeud enfant( s'il existe, bien sur) sous une forme proche de

Code:

---

1 2 3 4 5 6 7 8 9

void infix(Noeud * actuel){ if (gauche){ infix(gauche); } /* traiter la valeur du noeud actuelle */ if (droite){ infix(droite); } }

---

Une fois que tu as ces trois schémas en tête, il t'appartient de savoir ce que tu veux faire afin de pouvoir choisir celui qui correspond à ta situation ;)

NOTA: il t'est, bien sur, toujours possible d'inverser l'ordre de traitement gauche/droite, selon tes besoins réels ;)