Po pierwsze: czemu zwracane są liczby chociaż funkcja jest void?
Co do zadania to tu masz bardzo ładne wyjaśnienie co to jest kopiec: http://informatyka.wroc.pl/node/433?page=0,1
Jak się już wczytasz (albo po prostu wiesz co to jest kopiec binarny) to stwierdzisz następującą rzecz: jeśli mamy pozycje jakiegoś node w tablicy, nazwijmy ją idx
, to pozycja jego lewego dziecka to 2*idx
. Co więcej, ponieważ to kopiec binarny, każdy wierzchołek ma co najwyżej dwoje dzieci.
Zapewne zauważyłeś, że żeby to ładne założenie o numerze dziecka działało, wierzchołki trzeba trzymać w tablicy od pozycji 1
, a nie 0
jak normalnie, więc 1
to po prostu numer korzenia.
Co więc robi twoja funkcja? Zwraca liczbę liści dla drzewa którego korzeń znajduje się w wierzchołku node
. Oto dlaczego:
Linijka:
if(node>HeapSize) return 0;
Sprawdza czy node
należy do drzewa. Jeśli jest większy od ilości wierzchołków w drzewie, czyli nie należy do tego drzewa, to zwracamy 0. Nieistniejące drzewo ma zero liści.
int aux=node<<1;
To może lub nie wyglądać strasznie (w zależności od znajomości C/C++) ale jest to po prostu przesunięcie bitowe w lewo, czyli dodanie zera po prawej stronie zapisu binarnego liczby, czyli po prostu pomnożenie razy dwa (zakładając że wynik mieści się w int
cie). Tak więc w aux
mamy po prostu numer lewego dziecka wierzchołka node
.
if(aux>HeapSize) return 1;
Jeśli okazuje się że to dziecko nie mieści się już w tym drzewie, to znaczy że wierzchołek node
nie ma dzieci - jest liściem. Zwracamy więc jeden, znaleźliśmy kolejny liść.
return Guess(aux,HeapSize)+Guess(aux+1,HeapSize);
Skoro doszliśmy do tej linijki, znaczy że node
nie jest liściem, zwracamy więc sumę ilości liści w jego lewym poddrzewie (tym dla którego jego lewe dziecko - aux
- jest korzeniem) i jego prawym poddrzewie (z prawym dzieckiem - aux+1
- jako korzeń).
I voilà! Jeśli wywołaliśmy tę funkcję z korzeniem jako pierwszym argumentem, to dostaniemy liczbę liści w drzewie. Oczywiście, zawołanie Guess(1)
wywali błąd kompilacji jak już @Sopelek trafnie zauważył. Musisz podać jeszcze wielkość kopca (HeapSize
) no i oczywiście zmienić deklaracje funkcji na taką która zwraca int
(patrz komentarz @mwl4 poniżej):
int Guess(int node,int HeapSize)
Powodzenia na egzaminie!