drzewo binarne C

ktosja
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 28 kwie 2011, o 10:21
Płeć: Kobieta
Lokalizacja: gdzies

drzewo binarne C

Post autor: ktosja »

Muszę napisać program który policzy ile jest liści w drzewie na jakimś poziomie. Problem zaczyna się już na wstępie bo nie rozumiem w jaki sposób stworzyć drzewo binarne, gdzie w lisciach będą kolejne znaki z tablicy. szukałam dużo w internecie jednak bez skutków, większość przykładów były w innych językach.
Wiem jedynie tyle że drzewo na strukturę:

Kod: Zaznacz cały

struct drzewo {
        struct drzewo *lewy_syn;
        struct drzewo *prawy_syn;
        char *dane;
};
Proszę o jakąś pomoc czy wskazówki
PMichalak
Użytkownik
Użytkownik
Posty: 125
Rejestracja: 29 paź 2009, o 20:03
Płeć: Mężczyzna
Lokalizacja: Kalisz
Podziękował: 1 raz
Pomógł: 16 razy

drzewo binarne C

Post autor: PMichalak »

Możesz użyć do tego celu przeszukiwania wszerz (BFS).
ktosja
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 28 kwie 2011, o 10:21
Płeć: Kobieta
Lokalizacja: gdzies

drzewo binarne C

Post autor: ktosja »

niestety nic z tego nie rozumiem, naprawę jestem zielona,
a mógłbyś mi podać przykład w jaki sposób stworzyć 1 węzeł i przypisać do niego 2 wartości.
bardzo prosze
Awatar użytkownika
mcbob
Użytkownik
Użytkownik
Posty: 479
Rejestracja: 15 gru 2008, o 19:02
Płeć: Mężczyzna
Lokalizacja: Poland
Pomógł: 69 razy

drzewo binarne C

Post autor: mcbob »

Taki przykład na szybko, mam nadzieję że trochę rozjaśni.

Kod: Zaznacz cały

#include <stdio.h>
#include <stdlib.h>

struct drzewo{
        struct drzewo *lewy_syn;
        struct drzewo *prawy_syn;
        char *dane;
};


