Drzewo binarne Pierwsze wyszukiwanie

Question

Używam OCaml. Mam typ:

type 'a bt = Empty | Node of 'a * 'a bt * 'a bt;; 

Mam także przykładowy BST:

let tree = Node(1,Node(2,Node(4,Empty,Empty),Empty),Node(3,Node(5,Empty,Node(6,Empty,Empty)),Empty)); 

muszę napisać: breadthBT : 'a bt -> 'a list funkcję, która będzie Szerokość pierwszego wyszukiwania przejścia. Dla powyższego drzewa przykładowego powinno ono powrócić: [1; 2; 3; 4; 5; 6]

Jak napisać tę funkcję? Mogę tylko napisać następującą funkcję, która wykorzystuje DST:

let rec breadthBT tree = 
if tree=Empty then [] 
else let Node(w,l,r)=tree in (w::breadthBT l)@breadthBT r;; 

Przede zwrotów funkcję (np drzewa) [1; 2; 4; 3; 5; 6]. Ale nie mogę napisać funkcji, która używa BFS. Czy mógłbyś mi pomóc?

Answer 1

To nie jest rozwiązanie kompilacyjne. Tylko wskazówka. Powinieneś iterować od najwyższego poziomu węzła głównego do węzłów poziomu głębokiego. Niech nasza funkcja odbiera akumulator dla odpowiedzi i listę węzłów (twoje "wartości bt") jako drugi parametr. Możesz zmapować tę listę, otrzymując pierwszy element potrójny, a następnie otrzymasz kolejną część odpowiedzi. Musisz także ocenić następny poziom drzewa. Dla każdego węzła jest co najwyżej dwóch potomków. Możesz zmapować listę i zastosować _a_function_, aby otrzymać listę potomków. Będzie to następny poziom twojego drzewa. I niż --- rekursja.

A nie określi tego _a_function_. Spróbuj dowiedzieć się, co jest concatMap w google.

Happy hacking!

Answer 2

Wyobraź sobie, że przyklejasz nos do drzewa. Czy możliwe jest przemierzanie drzewa w pierwszy sposób, bez ustawiania zakładek w twoim notatniku? Nie, ponieważ kolejność może sprawić, że przeskoczysz z jednej gałęzi do drugiej niepowiązanej gałęzi. Potrzebujesz więc notatnika z "pozostałymi pozycjami do odwiedzenia". Wybierasz następną pozycję z notatnika i przeskakujesz na ślepo. Ponieważ usuwasz odwiedzone pozycje z notatnika, jesteś w węźle, którego jeszcze nie odwiedziłeś. A ponieważ nie możesz uzyskać drzewa bez odwiedzania pośrednich węzłów, nie odwiedziłeś dwóch węzłów nad tobą. Ale przeciwstawiasz się instynktowi bezpośredniego wspinania się na gałęzie - heck, to jest szerokość pierwsze zamówienie. Nie chcesz zapomnieć o tych dwóch nie odwiedzonych węzłach, więc chcesz umieścić je w notatniku. Gdzie je kładziesz, przed nim lub na plecach? Na odwrocie oczywiście, w przeciwnym razie wybierzecie jeden z nich natychmiast i tego właśnie chcemy uniknąć. Et voila: twój notatnik jest kolejką FIFO węzłów, które przechowujesz (tj. Przechodzą) jako akumulator, ale także zużywasz do wybierania poddrzewa do odwiedzenia.