drzewo w C++

Witam!
Chcę napisać program, który by czytał z pliku drzewo katalogów i zapisywał je w pamięci RAM. Proszę o pomoc ze stworzeniem przykładowego drzewa (może - choć niekoniecznie - z wykorzystaniem STL? znalazłem np. podwójną listę połączoną w STL, ale drzew niestety nie ma w STL), które zapisywałoby poniższe drzewo katalogów, a później je wyświetlało. Dalej sobie samemu poradzę z czytaniem z pliku.

main
---dir1
------subdir1
---------subdir4
---------subdir5
------subdir2
---dir2
------subdir3
---dir3

a na dobry początek przynajmniej takie drzewo
main
---dir1
---dir2

Z góry dzięki!
Pozdrawiam.

Najprostsze drzewo to jedna klasa, przechowująca nazwę katalogu, listę wskaźników na tą klasę (katalogi podrzędne) i ew. wskaźnik na katalog nadrzędny, jeśli będzie ci potrzebny. A rekurencyjne wypisanie takiego drzewa to już banał. :P

Hmm... Czy mógłbym Cię prosić o napisanie przynajmniej części tego kodu tak, żebym wiedział, jak go zacząć tworzyć? Na razie próbuję z tym http://www.gamedev.net/reference/articles/article2192.asp coś zrobić (http://cboard.cprogramming.com/showthread.php?p=801229#post801229), ale jak mi nie wyjdzie, to chętnie skorzystam z Twojego pomysłu (a nawet, jak mi wyjdzie, to i tak spróbuję później stworzyć to samemu od początku, bez korzystania z zewnętrznych plików .h, za to wykorzystując pomysł z klasą i wskaźnikami na nią - ale jak zacząć?). Pozdrawiam!

Kod pisany z palca:

Idea drzewa ( indeksy dzieci ):

parent - 0
child - 0
child - 1
child - 2
parent - 1
parent - 2
child - 0
child - 0
child - 1
..

class Node
{
public:
  Node( Node *aParent = 0 );
  ~Node();
  inline Node* parent() const { return pParent; }
  inline list<Node*> children() const { return pChildren; }
  void appendChild( Node *aChild );
  int childIndex( Node *aChild ); // to ma zwrocic index dziecka, -1 jak nie ma
  Node* child( const int &aIndex ); // zwraca dziecko lub NULL jak zly index
private:
  Node *pParent;
  list<Node*> pChildren;
};

Node::Node( Node *aParent ) : pParent ( aParent )
{
   
}

Node::~Node()
{
  //mozna tez na iteratorach, albo zwykle for
   while ( !pChildren.empty() )
   {
      delete pChildren.front();
      pChildren.pop_front();
    }
}

void Node::appendChild( Node *aChild )
{
  // mozna dodac sprawdzanie czy nie dodajesz samego siebie, albo dziecka ktore juz istnieje
  if ( aChild->parent() )
    return;
  pChildren.push_back( aChild );
}

//Budujemy drzewo - tu proponuje zrobic klase zawierajaca cale potrzebne API
//mozna zrobic tez tak ze przy dodawaniu sie bedzie samo reparentowalo  

Node *root = new Node;
root->appendChild( new Node );
root->appendChild( new Node );
Node *node = root->child( 0 );
root->child( 0 )->appendChild( new Node( node ) );

IMVHO do prostej struktury katalogów nie potrzebujesz nic tak rozbudowanego.

Kod drzewa ogranicza się do jednej struktury z dwiema zmiennymi, kod konstrukcji i wyświetlenia można załatwić rekurencją. Pewnie dałoby się optymalniej, ale to sobie poszukasz. :P

W wersji "nie obchodzą mnie wycieki pamięci" mogłoby to wyglądać tak:

Struktura reprezentująca katalog - katalog, obvously, ma nazwę i podkatalogi (a konstruktor dla skrócenia kodu):

struct Directory {
 std::string name;
 std::vector<Directory*> children;

 Directory(std::string name_) : name(name_) { };
};

Najprostsza rekurencyjna funkcja wypisująca drzewo (std::for_each to nagłówek algorithm):

void print(Directory *dir) {
 std::cout << dir->name << " : " << std::endl;
 std::for_each(dir->children.begin(), dir->children.end(), print);
}