int main(int argv, char *args[]) {
	
	struct drzewo *korzen;
	
	korzen = (struct drzewo*)malloc(sizeof(struct drzewo));
	korzen->prawy_syn = (struct drzewo*)malloc(sizeof(struct drzewo));
	korzen->lewy_syn = (struct drzewo*)malloc(sizeof(struct drzewo));
	
	korzen->dane = "korzen";
	korzen->prawy_syn->dane = "prawy syn";
	korzen->lewy_syn->dane = "lewy syn";
	
	printf("%s
",korzen->dane);
	printf("%s
",korzen->prawy_syn->dane);
	printf("%s
",korzen->lewy_syn->dane);
	
	free(korzen->prawy_syn);
	free(korzen->lewy_syn);
	free(korzen);

	return 0;
}
Jeszcze dodam że przeszukiwanie takiego drzewa sprowadza się do prostych funkcji rekurencyjnych. Tzn.
ilość liści w drzewie = ilość liści w prawym poddrzewie + ilość liści w lewym poddrzewie
Żeby policzyć liście na danym poziomie wystarczy zadbać o odpowiednią głębokość rekurencji.
Ostatnio zmieniony 15 maja 2011, o 14:33 przez mcbob, łącznie zmieniany 1 raz.
void_t
Użytkownik
Użytkownik
Posty: 103
Rejestracja: 14 maja 2011, o 18:25
Płeć: Mężczyzna
Pomógł: 26 razy

drzewo binarne C

Post autor: void_t »

Kod: Zaznacz cały

malloc(sizeof(char)*20);
i
ktosja pisze:gdzie w lisciach będą kolejne znaki z tablicy
Niepotrzebnie w takim razie marnujesz pamięć

A ponadto mamy tutaj wyciek pamięci - konkretnie 60 bajtów, dlatego do operacji na listach, drzewach warto napisać sobie kilka przydatnych funkcji służących alokacji i zwalnianiu obiektów takiej struktury.
Awatar użytkownika
mcbob
Użytkownik
Użytkownik
Posty: 479
Rejestracja: 15 gru 2008, o 19:02
Płeć: Mężczyzna
Lokalizacja: Poland
Pomógł: 69 razy

drzewo binarne C

Post autor: mcbob »

Pisałem jedną wersję potem zmieniłem koncepcję i nie skasowałem niepotrzebnego kodu, stąd ten błąd. Teraz jest dobrze. Wiem że ma być jeden znak w zadaniu ale ja nie rozwiązuję tego zadania tylko podaję prosty przykład.
ktosja
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 28 kwie 2011, o 10:21
Płeć: Kobieta
Lokalizacja: gdzies

drzewo binarne C

Post autor: ktosja »

Bardzo dziękuję.

-- 15 maja 2011, o 18:37 --

Starałam się napisać kod który wypisze mi kody gałęzi drzewa, dla 10 węzłów, tylko niestety coś nie tak niestety nie umiem dojść do tego co... :(
Proszę kolejny raz o pomoc:

Kod: Zaznacz cały

#include <stdio.h>
#include <stdlib.h>

struct drzewo{
        struct drzewo *rodzic;
        struct drzewo *lewy_syn;
        struct drzewo *prawy_syn;
        char dane;
};
void wypisz(struct drzewo * n, char c[], int p){ 
     int i;
  if(!(n->lewy_syn))
  {
    printf("%s:", n->dane);
    for(i = 0; i < p; i++) printf("%s",c[i]);
    printf("\n");
  }
  else
  {
    c[p] = '0'; wypisz(n->lewy_syn,c,p + 1);
    c[p] = '1'; wypisz(n->prawy_syn,c,p + 1);    
  }
}

int main(int argv, char *args[]) {
   
   struct drzewo * n;
   struct drzewo * x;
   struct drzewo * r;
   int i;
   char c[16];  // tablica przechowująca kody ścieżek
   
    n = (struct drzewo*)malloc(sizeof(struct drzewo));
    n->prawy_syn = (struct drzewo*)malloc(sizeof(struct drzewo));
    n->lewy_syn = (struct drzewo*)malloc(sizeof(struct drzewo));
    n->rodzic = n->lewy_syn = n->prawy_syn = NULL;
    n->dane = 'A';
    
   //10 nastepnych wezłow
    
     for(i = 1; i < 10; i++)
  {
    x= (struct drzewo*)malloc(sizeof(struct drzewo));
    x->prawy_syn = (struct drzewo*)malloc(sizeof(struct drzewo));
    x->lewy_syn = (struct drzewo*)malloc(sizeof(struct drzewo));
    x->lewy_syn = x->prawy_syn = NULL;
    x->dane = 'A'+i;

// tworzymy nowy korzeń
  
    r = (struct drzewo*)malloc(sizeof(struct drzewo));
    r->prawy_syn = (struct drzewo*)malloc(sizeof(struct drzewo));
    r->lewy_syn = (struct drzewo*)malloc(sizeof(struct drzewo));
    r->rodzic = NULL;
    
// do korzenia dołączamy węzły n i x

    n->rodzic = x->rodzic = r;
    
    r->lewy_syn = x; r->prawy_syn = n;            

// n staje się nowym korzeniem drzewa
    n = r;    
  };
  
  wypisz(n,c,0);
   
getch();
   return 0;
}
void_t
Użytkownik
Użytkownik
Posty: 103
Rejestracja: 14 maja 2011, o 18:25
Płeć: Mężczyzna
Pomógł: 26 razy

drzewo binarne C

Post autor: void_t »

Ok, źle podajesz format do printf.
Zauważ, że wypisujesz jeden znak, w wyniku tego musisz użyć innej (nazwijmy to) flagi.

Zamiast:

Kod: Zaznacz cały

printf("%s:", n->dane);
zastosuj:

Kod: Zaznacz cały

printf("%c:", n->dane);
Podobnie z drugim wywołaniem funkcji printf();

Przy okazji przypomnę - pamiętaj o zwalnianiu zaalokowanej pamięci, bo w chwili obecnej po uruchomieniu programu masz spory wyciek
==2932== HEAP SUMMARY:
==2932== in use at exit: 1,824 bytes in 57 blocks
==2932== total heap usage: 57 allocs, 0 frees, 1,824 bytes allocated
==2932== LEAK SUMMARY:
==2932== definitely lost: 1,248 bytes in 39 blocks
==2932== indirectly lost: 576 bytes in 18 blocks
Odnośnie jeszcze zapisu w stylu:

Kod: Zaznacz cały

r = (struct drzewo*)malloc(sizeof(struct drzewo));
Rzutowanie tutaj, jest operacją zbędną.
ktosja
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 28 kwie 2011, o 10:21
Płeć: Kobieta
Lokalizacja: gdzies

drzewo binarne C

Post autor: ktosja »

Dziękuje bardzo przydały się wskazówki.
Niestety dalej mam małe problemy z drzewami binarnymi.
tym razem mając już stworzone drzewo binarne, wczytując jakiś tekst chce go zakodować. wczytując kolejne znaki z pliku f :

Kod: Zaznacz cały

while((w=getc(f))!=EOF){
                         kodowanie(n,t,0,w);
                          }
funkcja kodowanie wypisze mi zakodowany ciag:

Kod: Zaznacz cały

void kodowanie(struct drzewo *n, char t[], int lenc, char w){
     int i;
     if(!(n->left))
     {
     if(n->ch == w){
    for(i = 0; i < lenc; i++){
          printf("%d", t[i]);
          
          }
    }
  }
  else
  {
    t[lenc] = 0; kodowanie(n->left,t,lenc + 1,w);
    t[lenc] = 1; kodowanie(n->right,t,lenc + 1,w);    
  }
}    
 
tylko że chce aby ten zakodowany ciąg zapisywał sie do pliku tekstowego. Cy można stosować w funkcji fprintf ?? bo coś nie chce mi działać
void_t
Użytkownik
Użytkownik
Posty: 103
Rejestracja: 14 maja 2011, o 18:25
Płeć: Mężczyzna
Pomógł: 26 razy

drzewo binarne C

Post autor: void_t »

Chcesz użyć funkcji fprintf by zapisać do pliku? Jest to jak najbardziej możliwe, spójrz na przykład:
ktosja
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 28 kwie 2011, o 10:21
Płeć: Kobieta
Lokalizacja: gdzies

drzewo binarne C

Post autor: ktosja »

wiem jak działa fprintf tylko ze wlasnie jak umieszczam instrukcje w funkcji nic mi do pliku nie zapisuje...;/
ale dziękuję za poświęcony czas
void_t
Użytkownik
Użytkownik
Posty: 103
Rejestracja: 14 maja 2011, o 18:25
Płeć: Mężczyzna
Pomógł: 26 razy

drzewo binarne C

Post autor: void_t »

Pokaż całą funkcję w której występuje fprintf, bo jak dotąd widziałem tylko wywołania printf.
ktosja
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 28 kwie 2011, o 10:21
Płeć: Kobieta
Lokalizacja: gdzies

drzewo binarne C

Post autor: ktosja »

Już wiem w czym robiłam błąd- pisałam zły typ zmiennej.
Ale pojawił się znowu inny problem, mianowicie mam teraz zakodowany plik, i odpowiednie drzewo binarne- gałęziom lewym przypisane jest 0 gałęziom prawym 1, w liściach znajdują się odpowiadające gałęziom znaki.

W jaki sposób poruszać się po drzewie tzn zczytuje kolejno kod jesli jest 0 ile w lewo jesli 1 ide w prawo az dojde do liscia, wtedy wypisuje wartosc w lisciu i zaczynam od poczatku...
moje proby wygladają w ten sposob :

Kod: Zaznacz cały


   while((bufor=getc(f))!= EOF){
                           i=7;
                                                      
                           if(!(n->left)){
                                             
                                             if(bufor & (1 << i)){
                                                  n=n->right;
                                                  i--;
                                                  }
                                             else{ 
                                                   n= n->left;
                                                   i--
                                                   }
                           }
                           
                           else{
                                printf("%c", n->ch);
                                }  
                           
   }
W jaki sposób na początku wskażnik umiescic na początku drzewa a następnie bo wypisaniu n->ch wrócic do korzenia ?
ODPOWIEDZ