Autor Wątek: Zapisywanie drzewa binarnego do pliku  (Przeczytany 4307 razy)

Offline Demon

  • Użytkownik

# Styczeń 18, 2008, 19:11:43
Tak jak w temacie, czy znacie jakiś dobry sposób na zapisanie drzewa binarnego do pliku ( oczywiście tak żeby dało się je odtworzyć :) ). Najpierw napiszę co mi przychodzi do głowy. Dla każdego poziomu ustalamy ile jest węzłów i dla każdego węzła przeznaczamy 2 bity, ich znaczenie to:

00 - brak lewej i prawej gałęzi
10 - istnieje lewa gałąź
01 - istnieje prawa gałąź
11 - istnieją obie gałęzie

Kończymy kiedy każdy z węzłów danego poziomu ma wartość 00.

Przykład:

        A
       / \
      /   \
     /     \
    B       C
     \     / \
      D   E   F
     /
    G

startujemy od A, ponieważ ma 2 gałęzie więc zapisujemy wartość 11, przechodzimy na następny poziom, B ma 1 gałąź - prawą, więc zapisujemy 01, C ma 2 gałęzie - 11 itd, rezultat:

A  B  C  D  E  F  G
11 01 11 10 00 00 00

Teraz odczyt - odczytujemy pierwsze 2 bity, jest to 11, więc wiemy że mamy 2 węzły na niższym poziomie. Przechodzimy na niższy poziom, wiedząc że mamy teraz odczytać dane dla 2 węzłów, więc odczytujemy 01, 11, mamy więc 3 węzły na niższym poziomie, odczytujemy więc 10, 00, 00. Mamy 1 węzeł na niższym poziomie, więc wczytujemy jego wartość - 00, ponieważ to jedyny węzeł i ma on wartość 00 to kończymy wczytywanie.


Ten pomysł narodził się w mojej głowie i nie mam zielonego pojęcia czy jest dobry, dlatego chciałbym abyście podzielili się własnymi sposobami.
« Ostatnia zmiana: Styczeń 18, 2008, 19:35:03 wysłana przez Demon »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Xion

  • Redaktor
    • xion.log

# Styczeń 18, 2008, 19:41:36
Ja bym zrobił podobnie, tylko dla porządku PREORDER (ty masz LEVELORDER). Najpierw więc zapisujemy bity dla korzenia, następnie rekurencyjnie najpierw reprezentację jego lewego, a potem prawego poddrzewa. Odczyt będzie chyba prostszy: wystarczy użyć stosu, na który odkładamy kolejne wierzchołki i nowe czynić childami tego, który aktualnie jest na szczycie stosu. U ciebie byłoby chyba trochę więcej kombinacji z przypisaniem wierzchołków ich przodkom.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Styczeń 18, 2008, 19:42:23
Cytuj
Ten pomysł narodził się w mojej głowie i nie mam zielonego pojęcia czy jest dobry
Działa? Wygląda na to że tak. A skoro działa, to dobry, ale w tym przypadku zrobił bym tak samo jak Xion.:)

Offline Demon

  • Użytkownik

# Styczeń 18, 2008, 20:00:49
Macie oboje rację, gadałem też z kumplem na GG który mi podsunął ten sam pomysł, trochę ciężko się myśli rekurencyjnie. Ale zauważyłem że w moim sposobie też dałoby się odczytywać w rekurencji. Przynajmniej tak mi się wydaje, ale ciężko stwierdzić który sposób będzie szybszy bez jego implementowania w C++.
« Ostatnia zmiana: Styczeń 18, 2008, 20:05:05 wysłana przez Demon »

Offline ŁukaszB

  • Użytkownik

