Zaproponuj algorytm, który bada czy dany skończony ciąg, o elementach należących do pewnego zbioru liniowo uporządkowanego Et, może być ciągiem etykiet drzewa BST zapisanych w porządku preorder i jeśli jest to możliwe, tworzy takie drzewo BST.
Rozwiązanie powinno zawierać:
specyfikację zadania,
opis słowny metody rozwiązania,
algorytm rozwiązujący (ew. jego implementację),
analizę kosztu i
analizę poprawności algorytmu względem podanej specyfikacji.
Ma ktoś jakieś pomysły na rozwiązanie ?
[Algorytmy][C] Etykiety drzewa BST
-
- Użytkownik
- Posty: 16
- Rejestracja: 27 maja 2011, o 00:50
- Płeć: Mężczyzna
- Lokalizacja: Polska
[Algorytmy][C] Etykiety drzewa BST
Ostatnio zmieniony 22 gru 2011, o 13:09 przez Afish, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
[Algorytmy][C] Etykiety drzewa BST
Implementacja to pikuś, więc powiedzmy sobie co jest ważne.
Kiedy mówimy, że dany ciąg może być ciągiem etykiet drzewa BST ?
Z wykładu powinieneś to wiedzieć. Z notatek. Zatem?
Kiedy mówimy, że dany ciąg może być ciągiem etykiet drzewa BST ?
Z wykładu powinieneś to wiedzieć. Z notatek. Zatem?
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
[Algorytmy][C] Etykiety drzewa BST
Rekursja. Pierwszy element musi być korzeniem (w końcu to preorder), a po nim musi nastąpić najpierw lewe podrzewo, a potem prawe. Na obu należy osobno wywołać rekursję, tylko jak odróżnić, gdzie kończy się lewe, a zaczyna prawe? Pomyśleć o własności BST
Uwaga do mojego poprzednika: Twój post wygląda trochę, jakbyś wziął gotowy szablon ("powinieneś mieć (...) w notatkach z wykładu") i przekleił do niego pytanie bez zrozumienia. Akurat to zadanie ma małe szanse być rozwiązywanym na typowym wykładzie, a to dlatego, że nie jest na tyle ważne, żeby marnować cenny czas
Uwaga do mojego poprzednika: Twój post wygląda trochę, jakbyś wziął gotowy szablon ("powinieneś mieć (...) w notatkach z wykładu") i przekleił do niego pytanie bez zrozumienia. Akurat to zadanie ma małe szanse być rozwiązywanym na typowym wykładzie, a to dlatego, że nie jest na tyle ważne, żeby marnować cenny czas
-
- Użytkownik
- Posty: 16
- Rejestracja: 27 maja 2011, o 00:50
- Płeć: Mężczyzna
- Lokalizacja: Polska
[Algorytmy][C] Etykiety drzewa BST
Więc mamy, że pierwszym elementem jest wierzchołek. Etykiety z lewego podrzewa muszą być mniejsze od korzenia, a etykiety z prawego podrzewa większe od korzenia?
Czyli na poczatku mamy ciąg uporządkowany zapisany w porządku preorder ? Czyli np: 10,24,34,45,55,60?
Czyli na poczatku mamy ciąg uporządkowany zapisany w porządku preorder ? Czyli np: 10,24,34,45,55,60?
[Algorytmy][C] Etykiety drzewa BST
adams1604, przeczytaj pierwsze słowo w poście paladina. Pierwsza etykieta idzie do korzenia. Jeśli następny dany element jest mniejszy od korzenia, idziesz do lewego poddrzewa. Gdzie trafi ten wierzchołek jeśli patrzysz tylko na to poddrzewo?
-
- Użytkownik
- Posty: 16
- Rejestracja: 27 maja 2011, o 00:50
- Płeć: Mężczyzna
- Lokalizacja: Polska
[Algorytmy][C] Etykiety drzewa BST
Pierwsza etykieta to będzie korzeń. Następnie jeśli element jest mniejszy od korzenia to bedzie to lewa etykieta tego wierchołka. Wiec mamy lewe poddrzewo. Postepujemy zdognie z reguła preorder. I tak np przykladowy ciag liczb: 8 5 2 1 6 9 10 11 jest bedzie drzewem BST a ciag liczb: 4 5 2 1 3 nie bedzie drzewem BST bo 5>4 i nie moze byc w lewym poddrzewiu wiercholka 4.
Nie wiem dokladnie jak nalezy interpretowac takie zadania. Jakie bedzie koszt takich dzialan ?
Nie wiem dokladnie jak nalezy interpretowac takie zadania. Jakie bedzie koszt takich dzialan ?
[Algorytmy][C] Etykiety drzewa BST
Nie chodzi o to, że \(\displaystyle{ 5>4}\). Po prostu \(\displaystyle{ 5}\) zostanie umieszczona w prawym poddrzewie, a lewe będzie puste. Chodzi tutaj o to, że po \(\displaystyle{ 5}\) mamy elementy mniejsze od \(\displaystyle{ 4}\), które powinny być w lewym poddrzewie, ale my już dotarliśmy do prawego.bo 5>4 i nie moze byc w lewym poddrzewiu wiercholka 4.