Hoe om 'n boom in C ++ maak?

Question

Hoe maak ek 'n boom datastruktuur in C ++ wat iterators plaas van wysers gebruik? Ek kon niks in die STL wat dit kan doen. Wat ek wil doen, is om in staat wees om bome soos hierdie te skep en te manipuleer:

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

---

Dankie, tree.hh blyk te wees net wat ek was op soek na.

  

As dit vir die verkryging van die voordeel van   'n data-struktuur hou arbitrêre   indeks tipes, geskik vir soek   en 'n goeie by te voeg dan oorweeg   met behulp van 'n kaart.

     

'n kaart is 'n assosiatiewe houer wat   het prestasie waarborge identies   aan dié van 'n boom: logaritmiese   soek, logaritmiese te voeg,   logaritmiese skrap, lineêre ruimte.   Intern hulle dikwels geïmplementeer   as rooi-swart bome, alhoewel dit is   nie 'n waarborg. Tog, as 'n STL gebruiker   al wat jy moet omgee vir die   prestasie waarborge van die STL   algoritmes en data-strukture.   Of dit nou geïmplementeer as bome   of bietjie groen manne moet nie saak   na jou toe.

Ek is nie seker of 'n kaart is wat ek nodig het, maar dankie vir die info. Ek sal onthou om kaarte te gebruik, waar moontlik, in plaas van die implementering van bome.

Answer 1

Hier is tree.hh wat is 'n bietjie naby aan wat jy wil hê om te doen, maar 'n bietjie verskillende.

Hier is 'n stukkie van die kode uit sy webwerf.

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

Nou wat anders? Jou implementering is eenvoudiger as dit kom by voeg 'n knoop aan die boom. Hoewel jou weergawe is indiscutably eenvoudiger, die dev van hierdie lib waarskynlik wou 'n paar inligting toeganklik sonder die boom, op soos die grootte van die boom byvoorbeeld het.

Ek neem aan ook hy wou nie die wortel te slaan op alle nodes vir prestasie rede. So as jy wil om dit te implementeer jou pad, ek stel voor jy die meeste van die logika hou en voeg die skakel na die ouer boom in die iterator en herskryf voeg 'n bietjie.

Answer 2

Waarom sou jy wil om dit te doen? As dit vir leerdoeleindes dan kan jy jou eie boom datastruktuur skryf. As dit vir die verkryging van die voordeel van 'n data-struktuur hou arbitrêre tipes indeks, geskik vir die soek en goed in te voeg dan oorweeg om 'n kaart.

'n kaart is 'n assosiatiewe houer wat prestasie waarborge identies aan dié van 'n boom het: logaritmiese soek, logaritmiese te voeg, logaritmiese skrap, lineêre ruimte. Intern hulle dikwels geïmplementeer as rooi-swart bome, alhoewel dit is nie 'n waarborg. Tog, as 'n STL gebruiker al wat jy moet omgee is die prestasie waarborge van die STL algoritmes en data-strukture. Of dit nou geïmplementeer as bome of bietjie groen manne moet nie belangrik vir jou.

As 'n kant nota, daar is nie so iets soos 'n wortel () funksie. Alle STL houers hê die funksie begin () die implementering van die konseptuele begin van 'n houer. Die soort iterator teruggekeer deur daardie funksie is afhanklik van die eienskappe van die houer.