Drzewa BST-CzyPotomek, CzyPrzodek

Question

Napisać funkcje sprawdzającą czy p jest potomkiem w : int CzyPotomek (wezel  *p, wezel *w)

Napisać funkcje sprawdzającą czy p jest przodkiem w : int CzyPrzodek (wezel  *p, wezel *w)

We wskazówkach mam zapisane, aby zrobić to rekurencyjnie.Pomoże ktoś ?

   struct wezel{
int klucz;
wezel *ojciec, *lewy, *prawy;
};

class BST{
wezel *korzen;

public:
int CzyPotomek (wezel *p, wezel *w);
int CzyPotomek (wezel *p, wezel *w);
};

 

Comments

Bez kodu struktury/klasy wezel raczej nikt ci nie pomoże.

---

Edytowałam post, wstawiłam kod 

Answer 1

Zacznijmy od funkcji int CzyPotomek (wezel  *p, wezel *w)

Algorytm bazuje na trzech obserwacjach:
1. Jeżeli p nie ma rodzica to nie jest potomkiem w.
2. Jeżeli p jest dzieckiem w to jest jego potomkiem.
3. Sprawdź czy rodzic p jest potomkiem w.

Druga funkcja jest bardzo podobna. Węzeł jest p jest przodkiem węzła w wtedy i tylko wtedy, gdy węzeł w jest potomkiem węzła p.

Comments

W teorii rozumiem zależności między potomkiem, ojcem, synem , ale nie wiem jk to zapisać w kodzie

---

Jeszcze troszkę ci pomogę.

int CzyPotomek (wezel  *p, wezel *w) {
    if (p nie ma rodzica)
        return 0;
    if (rodzic p == w)
        return 1;
    return CzyPotomek(rodzic wezła p, w);
}

Reszta w twoich rękach.