Comment faire un arbre en C++ ?

Question

Comment créer une structure de données arborescente en C++ qui utilise des itérateurs au lieu de pointeurs ?Je n'ai rien trouvé dans la STL qui puisse faire cela.Ce que j'aimerais faire, c'est pouvoir créer et manipuler des arbres comme ceci :

#include <iostream>
#include <tree>
using namespace std;

int main()
{
    tree<int> myTree;

    tree<int>::iterator i = myTree.root();
    *i = 42;

    tree<int>::iterator j = i.add_child();
    *j = 777;
    j = j.parent();

    if (i == myTree.root() && i == j) cout << "i and j are both pointing to the root\n";

    return 0;
}

---

Merci, tree.hh semble être exactement ce que je cherchais.

S'il s'agit de bénéficier d'un bénéfice d'une structure de données détenant des types d'index arbitraires, optimisé pour la recherche et bon à l'insertion, envisagez d'utiliser une carte.

Une carte est un conteneur associatif qui a des garanties de performance identiques à celles d'un arbre:Recherche logarithmique, insertion logarithmique, délétion logarithmique, espace linéaire.En interne, ils sont souvent mis en œuvre comme des arbres rouge-noir, bien que ce ne soit pas une garantie.Pourtant, en tant qu'utilisateur STL, tout ce qui vous convient, ce sont les garanties de performances des algorithmes STL et des structures de données.Qu'ils soient mis en œuvre en tant qu'arbres ou de petits hommes verts ne vous importent pas.

Je ne sais pas si j'ai besoin d'une carte, mais merci pour l'information.Je me souviendrai d'utiliser des cartes autant que possible au lieu d'implémenter des arbres.

Answer 1

Voici arbre.hh Ce qui est un peu proche de ce que vous voulez faire, bien qu'un peu différent.

Voici un morceau de code extrait de son site Internet.

int main(int, char **)
   {
   tree<string> tr;
   tree<string>::iterator top, one, two, loc, banana;

   top=tr.begin();
   one=tr.insert(top, "one");
   two=tr.append_child(one, "two");
   tr.append_child(two, "apple");
   banana=tr.append_child(two, "banana");
   tr.append_child(banana,"cherry");
   tr.append_child(two, "peach");
   tr.append_child(one,"three");

   loc=find(tr.begin(), tr.end(), "two");
   if(loc!=tr.end()) {
      tree<string>::sibling_iterator sib=tr.begin(loc);
      while(sib!=tr.end(loc)) {
         cout << (*sib) << endl;
         ++sib;
         }
      cout << endl;
      tree<string>::iterator sib2=tr.begin(loc);
      tree<string>::iterator end2=tr.end(loc);
      while(sib2!=end2) {
         for(int i=0; i<tr.depth(sib2)-2; ++i) 
            cout << " ";
         cout << (*sib2) << endl;
         ++sib2;
         }
      }
   }

Maintenant, qu'est-ce qui est différent ?Votre implémentation est plus simple lorsqu'il s'agit d'ajouter un nœud à l'arborescence.Bien que votre version soit incontestablement plus simple, le développeur de cette lib a probablement voulu avoir certaines informations accessibles sans parcourir l'arborescence, comme la taille de l'arborescence par exemple.

Je suppose également qu'il ne voulait pas stocker la racine sur tous les nœuds pour des raisons de performances.Donc, si vous souhaitez l'implémenter à votre manière, je vous suggère de conserver l'essentiel de la logique et d'ajouter le lien vers l'arborescence parent dans l'itérateur et de réécrire un peu l'ajout.

Answer 2

Pourquoi voudriez-vous faire ça ?Si c'est à des fins d'apprentissage, vous pouvez écrire votre propre structure de données arborescente.Si cela permet de bénéficier d'une structure de données contenant des types d'index arbitraires, optimisée pour la recherche et bonne pour l'insertion, envisagez d'utiliser une carte.

Une carte est un conteneur associatif qui présente des garanties de performances identiques à celles d'une arborescence :recherche logarithmique, insertion logarithmique, suppression logarithmique, espace linéaire.En interne, ils sont souvent mis en œuvre sous forme d’arbres rouge-noir, bien que cela ne soit pas une garantie.Néanmoins, en tant qu'utilisateur STL, tout ce dont vous devez vous soucier, ce sont les garanties de performances des algorithmes et des structures de données STL.Qu'ils soient mis en œuvre sous forme d'arbres ou de petits hommes verts ne devrait pas vous intéresser.

En remarque, il n’existe pas de fonction root().Tous les conteneurs STL ont la fonction Begin() implémentant le début conceptuel d'un conteneur.Le type d'itérateur renvoyé par cette fonction dépend des caractéristiques du conteneur.