Ĺadny brzuch
Mógłby mi ktoś przedstawić porzadna metode implementacji drzewa binarnego wraz z sposobem wczytywania do nieog wezlow? Bo na necie (o dziwo) praktycznie wogole tego nie ma... A jak juz cos jest to ogranicza sie to do kodu:
struct Node { char Dane; Node * Left; Node * Right; };
A poniewaz ja jeszcze z drzewami nie mialem do czynienia (a najzwyzszy czas miec), to sprobowalem dopisac do tego odpowiedni kod, ale nie jestem pewien czy to aby na pewno tak ma byc. Jesli nie, to powiedzcie mi jak to wzorcowo powinno wygladac:
#include<iostream> #include<cstdio> #include<vector> using namespace std; struct Node { char Dane; Node * Left; Node * Right; }; vector<Node> drzewko; int find(int a) { for(int i=0; i<drzewko.size(); i++) if(drzewko[i].Dane == a) return i; return -1; } main() { int n, dane, pos, rodzic; //liczba wezlow, dane w wezle, pozycja(0 - lewy, 1 - prawy), rodzic Node wezel={1, NULL, NULL}; drzewko.push_back(wezel); scanf("%d", &n); n--; while(n--) { scanf("%d %d %d", &rodzic , &pos, &dane); Node wez={dane, NULL, NULL}; Node *wsk=&wez; if(pos==0) drzewko[find(rodzic)].Left=wsk; else drzewko[find(rodzic)].Right=wsk; } system("pause"); return 0; }
Tak, zaimplementowałeś poprawnie. Ale to w sumie ogólny sposób implementacji, nie tylko dla binarnych (możesz przecież zamiast dwóch zmiennych wskaźnikowych Left, Right dać tam tablicę/listę wskaźników i zrobić z tego dowolne drzewo).
Dla binarnych drzewek istnieje jeszcze taki ciekawy myk, dzięki któremu możesz:
1) ustalić w czasie stałym czy dany wierzchołek jest lewy, czy prawy
2) ustalić w czasie stałym synów wierzchołka
3) ustalić w czasie stałym kto jest ojcem wierzchołka
4) oszczędzić pamięć, pod warunkiem że drzewo jest w miarę pełne
a ogranicza się on do tego, że dla drzewa o wysokości h tworzymy tablicę T długości 2h+1-1 (zakładamy że jest indeksowana od 1) przy czym
1) w T[1] trzymamy dane dla korzenia
2) w T[2n] trzymamy dane dla lewego syna n-tego wierzchołka
3) w T[2n+1] trzymamy dane dla prawego syna n-tego wierzchołka
:D
Użytkownik bryn edytował ten post 15 marzec 2008, 13:20
twoje rozwiązanie raczej nie bedzie dzialalo bo:
przy kolejnej iteracji petli while wez zostanie skasowane ? (zmiena lokalna), np ustawiony Left będzie pokazywac na jakis obszar pamieci w ktorej nikt nie wie co bedzie.
ale moge sie mylic, natomiast na pewno zadziała cos takiego:
Node* wsk = new Node; (*wsk).dane = dane; (*wsk).Left = NULL; (*wsk).Right = NULL; // radzil bym konstruktor napisac bo to zawsze wygodniej Node* wsk = new Node(dane, NULL, NULL);
teraz wektor ...
nie wiem za bardzo jak to chciales napisac ale jezeli chciales wszystkie galezie dopisywac do vectora to raczej trzeba by to zrobic jakos tak:
Node wez = {1, NULL, NULL}; drzewko.push_back(wez); // tu nie wiem do konca jak to zrobic Node* wez = &(drzewko[v.size()-1]);
tu moze byc problem bo wektor jezeli skoczy sie mu pamiec jest reallocowany i wtedy mogą zmienic sie adresy jego komorek? prosze o poprawienie mnie jesli sie myle.
Jezeli wiesz ze zawsze bedzie tylko 100 galezi to mozesz zaalokowac sobie poprostu 100 komorek w vektorze i powinno dzialac.
Jednak bardziej intuicyjnym rozwiazaniem tutaj jest kolejka zamiast vectora jezeli wogole juz chcesz w jakiejs struktorze to trzymac... bo przeciez mozna w samym drzewie:
Node* dodajLeft(Node* wsk, char dane){ (*wsk).Left = new Node(dane); return((*wsk).Left); } main{ Node* root = new Node; Node* wsk = root; while(cin >> dane) // taki pseudokod wsk = dodajLeft(wsk, dane); }
Użytkownik Pinochet edytował ten post 15 marzec 2008, 13:49
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
struct Node { char Dane; Node * Left; Node * Right; };
A poniewaz ja jeszcze z drzewami nie mialem do czynienia (a najzwyzszy czas miec), to sprobowalem dopisac do tego odpowiedni kod, ale nie jestem pewien czy to aby na pewno tak ma byc. Jesli nie, to powiedzcie mi jak to wzorcowo powinno wygladac:
#include<iostream> #include<cstdio> #include<vector> using namespace std; struct Node { char Dane; Node * Left; Node * Right; }; vector<Node> drzewko; int find(int a) { for(int i=0; i<drzewko.size(); i++) if(drzewko[i].Dane == a) return i; return -1; } main() { int n, dane, pos, rodzic; //liczba wezlow, dane w wezle, pozycja(0 - lewy, 1 - prawy), rodzic Node wezel={1, NULL, NULL}; drzewko.push_back(wezel); scanf("%d", &n); n--; while(n--) { scanf("%d %d %d", &rodzic , &pos, &dane); Node wez={dane, NULL, NULL}; Node *wsk=&wez; if(pos==0) drzewko[find(rodzic)].Left=wsk; else drzewko[find(rodzic)].Right=wsk; } system("pause"); return 0; }
Tak, zaimplementowałeś poprawnie. Ale to w sumie ogólny sposób implementacji, nie tylko dla binarnych (możesz przecież zamiast dwóch zmiennych wskaźnikowych Left, Right dać tam tablicę/listę wskaźników i zrobić z tego dowolne drzewo).
Dla binarnych drzewek istnieje jeszcze taki ciekawy myk, dzięki któremu możesz:
1) ustalić w czasie stałym czy dany wierzchołek jest lewy, czy prawy
2) ustalić w czasie stałym synów wierzchołka
3) ustalić w czasie stałym kto jest ojcem wierzchołka
4) oszczędzić pamięć, pod warunkiem że drzewo jest w miarę pełne
a ogranicza się on do tego, że dla drzewa o wysokości h tworzymy tablicę T długości 2h+1-1 (zakładamy że jest indeksowana od 1) przy czym
1) w T[1] trzymamy dane dla korzenia
2) w T[2n] trzymamy dane dla lewego syna n-tego wierzchołka
3) w T[2n+1] trzymamy dane dla prawego syna n-tego wierzchołka
:D
Użytkownik bryn edytował ten post 15 marzec 2008, 13:20
twoje rozwiązanie raczej nie bedzie dzialalo bo:
przy kolejnej iteracji petli while wez zostanie skasowane ? (zmiena lokalna), np ustawiony Left będzie pokazywac na jakis obszar pamieci w ktorej nikt nie wie co bedzie.
ale moge sie mylic, natomiast na pewno zadziała cos takiego:
Node* wsk = new Node; (*wsk).dane = dane; (*wsk).Left = NULL; (*wsk).Right = NULL; // radzil bym konstruktor napisac bo to zawsze wygodniej Node* wsk = new Node(dane, NULL, NULL);
teraz wektor ...
nie wiem za bardzo jak to chciales napisac ale jezeli chciales wszystkie galezie dopisywac do vectora to raczej trzeba by to zrobic jakos tak:
Node wez = {1, NULL, NULL}; drzewko.push_back(wez); // tu nie wiem do konca jak to zrobic Node* wez = &(drzewko[v.size()-1]);
tu moze byc problem bo wektor jezeli skoczy sie mu pamiec jest reallocowany i wtedy mogą zmienic sie adresy jego komorek? prosze o poprawienie mnie jesli sie myle.
Jezeli wiesz ze zawsze bedzie tylko 100 galezi to mozesz zaalokowac sobie poprostu 100 komorek w vektorze i powinno dzialac.
Jednak bardziej intuicyjnym rozwiazaniem tutaj jest kolejka zamiast vectora jezeli wogole juz chcesz w jakiejs struktorze to trzymac... bo przeciez mozna w samym drzewie:
Node* dodajLeft(Node* wsk, char dane){ (*wsk).Left = new Node(dane); return((*wsk).Left); } main{ Node* root = new Node; Node* wsk = root; while(cin >> dane) // taki pseudokod wsk = dodajLeft(wsk, dane); }
Użytkownik Pinochet edytował ten post 15 marzec 2008, 13:49