Binarne drzewa wyszukiwawcze

Witam.

Robię jeden z projektów na SPOJ'u, który się zwie Binarne drzewo wyszukiwawcze (TBDW). Wszystko napisane, ale niestety otrzymuję cały czas błędną odpowiedź. Walczę z tym już dość długo i nie mogę znaleźć błędu w kodzie, a wiem, że ktoś patrzący na problem z boku, łatwiej dostrzeże jakiś błąd.

W związku z tym mam pytanie, czy jest ktoś, kto podjąłby się sprawdzenia implementacji drzewa BST w moim programie?

Oto treść zadania:

Na wejściu podana jest sekwencja instrukcji: zapytań, modyfikacji drzew oraz przeglądania węzłów drzewa (składnia każdego polecenia identyczna: duża litera oznaczająca instrukcję oraz liczba), precyzyjnie:

* wstawienie elementu x do drzewa (I x) (1 <= x <= 10000),
* usunięcie elementu x z drzewa (D x),
* wyszukiwanie elementu x w drzewie (S x),
* znajdowanie najmniejszego (X 0) oraz największego (X 1) elementu w drzewie,
* znajdowanie następnika elementu x (N x) oraz poprzednika elementu x (P x),
* przeglądanie wierzchołków drzewa trzema sposobami (inorder: R 0, preorder: R 1, postorder: R 2). 

W zadaniu nie można stosować dodatkowych optymalizacji, podczas usuwania elementu, który posiada dwóch potomków - wstawiamy w jego miejsce jego bezpośredniego poprzednika.
Wejście

t [liczba testów = 10]
n [liczba instrukcji do wykonania <= 10000]
instrukcje... [w jednej linii jedna instrukcja]
[kolejne testy]

Wyjście

W pierwszej linijce odpowiedzi do danego testu powinien znaleźć się napis: test nr. Odpowiedzi podawane są w kolejnych linijkach. W przypadku jednej z instrukcji R należy na wyjściu wydrukować wartości kluczy w kolejnych węzłach drzewa zgodnie z porządkiem, dla zapytań należy wydrukować wartość klucza (dla Min, Max, Succ, Pred, Search (tak)) lub - dla Search (nie), Pred (nie) lub Succ (nie). Zwracam uwagę, że żądanie wydrukowania następnika lub poprzednika elementu, którego nie ma w drzewie zakończyć się powinno wydrukowaniem -.

Przykład

Wejście:
4
13
I 5
I 8
I 3
I 4
I 7
R 1
I 1
R 2
S 7
S 6
N 3
D 8
R 0
10
I 4
I 2
R 0
D 2
X 1
X 0
I 1
X 0
X 0
X 1
10
I 4
P 1
I 1
R 1
I 2
I 5
R 0
D 2
I 2
P 1
11
I 3
X 0
I 2
D 3
I 1
I 5
I 4
D 4
I 4
D 4
X 1

Wyjście:
test 1
5 3 4 8 7
1 4 3 7 8 5
7

4
1 3 4 5 7
test 2
2 4
4
4
1
1
4
test 3

4 1
1 2 4 5

test 4
3
5

Z góry dziękuję za zainteresowanie.

PS. Kodu nie zamieszczam tutaj, bo mimo iż nie działa, to komuś mógłby za podkładkę posłużyć, a ja później leżę i kwiczę ;) Chętnemu prześlę na PW.

Ja zrobiłem to zadanie... za 50-tym razem :D nie lubię tej struktury, jest strasznie trudna w implementacji, jak na możliwości które daje... w końcu BST to w pesymistycznym przypadku kwadraciak, i tak najczęściej trzeba pisać jeszcze dużo bardziej skomplikowane struktury, np. drzewa czerwono-czarne, czy drzewa AVL.

Jak chcesz, to mogę rzucić okiem. Może jakiś błąd wynajdę, ewentualnie przyrównam z moim kodem.

Ja natomiast lubię drzewa BST...
Nie wiem, czego dokładnie oczekujesz? Kodu całego programu?
W C czy C++? Może napisz dokłądniej... ;)

Spykaj napisał(a)

Jak chcesz, to mogę rzucić okiem. Może jakiś błąd wynajdę, ewentualnie przyrównam z moim kodem.

Wysyłam kod na maila. Będę wdzięczny, jeżeli uda Ci się znaleźć problem.

nwpirx napisał(a)

Ja natomiast lubię drzewa BST...
Nie wiem, czego dokładnie oczekujesz? Kodu całego programu?
W C czy C++? Może napisz dokłądniej... ;)

Tak jak pisałem, chciałbym, aby jakiś znający się na rzeczy człowiek sprawdził moją implementację BST napisaną w C++ i wytknął mi błąd/błędy, przez które SPOJ nie chce jej przyjąć :)