Albo z ładniejszym formatowaniem (na szybko pisane, nie czepiać się :P):

int nesting = 0;

void print(Directory *dir) {
 for (int i = 0; i < nesting; ++i) std::cout << ' ';
 std::cout << dir->name << " => (" << std::endl;
 ++nesting;
 std::for_each(dir->children.begin(), dir->children.end(), print);
 --nesting;
 for (int i = 0; i < nesting; ++i) std::cout << ' ';
 std::cout << ")" << std::endl;
}

I przykładowe drzewo:

int main(void) {
 /*
  - root
   - sub1
    - sub1.1
   - sub2
   - sub3
    - sub3.1
     - sub3.1.1
  */
 Directory *root   = new Directory("root");
 Directory *sub1   = new Directory("sub1");
 Directory *sub11  = new Directory("sub1.1");
 Directory *sub2   = new Directory("sub2");
 Directory *sub3   = new Directory("sub3");
 Directory *sub31  = new Directory("sub3.1");
 Directory *sub311 = new Directory("sub3.1.1");
 
 root->children.push_back(sub1);
 sub1->children.push_back(sub11);
 root->children.push_back(sub2);
 root->children.push_back(sub3);
 sub3->children.push_back(sub31);
 sub31->children.push_back(sub311);
 
 print(root);
 return 0;
}

Dzięki Wam obu za odpowiedź :).
PiotrLegnica, Twoje rozwiązanie wydaje mi się łatwiejsze do zrozumienia z moją wiedzą na temat C++ (czyli pewna znajomość języka jest, ale nie jest ona wielka :)). Parę rzeczy mnie zastanawia - np. 1) ta linijka

for (int i = 0; i < nesting; ++i) std::cout << ' ';

jeśli nesting=0 to tak naprawdę nie ma pętli, dobrze rozumiem, że ma ona znaczenie dopiero później?
2)

std::vector<Directory*> children;

czyli tak naprawdę do każdej gałęzi tworzony jest wektor, ale tylko dla niektórych jest on niezerowy?
3) skąd ta linijka

std::for_each(dir->children.begin(), dir->children.end(), print);

wywołuje print. To przecież nie jest print(), które by przyjmowało parametr Directory *dir
4) na czym polegają w tym wypadku "wycieki pamięci" i jak im zapobiec :D.
dzięki i pozdrawiam :)!

Ad.1.
I o to chodzi. Ta pętla jest tylko po to, żeby output miał odpowiednie wcięcia, np.

root => (
 sub1 => (
  sub1.1 => (
  )
 )
 sub2 => (
 )
 sub3 => (
  sub3.1 => (
   sub3.1.1 => (
   )
  )
 )
)

Ad.2.
Ta. Można by kombinować inaczej, ale po co.

Ad.3.
for_each dla każdego elementu pomiędzy dwoma iteratorami wywołuje podaną funkcję. A jako, że elementy są typu Directory*, to funkcja jest print(Directory*).
Pętla ta zapisana ręcznie wyglądałaby pewnie tak (pisane z pamięci):

for (
 std::vector<Directory*>::const_iterator it = dir->children.begin();
 it != dir->children.end();
 ++it
) {
 print(*it);
}

Ad.4.
Dopisać porządne zarządzanie pamięcią. :P

Dzięki raz jeszcze :)

Otrzymałem taką sugestię, żeby to

Directory *root   = new Directory("root");

zamienić na to

Directory root("root");

i wtedy nie będzie żadnych wycieków pamięci (osoba ta nie widziała żadnego powodu, żeby używać wskaźników lub dynamicznej alokacji pamięci). Rzecz jasna wtedy trzeba też będzie zrobić to samo z resztą zmiennych mojego Directory, czyli zmienić dzieci (czyli w którym miejscu miałbym to zmienić????) na std::vector<Directory> zamiast wskaźników. Wtedy też trzeba używać kropki zamiast -> w każdym miejscu.

Po wprowadzeniu takich zmian nie będę używać dynamicznej pamięci, nie będzie trzeba zwalniać pamięci po jej zaalokowaniu z użyciem new. To oznacza brak wycieków pamięci.

Czyżby więc Twój kod (po wprowadzeniu takiej prostej zmiany) był idealnym zastosowaniem do przechowywania struktury katalogów w formie drzewa :)?

