[C++] drzewa binarne - wypisanie najdłuższej ścieżki

[anilahcim]

Mam problem z napisaniem kodu, który wypisywałby najdłuższą ścieżkę (rekurencyjnie). Chyba nie do końca rozumiem, jak działa rekurencja jeśli chodzi o drzewa binarne, dlatego nie wiem, jak napisać tę funkcję. Próbowałam skorzystać z funkcji na wysokość, ale nie mam pomysłu, co zrobić, żeby ją wypisać.

Kod: Zaznacz cały

int wysokosc(wezel*d)
{
   if(d==NULL)
      return 0;
   else
   {
      int hl=wysokosc(d->lewy);
      int hp=wysokosc(d->prawy);
      if(hl>hp)
            return (hl+1);
      else
            return (hp+1);
   }
}

[siryj]

Mam taki pomysł. Zmień funkcję wysokość tak żeby zapisywała do listy wartości węzłów jeśli należa do najdłuższej ścieżki, a potem poprostu wyświetl tą listę. Myślę że funkcję wysokość trzeba zmienić tak, żeby zwracała strukturę która zawiera długość listy i wskażnik na listę

[royas]

Jeśli węzeł drzewa ma wskazanie na rodzica, to możesz zmodyfikować wysokość tak aby oprócz wysokości zwracał również wskazanie na których z najgłębiej położonych węzłów. Po wykonaniu dla całego drzewa wypisujesz po prostu ścieżkę od tego węzła do korzenia.