[es] - [zadatak]funkcija za minimum u drvetu

milos_r
Beograd

Član broj: 49289
Poruke: 38
79.101.228.*

Profil

[zadatak]funkcija za minimum u drvetu

^{22.01.2009. u 23:32 - pre 185 meseci}

Imam jedan neobican problem vezan za funkciju za trazenje minimalne vrednosti u drvetu. Funkcija radi ali nikako nemogu da joj ubacim neki uslov za prazno drvo tj. cim ubacim bilo kako return 0; funkcija mi nadalje uvek vraca 0. Evo i koda:

Code:

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

struct cvor{
    int broj;
    struct cvor *l, *d;
};

void ubaci_u_drvo(struct cvor **pdrvo, int b){

    if (*pdrvo == NULL){
        struct cvor *novi;
        if ((novi = (cvor*)malloc(sizeof(cvor))) == NULL){
            fprintf(stderr, "Greska prilikom alokacije memorije");exit(1);}
        novi->broj = b;
        novi->l = NULL;
        novi->d = NULL;
        *pdrvo = novi;}
    else{
        if (b < (*pdrvo)->broj)
            ubaci_u_drvo(&((*pdrvo)->l), b);
        else
            ubaci_u_drvo(&((*pdrvo)->d), b);
    }
}

int pronadji(struct cvor *drvo){
        int vrati, l, d,;

        if (drvo != NULL){
            l = pronadji(drvo->l);
            d = pronadji(drvo->d);
            if (l < d ){
                if(l < drvo->broj)
                    vrati=l;
                else
                    vrati=drvo->broj;
                    }
            else{
                if(d < drvo->broj)
                    vrati=d;
                else
                    vrati=drvo->broj;
                }
            }
return vrati;
}

void ispisi_drvo(struct cvor *drvo){
    if (drvo != NULL){
        ispisi_drvo(drvo->l);
        printf("%d ", drvo->broj);
        ispisi_drvo(drvo->d);
    }
}

void obrisi_drvo(struct cvor *drvo){
    if (drvo != NULL){
        obrisi_drvo(drvo->l);
        obrisi_drvo(drvo->d);
        free(drvo);
    }
}

int main(){
    struct cvor *drvo = NULL;
    int i;
    int max=1,min=0;
    while(1){
        printf("ubacujte brojeve u drvo za izlaz unesite 0: ");
        scanf("%d",&i);
        if(i==0) break;
        ubaci_u_drvo(&drvo,i);}

    ispisi_drvo(drvo);
    putchar('\n');

    printf("najmanji cvor u drvetu je: %d\n",pronadji(drvo));
    obrisi_drvo(drvo);
}

Znaci ovako napisana funkcija radi ali nema dobru povratnu vrednost u slucaju da je drvo prazno, a kad ubacim jedan "else return 0;" uvek mi vraca 0. Probao sam i da pocnem funkciju sa if(drvo==NULL) return 0; pa else ovo sve ostalo i opet ista stvar. Ovo se inace ne desava za funkciju koja trazi maksimum koja je skoro identicnog koda samo su joj vrednosti u ovim if-ovima zamenjene.
Ako neko ima ideju bio bih mu zahvalan
Milos

Odgovor na temu

Goran Rakić
Beograd

Član broj: 999
Poruke: 3766

Sajt: blog.goranrakic.com

+125 Profil

Re: [zadatak]funkcija za minimum u drvetu

^{22.01.2009. u 23:51 - pre 185 meseci}

Ako ubaciš proveru da li je drvo NULL, moraš da istu proveru ubaciš i pre prelaska na levu/desnu stranu.

Svako drvo na nekoj dubini postane "prazno". Problem je što tvoja provera onda vrati nulu kao vrednost/grešku. Kako je to verovatno najmanja vrednost u drvetu (svi čvorovi su izgleda pozitivni), to bude i konačan rezultat. Maksimum "radi" zato što nula ne bude najveći čvor. Upiši sve negativne pa će minimum raditi, a maksimum neće ;)

Nevezano za ovaj zadatak, ne smeš brkati signaliziranje greške i vrednost. Za grešku uvek koristi samo vrednost koja inače nije dopuštena (i onda je ispravno "obradi"), koristi globalnu promenljivu ili program napiši tako da do greške ne može da dođe ;)

http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja

Odgovor na temu

milos_r
Beograd

Član broj: 49289
Poruke: 38
79.101.228.*

Profil

Re: [zadatak]funkcija za minimum u drvetu

^{23.01.2009. u 08:39 - pre 185 meseci}

Citat:

Goran Rakić: Ako ubaciš proveru da li je drvo NULL, moraš da istu proveru ubaciš i pre prelaska na levu/desnu stranu.

Svako drvo na nekoj dubini postane "prazno". Problem je što tvoja provera onda vrati nulu kao vrednost/grešku. Kako je to verovatno najmanja vrednost u drvetu (svi čvorovi su izgleda pozitivni), to bude i konačan rezultat. Maksimum "radi" zato što nula ne bude najveći čvor. Upiši sve negativne pa će minimum raditi, a maksimum neće ;)

Nevezano za ovaj zadatak, ne smeš brkati signaliziranje greške i vrednost. Za grešku uvek koristi samo vrednost koja inače nije dopuštena (i onda je ispravno "obradi"), koristi globalnu promenljivu ili program napiši tako da do greške ne može da dođe ;)

Hvala za ovo prvo sto si rekao, sad mi je naravno jasno zasto minimum nece da radi, samo jos da smislim kako to da postavim da profunkcionise. A za ovo drugo te nisam bas najbolje shvatio. Osim ovoga sto si rekao za globalne promenljive sto je najstroze zabranjeno i nepriznaje se kao ispravan zadatak.
Milos

Odgovor na temu

milos_r
Beograd

Član broj: 49289
Poruke: 38
79.101.228.*

Profil

Re: [zadatak]funkcija za minimum u drvetu

^{23.01.2009. u 09:46 - pre 185 meseci}

Bzvz, evo shvatio sam da sam totalno pogresnu koncepciju imao od pocetka. Pre svega uopste nisam iskoristio cinjenicu da je to uredjeno drvo i da se minimalna vrednost svakako nalazi na levoj strani ili u korenu. Ovako postavljeno svakako nema potrebe nizakakvim rekurzijama vec je moguce kao kroz listu proci iterativno do poslednjeg cvora kojem je levi pokazivac NULL i taj ce ujedno biti najmanji.
Recimo nesto ovako:

Code:

int pronadji(struct cvor *drvo){
    int vrati;
    if (drvo == NULL)
            return 0;
    if(drvo->l==NULL)
        vrati=drvo->broj;
    while (drvo->l!=NULL){
            drvo=drvo->l;
            vrati=drvo->broj;
        }
return vrati;
}

Pozdrav
Milos

Odgovor na temu