Jak rozumiem funkcja print w dalszym ciągu działa tak samo - czy mam rację? Myślę, że taka zmiana powinna wyjść tylko na dobre:

void print(const Directory *dir) {

nie jestem jednak całkiem pewien, czy dobrze wstawiłem const (chcę, żeby funkcja print pobierała referencję do const tak, żebym nie kopiował roota, kiedy go pobieram).

Pozdrawiam :)!

Może być i stos, jeśli dasz radę zagwarantować, że elementy nie będą nigdzie kopiowane. Mi się nie chciało w to bawić, dlatego sterta i wskaźniki.

Dzięki, teraz mam takie dwa pytanka:

1. jak mogę stworzyć konstruktor kopiujący (i czy rzeczywiście go potrzebuję? - linia print(root); nie mogła być skompilowana, więc pomyślałem, że może to być spowodowane przez brak konstruktora kopiującego).
2. czy dobrze użyłem 'const'?

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

class Directory
{
 public:
    string name;
    vector<Directory> children; //I erased * in this line

    Directory(string name_) : name(name_) { };
    Directory(Directory *dir)
    {
       //First question:
       //I guess I should create here copying constructor
       //but I don't know how to do it
    }
};

int nesting = 0;

//void print(Directory *dir) {
                                   //Second question:
void print(const Directory *dir) { //do i use the word 'const' properly?
 for (int i = 0; i < nesting; ++i) cout << ' ';
 cout << dir->name << endl;
 ++nesting;
 for_each(dir->children.begin(), dir->children.end(), print);
 --nesting;
 //for (int i = 0; i < nesting; ++i) cout << ' ';
 //cout << endl;
}

int main(void) {
 /*
  - root
   - sub1
    - sub1.1
   - sub2
   - sub3
    - sub3.1
     - sub3.1.1
  */
 Directory root("root");
 Directory sub1("sub1");
 Directory sub11("sub1.1");
 Directory sub2("sub2");
 Directory sub3("sub3");
 Directory sub31("sub31");
 Directory sub311("sub311");
/*
 Directory *root   = new Directory("root");
 Directory *sub1   = new Directory("sub1");
 Directory *sub11  = new Directory("sub1.1");
 Directory *sub2   = new Directory("sub2");
 Directory *sub3   = new Directory("sub3");
 Directory *sub31  = new Directory("sub3.1");
 Directory *sub311 = new Directory("sub3.1.1");
*/ 
 root.children.push_back(sub1);
 sub1.children.push_back(sub11);
 root.children.push_back(sub2);
 root.children.push_back(sub3);
 sub3.children.push_back(sub31);
 sub31.children.push_back(sub311);
 
 print(root);
 system("pause");
 return 0;
}

Jeżeli chcesz użyć takiego rozwiązania :

 root.children.push_back(sub1);
 sub1.children.push_back(sub11);
 root.children.push_back(sub2);
 root.children.push_back(sub3);
 sub3.children.push_back(sub31);
 sub31.children.push_back(sub311);
 
 print(&root); // tu powinien być adres !
 system("pause");
 return 0;
}

to niezbędne jest użycie :

vector<Directory*> children;

ponieważ przy użyciu :

vector<Directory> children;

Tworzony obiekt wektora children jest kopią podanego obiektu w argumencie metody push_back .
A więc, użycie :

print(&root);

spowoduje wyświetlenie :
root
sub1
sub2
sub3
ze względu na to, że instrukcja :

sub1.children.push_back(sub11);

ma się nijak do sub1, który jest dzieckiem root'a (bo dziecko sub1 root'a jest kopią lokalnego obiektu sub1 w funkcji main !). Wygląda na to, że nawet nie przetestowałeś swojego kodu zanim zapostowałeś na 4um...
Jeśli jednak chcesz użyć konstrukcji z :

vector<Directory> children;

to musisz dodawać dzieci w następujący sposób :

root.children.push_back(sub1);
root.children.at(0).children.push_back(sub11);
// itd..

Jeśli chodzi o konstruktor kopiujący, to powinien wyglądać mniej więcej tak :

Directory(Directory *dir) {
    Directory(dir->name);
    children = vector<Directory>(dir->children);
}

musisz oczywiście pamiętać o destruktorze..