Witam,
Mam za zadanie stworzenie programu który wczytywał by z pliku dane oraz
na ich podstawie tworzył drzewo.
Z implementacją drzewa jakoś sobie poradzę ale nie mam pomysłu na format pliku.
Tzn jak w pliku tekstowym najoptymalniej zawrzeć całe drzewo.
Czy robił ktoś coś takiego?Mógłby mi ktoś podsunąć jakieś pomysły?
_13th_Dragon napisał(a):
Rekurencyjne preorder:
węzeł
lewo
prawo
Chyba że nie jest to drzewo binarne ...
Przepraszam zapomniałem dodać że jest to drzewo binarne.
Czy ten rekurencyjny sposób powinien zacząć działanie od korzenia?
Nadal nie do końca się domyślam jak to powinno być wpisywane w pliku ,czym separowane etc.
Program to quiz gdzie użytkownik odp na kolejne pytania (liście to odp)
moja struktura ma format
struct node
{
node *top,*left, *right
int key
string content
};
Będę wdzięczny za kolejne podpowiedzi ! :)
Tak od korzenia, później lecisz po drzewie według kolejności preorder. Co do "separowania" możesz zrobić to tak że albo do każdego noda dopiszesz sobie flage informującą czy posiada lewą/prawą gałąź lub zapisać pustego noda jako znacznik końca, są różne metody, którą wybrać zależy od ciebie i od tego jaki "kształt" najczęściej przyjmuje drzewo(czy jest zrównoważone, itd).
Jeśli drzewo jest zrównoważone to możesz również użyć kopca binarnego (kolejność BFS).
Dla dowolnego drzewa binarnego:
Zapis (w kolejności pre-order)
parametry Funkcji:
Wczytywanie
parametry Funkcji:
Tylko czym tak na prawdę jest to drzewo? Może strukturę da się odtworzyć na podstawie zawartości węzłów? Wtedy zapisujesz po prostu same węzły w dowolnej kolejności...
możesz zrobić plik w stylu:
0 - 5 ...
1 L 3 ...
2 L 2 ...
2 P 4 ...
1 P 7 ...
2 P 9 ...
3 L 8 ...
pierwsza kolumna to głębokość, druga oznacza czy dziecko jest lewy czy prawym potomkiem, trzecia to key, 4 (...) to jakiś content.
wczytywanie z pliku wygląda tak:
(glebokosc, lewyprawy, key, content) <- wczytaj pierwsza linijke
node <- utworz wezel (key, content)
node.top <- none
wrzuc node na pusty stos
wykonuj do konca pliku:
(glebokosc, lewyprawy, key, content) <- wczytaj linijke
node <- utworz wezel (key, content)
dopóki ilosc elementow na stosie >= glebokosc:
parent <- zdejmij element ze stosu
parent.lewyprawy <- node
node.top <- parent
wrzuc parent na stos
wrzuc node na stos
#include <iostream>
#include <iomanip>
#include <fstream>
#include <ctime>
using namespace std;
struct TreeNode
{
TreeNode *left,*right;
double data;
TreeNode(double data,TreeNode *left=0,TreeNode *right=0):left(left),right(left),data(data) {}
TreeNode(ifstream &f):left(0),right(0) { f>>data; }
};
struct Tree
{
TreeNode *root;
TreeNode():root(0) {}
};
void recwrite(ofstream &f,TreeNode *node)
{
if(node)
{
f<<'1'<<' '<<node->data<<endl;
recwrite(f,node->left);
recwrite(f,node->right);
}
else f<<'0'<<endl;
}
TreeNode *recread(ifstream &f)
{
char x;
f>>x;
if(x=='1')
{
TreeNode *node=new TreeNode(f);
node->left=recread(f);
node->right=recread(f);
return node;
}
else return 0;
}
void show(TreeNode *node,unsigned p=1)
{
if(node)
{
show(node->left,p+1);
cout<<setw(p)<<"-"<<' '<<node->data<<endl;
show(node->right,p+1);
}
}
TreeNode *add(Tree &T,double data)
{
bool v=false;
TreeNode *parent=0,*node=T.root;
while(node)
{
parent=node;
v=(data<node->data);
node=v?node->left:node->right;
}
return (parent?(v?parent->left:parent->right):T.root)=new TreeNode(data);
}
int main()
{
srand(time(0));
while(true)
{
Tree T;
for(unsigned i=0;i<10;++i) add(T,10+90.*rand()/(RAND_MAX+1));
show(T.root);
ofstream ofs("drzewo.txt");
recwrite(ofs,T.root);
ofs.close();
cout<<"---------"<<endl;
Tree Q;
ifstream ifs("drzewo.txt");
Q.root=recread(ifs);
ifs.close();
show(Q.root);
cout<<"========="<<endl;
cin.sync();
cin.get();
}
return 0;
}
dziękuje bardzo wszystkim za odpowiedzi ! :) niestety dopiero dzisiaj będę mógł przysiąść i z nich skorzystać :) postaram się przedstawić to co stworzę pod wasz krytyczny osąd- (lepiej żeby mnie ktoś doświadczony naprostował gdy dopiero sie uczę niż mam po latach pozbywać się złych nawyków )