Ponieważ jestem tu pierwszy raz, na wstępie chciałabym przywitać wszystkich użytkowników :)
A moje pytanie brzmi następująco: jak napisać algorytm, który zwraca indeks ojca poprzednika węzła w drzewie wyszukiwań binarnych? Mógłby mi ktoś coś doradzić?
poprzednika znajdziesz tak:
http://stackoverflow.com/questions/4581576/implementing-an-iterator-over-a-binary-search-tree
Jeśli węzeł ma lewego potomka, to poprzednikiem jest element o największym kluczu w lewym poddrzewie węzła (drzewie, którego korzeniem jest lewy potomek węzła).
Jeśli węzeł nie ma lewego potomka, to poprzednikiem węzła x jest pierwszy rodzic, dla którego węzeł leży w prawym poddrzewie.
Jeśli dwa powyższe warunki nie są spełnione, to nie istnieje jego poprzednik (węzeł ma najmniejszy klucz).
Znalezienie rodzica zależy od tego, jak masz przedstawione drzewo w pamięci. Możesz trzymać wskaźnik do rodzica, jeżeli węzłami są struktury lub dzielić indeks przez 2, jeżeli masz to przedstawione w tablicy, gdzie a ma potomków 2a, 2a+1 i numerację zaczynamy od 1.