# Styczeń 18, 2008, 20:19:49
można zapisywać tak...
A( B(D(G,),), C(E(,),F(,)) )
zapis banalny jak widać:), większy problem z odczytem może być :p ale reprezentacja jest jednoznaczna i ma właściwie strukturę drzewa jakby nie patrzeć...:) pozdrawiam
void zapisz( *korzen )
{ if( korzen )
   {   cout << korzen->nazwa << "(";
   }else
   {   return;
   }
   if( korzen->lewy )
   {   zapisz( korzen->lewy );
   }
   cout << ",";
   if( korzen->prawy )
   {   zapisz( korzen->prawy );
   }
   cout << ")";
}
*no teraz:P pisałem z ręki:P
« Ostatnia zmiana: Styczeń 18, 2008, 20:29:56 wysłana przez ŁukaszB »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Styczeń 18, 2008, 20:26:46
Cytuj
Macie oboje rację, gadałem też z kumplem na GG który mi podsunął ten sam pomysł, trochę ciężko się myśli rekurencyjnie. Ale zauważyłem że w moim sposobie też dałoby się odczytywać w rekurencji. Przynajmniej tak mi się wydaje, ale ciężko stwierdzić który sposób będzie szybszy bez jego implementowania w C++.
Zależy od konkretnej implementacji, bo z punktu widzenia złożoności będzie podobnie. Tak czy inaczej, jeżeli w Twoim sposobie na początku byś zapisał liczbę węzłów w całym drzewie, to można je odczytać w sposób bardzo elegancki, prosty i nierekurencyjny. Gorzej z zapisem. :)

Skoro zaczęliśmy rzucać kodem, poniżej jest kod czytający format z pierwszego posta (poprzedzony liczbą węzłów).
vector<Node> nodes;
vector<Node>::iterator r,c;
nodes.resize(liczba_węzłów());

for(r=nodes.begin(),c=r+1;r<nodes.end();r++)
{
    int b = weź_dwa_bity();
    r->left  = (b&1) ? &*c++ : NULL;
    r->right = (b&2) ? &*c++ : NULL;
}


ŁukaszB: Zapomniałeś sprawdzać, czy gdzieś nie ma NULL'a przypadkiem. :)

Offline Demon

  • Użytkownik

# Styczeń 18, 2008, 20:59:28
Krzysiek patrzę się na ten kod i staram zrozumieć, ale obwody mi się palą :D

Mój kod jest znacznie dłuższy, ale chyba czytelniejszy:

Kod: (cpp) [Zaznacz]
enum
{
   no_nodes = 0,
   right_node = 1,
   left_node = 2,
   both_nodes = 3,
};

struct node
{
   char value;
   node* left;
   node* right;
};

unsigned char state;

void SaveRecursive(node* root, FILE* f)
{
   if (root->left)
   {
      state = 0;
      root->left->left ? state |= left_node : 0;
      root->left->right ? state |= right_node : 0;
      fwrite(&state, 1, 1, f);
   }
   if (root->right)
   {
      state = 0;
      root->right->left ? state |= left_node : 0;
      root->right->right ? state |= right_node : 0;
      fwrite(&state, 1, 1, f);
   }
   if (root->left)
      SaveRecursive(root->left, f);
   if (root->right)
      SaveRecursive(root->right, f);
}

void SaveToFile(node& root)
{
   FILE* file;
   file = fopen("binary_tree.btree", "wb");
   state = 0;
   root.left ? state |= left_node : 0;
   root.right ? state |= right_node : 0;
   fwrite(&state, 1, 1, file);
   SaveRecursive(&root, file);
   fclose(file);
}

metoda proponowana przez was:

Kod: (cpp) [Zaznacz]
enum
{
   no_nodes = 0,
   right_node = 1,
   left_node = 2,
   both_nodes = 3,
};

struct node
{
   char value;
   node* left;
   node* right;
};

unsigned char state;

void SaveRecursive(node* root, FILE* f)
{
   state = 0;
   root->left ? state |= left_node : 0;
   root->right ? state |= right_node : 0;
   fwrite(&state, 1, 1, f);
   if (root->left)
      SaveRecursive(root->left, f);
   if (root->right)
      SaveRecursive(root->right, f);
}

void SaveToFile(node& root)
{
   FILE* file;
   file = fopen("binary_tree.btree", "wb");
   SaveRecursive(&root, file);
   fclose(file);
}

