Dodaj do ulubionych

Wyszukiwanie maxa w drzewie

15.02.06, 01:41
Hej, znow mam problem :)
Chce napisac funkcje zwracajaca wskaznik do wezla z max. wartoscia.
Myslalem ze cos takiego bedzie ok:

void max_t(DRZEWO *d,int *wartmax, DRZEWO **wmax)
{
if(d != NULL) {
if(d->wart > *wartmax) {
*wartmax = d->wart;
*wmax = d;
}
}
else {
max_t(d->lewy,wartmax,wmax);
max_t(d->prawy,wartmax,wmax);
}
}
DRZEWO *max_tree (DRZEWO *d)
{
DRZEWO *wmax = NULL;
int wartmax = 0;
if(!d)
return NULL;
else {
wartmax = d->wart;
max_t(d,&wartmax,&wmax);
return wmax;
}
}
Ale okazalo sie ze nie :/
Zawiesza sie, a po zakonczeniu tych procedur, wezel niby maksymalny jest rowny
NULL.Czy ktos widzi blad???

Jesli wiecie jak napisac taka funkcje, to tez nie pogardze.
Oczywiscie drzewo nie jest BST, tylko dowolne.
Pozdrawiam!
Obserwuj wątek
      • mistrz_patelni Re: Wyszukiwanie maxa w drzewie 15.02.06, 02:45
        Skrocilem.Jesli widzicie jeszcze jakies bledy to piszcie.




        void max_t(DRZEWO *d, DRZEWO **wmax)
        {
        if(d != NULL) {
        if(d->wart > (*wmax)->wart)
        *wmax = d;
        max_t(d->lewy, wmax);
        max_t(d->prawy, wmax);
        }
        }

        DRZEWO *max_tree (DRZEWO *d)
        {
        DRZEWO *wmax = d;
        DRZEWO *wmin = d;
        if(!d)
        return NULL;
        else {
        max_t(d, &wmax);
        return wmax;
        }
        }
        • ktosktomafajnegomisiaczka Re: Wyszukiwanie maxa w drzewie 18.02.06, 01:22
          ogolnie, poza ewentualna zmiana (niewiele potrzebnej) rekurencyjnosci na
          iteracje (ktora i tak by musiala uzywac jakiegos stosu) o tutaj juz sie nie da
          wiele wiecej zrobic..

          zmiana z rekursji w iteracje jest juz tez nawet kosmetyka, poniewaz zakladajac
          ze drzewo nie jest posortowane w zaden sposob, to i tak trzeba wszystkie pola
          odwiedziec. iteracja zrobila by to tylko troche szybciej i zajmujac mniej
          pamieci (acz napisanie takiej petli kosztuje duzo wiecej roboty niz jeden
          rekurencyjnej funkcyjki)
    • jacu131 Re: Wyszukiwanie maxa w drzewie 15.02.06, 18:32
      A dlaczego funkcja max_t nie zwraca niczego? Ja bym dał żeby zwracała wskaźnik
      do struktury drzewo (ostatecznie pokazujący na węzeł z maksymalną wartością).
      Wtedy funkcje max tree napisałbym tak:

      DRZEWO *max_tree (DRZEWO *d)
      {
      DRZEWO *wmax = d;
      DRZEWO *wmin = d;
      if(!d) return NULL;
      else return max_t(d, &wmax);
      }

      Ale to taka propozycja na pierwszy rzut oka, bez kompilowania, ręki uciąć nie
      dam. Zresztą nie skompiluję tego bez zadeklarowania paru rzeczy
Inne wątki na temat:

Popularne wątki

Nie pamiętasz hasła

lub ?

 

Nie masz jeszcze konta? Zarejestruj się

Nakarm Pajacyka