Come creare un albero in C++?

Question

Come posso creare una struttura dati ad albero in C++ che utilizzi iteratori anziché puntatori?Non sono riuscito a trovare nulla nell'STL che possa farlo.Quello che mi piacerebbe fare è essere in grado di creare e manipolare alberi come questo:

#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;
}

---

Grazie, tree.hh sembra essere proprio quello che stavo cercando.

Se questo è per ottenere il beneficio di un tipi di indice arbitrario di detenzione della struttura dati, ottimizzato per la ricerca e bravo all'inserimento, considerare l'utilizzo di una mappa.

Una mappa è un contenitore associativo che ha una prestazione garantisce identica a quelle di un albero:Ricerca logaritmica, inserimento logaritmico, eliminazione logaritmica, spazio lineare.Internamente sono spesso implementati come alberi rossi, sebbene non sia una garanzia.Tuttavia, come utente STL, tutto ciò che dovresti preoccuparti sono le garanzie delle prestazioni degli algoritmi e delle struttura dei dati STL.Che siano implementati come alberi o piccoli uomini verdi non dovrebbe avere importanza per te.

Non sono sicuro che una mappa sia ciò di cui ho bisogno, ma grazie per le informazioni.Mi ricorderò di utilizzare le mappe quando possibile invece di implementare gli alberi.

Answer 1

Qui è albero.hh Il che è un po 'vicino a quello che vuoi fare, anche se un po' diverso.

Ecco un pezzo di codice estratto dal suo sito web.

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;
         }
      }
   }

Ora cosa c'è di diverso?L'implementazione è più semplice quando si tratta di aggiungere un nodo all'albero.Sebbene la tua versione sia indiscutibilmente più semplice, lo sviluppatore di questa libreria probabilmente voleva avere alcune informazioni accessibili senza sfogliare l'albero, come ad esempio la dimensione dell'albero.

Presumo anche che non volesse memorizzare la radice su tutti i nodi per motivi di prestazioni.Quindi, se vuoi implementarlo a modo tuo, ti suggerisco di mantenere la maggior parte della logica e aggiungere il collegamento all'albero genitore nell'iteratore e riscrivere un po' l'aggiunta.

Answer 2

Perché vorresti farlo?Se questo è per scopi di apprendimento, puoi scrivere la tua struttura dati ad albero.Se questo serve per ottenere il vantaggio di una struttura dati che contiene tipi di indice arbitrari, ottimizzati per la ricerca e bravi nell'inserimento, prendi in considerazione l'utilizzo di una mappa.

Una mappa è un contenitore associativo che ha garanzie di prestazione identiche a quelle di un albero:ricerca logaritmica, inserimento logaritmico, cancellazione logaritmica, spazio lineare.Internamente sono spesso realizzati come alberi rosso-neri, anche se ciò non è una garanzia.Tuttavia, come utente STL, tutto ciò di cui dovresti preoccuparti sono le garanzie prestazionali degli algoritmi STL e delle strutture dati.Che siano implementati come alberi o piccoli omini verdi non dovrebbe importarti.

Come nota a margine, non esiste una funzione root().Tutti i contenitori STL hanno la funzione Begin() che implementa l'inizio concettuale di un contenitore.Il tipo di iteratore restituito da tale funzione dipende dalle caratteristiche del contenitore.