Jak dojdę do tego jak go skrócić to zmienię go w tym poście :)

P.S. Dla uproszczenia użyłem bajta zamiast 2 bitów.
« Ostatnia zmiana: Styczeń 18, 2008, 21:39:41 wysłana przez Demon »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Styczeń 18, 2008, 22:02:52
Demon: Twój kod nie robi tego, co niby miał. Drzewo, które podałeś, będzie zapisane w kolejności ABCDGEF.


Cytuj
root->left->left ? state |= left_node : 0;
Sam jestem zwolennikiem używania operatora ?:, ale to jest już chyba przesada. Nie lubisz if'ów, czy jak? :D

Cytuj
Jak dojdę do tego jak go skrócić to zmienię go w tym poście :)
Mogę spróbować? :)

struct node {
    node *left, *right;
};

void SaveRec(node *root,FILE *fp)
{
    if(root) putc(!!root->right+2*!!root->left,fp), SaveRec(root->left,fp), SaveRec(root->right,fp);
}

void SaveToFile(node &root)
{
    FILE *fp = fopen("binary_tree.btree","wb");
    SaveToFile(root,fp);
    fclose(fp);
}
« Ostatnia zmiana: Styczeń 18, 2008, 22:05:10 wysłana przez Krzysiek K. »

Offline Demon

  • Użytkownik

# Styczeń 18, 2008, 22:13:36
Krzysiek o którym kodzie mówisz, tym z mojego pomysłu czy tym który doradzaliście?

//EDIT Ok faktycznie nie działa tak jak powinien, nawet wiem dlaczego, tylko jak to obejść :/

//EDIT2 Chyba się nie da, przynajmniej nie w rekurencji
« Ostatnia zmiana: Styczeń 18, 2008, 22:20:02 wysłana przez Demon »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Styczeń 18, 2008, 22:15:35
Krzysiek o którym kodzie mówisz, tym z mojego pomysłu czy tym który doradzaliście?
O tym z Twojego pomysłu.

Offline Demon

  • Użytkownik

# Styczeń 18, 2008, 22:24:22
Ok widzę że nie ma sensu się przemęczać, po prostu muszę przyjąć wasz sposób i tyle...

//EDIT Krzysiek a co oznacza ten podwójny wykrzyknik w putc?
//EDIT2 Ok już kumam, ale to był trik nie do przebicia :)
« Ostatnia zmiana: Styczeń 18, 2008, 22:46:13 wysłana przez Demon »

Offline ŁukaszB

  • Użytkownik

# Styczeń 18, 2008, 23:55:58
hehe według mnie operator " ? : " zaciemnia kod:P choć sam go nadużywam:D wiem o tym;/...:p sry za ot:)

Offline Silther

  • Użytkownik

# Styczeń 19, 2008, 00:30:54
//EDIT Krzysiek a co oznacza ten podwójny wykrzyknik w putc?
//EDIT2 Ok już kumam, ale to był trik nie do przebicia :)
Mógłby mnie ktoś oświecić, bo mi się nie udało wymyślić do czego służy podwójny wykrzyknik.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Styczeń 19, 2008, 00:32:02
Cytuj
Mógłby mnie ktoś oświecić, bo mi się nie udało wymyślić do czego służy podwójny wykrzyknik.
To pomyśl do czego jest pojedynczy, a potem pomyśl co będzie, jak się użyje go dwa razy. :)

bies

  • Gość
# Styczeń 19, 2008, 00:41:53
Cytuj
root->left->left ? state |= left_node : 0;
Sam jestem zwolennikiem używania operatora ?:, ale to jest już chyba przesada. Nie lubisz if'ów, czy jak? :D
+
    // ...
    if(root) putc(!!root->right+2*!!root->left,fp), SaveRec(root->left,fp), SaveRec(root->right,fp);
    // ...
BUHAHAHAHAHAHAHA! Nie lubisz klamerek czy jak?