Witam, szukam pomysłu na przechodzenie drzewa, gdzie dzieci rodzica są zapisywane do mapy. Drzewo jest przechodzone w ten sposób że zaczynamy od korzenia aż do ostatniego liścia. Z tym że gdy osiągniemy liść, wracamy do korzenia i znowu do liścia z tym że już nie do tego samego. Po prostu musimy odwiedzić wszystkie liście zaczynając za każdym razem od korzenia. Widać więc że wszelakie preordery, postordery itd. raczej nie zadziałają. Póki co mam to rozwiązane tak że idę z korzenia jak najbardziej w lewo (można też w prawo) i po przejściu usuwam tę gałąź tak żeby nie była już brana pod uwagę. Następnie rekurencyjnie znowu wywołuję tę funkcję. Pojawiają się w tym przypadku 2 problemy. Pierwszy problem jest taki że usuwa mi się stopniowo to drzewo a nie chcę go kopiować w pamięci bo jest bardzo duże. Kolejnym problemem jest przepełnienie stosu (stack overflow), zapewne spowodowane dużą ilością rekurencji. Ma ktoś jakiś sensowny pomysł? Głównie zależy mi na rozw. drugiego problemu, bo gdy wyświetlam to drzewo (=przechodzę) to zatrzymuje mi się na mniej więcej 1/3 drzewa wyrzucając ten komunikat. Pozdrawiam
możesz sobie zaznaczać, których krawędzi już nie odwiedzać w trakcie robienia wielokrotnego DFS-a i lekko zmodyfikować DFS-a, żeby omijał te krawędzie. Jak dobrze zbudujesz drzewo to możesz po prostu zaczynać od dziecka i iść w górę.
Tak wiem, mogę je sobie oznaczać z tym że to rozwiązuje tylko pierwszy problem. Natomiast dalej pojawia się problem błędu stack overflow. Czy iteracyjne przechodzenie drzewa od 0 do n (gdzie n to ilość liści) to dobry pomysł? Być może rozwiąże problem.
jeśli n<10^6 to nie powinno być problemów z rekurencją, chyba że za dużo danych idzie na stos. Napisz może jaka była treść zadania, może coś przekombinowujesz.
Mam zbudować drzewo Trie i wepchać tam słownik. Wiadomo, muszę te wyrazy potem odczytać dlatego zawsze muszę zaczynać od korzenia (no albo od liścia ale odwracać potem wyraz)
to w jakim celu musisz wracać do korzenia przy DFSie?
Wynika to ze specyfiki drzewa Trie. Zapisane są w nim normalne wyrazy. Do samego korzenia wchodzę i zaczynam od jego dzieci, które są pierwszymi literami wyrazów. Dzieci tych dzieci to drugie litery wyrazów itd.
ZnajdzPierwszy() - od korzenia idziesz w lewo póki się da.
ZnajdzNastepny(PoprzednioZnaleziony) - szukasz w drzewie większego niż PoprzednioZnaleziony.
_13th_Dragon napisał(a):
ZnajdzPierwszy() - od korzenia idziesz w lewo póki się da.
ZnajdzNastepny(PoprzednioZnaleziony) - szukasz w drzewie większego niż PoprzednioZnaleziony.
Nie bardzo rozumiem... ZnajdzPierwszy() - ok. Tak robię. Ale o co chodzi z tą większością? W sensie następny liść?
Umiesz znaleźć w drzewie jakąś wartość? Dokładnie tak samo tylko jeden warunek zmieniasz.
Zawsze gdy chciałem znaleźć konkretną wartość w drzewie przechodziłem je pre-orderem, post-orderem lub in-orderem. Całe drzewo przeszukiwałem. W tym przypadku to mija się z celem bo drzewo musi być przechodzone w konkretny sposób. Jeśli się mylę to proszę mnie nakieruj.
Kompletny bezsens! Szukamy wartość X
- Bieżący węzeł - korzeń
- Jeżeli Bieżący węzeł jest NULL'em to koniec - nie znaleziono
- Porównujemy wartość z węzła bieżącego z X
3.1. jeżeli X jest mniejsza przechodzimy w lewo: Bieżący węzeł = lewy od bieżącego węzła
3.2. jeżeli X jest większa przechodzimy w prawo: Bieżący węzeł = prawy od bieżącego węzła
3.3 jeżeli X jest równa to koniec - znaleziono - przechodzimy do 2
NULL'em - może się stać jeżeli przechodzimy w lewo zaś w lewo nic nie ma, lub drzewo od początku było puste.
No tak się robi jeśli mamy drzewo BST i pochodne. Ale to szczególny przypadek. U mnie nie ma funkcjonalności znajdowania jakiegoś elementu - mam to zrobione na mapach i łatwo to zrobić.
Chodzi o coś w ten deseń
http://upload.wikimedia.org/wikipedia/commons/b/be/Trie_example.svg
z tym że tam jest cały słownik, setki wyrazów. Muszę po prostu wypisać wszystkie wyrazy.
Czyli potrzebujesz iteracyjną wersję preordera?
MateuszS napisał(a):
Drzewo jest przechodzone w ten sposób że zaczynamy od korzenia aż do ostatniego liścia. Z tym że gdy osiągniemy liść, wracamy do korzenia i znowu do liścia z tym że już nie do tego samego.
Rozumiem, że po prostu węzeł pamięta swoich dzieci ale nie rodzica.
MateuszS napisał(a):
Widać więc że wszelakie preordery, postordery itd. raczej nie zadziałają.
Dlaczego? Zwykły rekurencyjny DFS zadziała.
Zapuść DFS, wchodząc wgłąb do jakiegoś węzła dopisuj jego literkę do "aktualnego" wyrazu (wyraz ten przekazuj w dodatkowym parametrze funkcji rekurencyjnej DFS). Wracając z węzła odpisuj dopisaną (ostatnią) literkę z "aktualnego" wyrazu. Będąc w węźle końcowym jakiegoś wyrazu (to nie muszą być tylko liście!) "aktualny" wyraz będzie jednym z wyrazów zapisanych w drzewie.
DFS('wezel', 'wyraz')
- dopisz literkę 'wezel' do 'wyraz'
- jeśli 'wezel' jest węzłem końcowym wyrazu
- użyj 'wyraz' (tu mamy cały wyraz)
- dla każdego dziecka 'd' węzła 'wezel' wykonaj
- DFS('d', 'wyraz')
- odpisz ostatnią literkę z 'wyraz'
Iteracyjnie mogę to napisać wraz z oznaczaniem węzłów które przeszedłem tak jak ktoś wcześniej napisał ale nie wiem czy to będzie najlepsze wyjście. Raczej nie.
@up ok spróbuję
jak zrobisz tak jak adf88 napisal to nic nie bedziesz musial oznaczac
Dzięki! Działa idealnie. Sam nigdy bym na takie cudo nie wpadł. :(