Załóżmy, że masz pełne drzewo binarne (tzn. Każdy wewnętrzny węzeł ma dokładnie dwóch niepustych potomków). Każdy węzeł zawiera niezerową liczbę całkowitą. Zadanie polega na zakodowaniu i zdekodowaniu drzewa do / z listy liczb całkowitych.
Drzewo jest przechowywane wewnętrznie coś takiego:
struct node {
int data;
struct node *left, *right;
};
Musisz zaimplementować dwie funkcje:
int *encode(struct node *root);
struct node *decode(int *array);
Od Ciebie zależy, jak kodujesz i dekodujesz.
Punkty za:
- minimalna długość kodowania
- złożoność (idealnie liniowa w liczbie węzłów)
- oryginalność
Brak punktów za długość kodu źródłowego i nie jesteś ograniczony do C.
Przykład drzewa:
5
/ \
3 2
/ \
2 1
/ \
9 9
code-challenge
tree-traversal
Alexandru
źródło
źródło
int *
to czarna skrzynka dla użytkownika.Odpowiedzi:
~ 1,03 N
Wydaje się, że wszystkie dotychczasowe odpowiedzi wymagają co najmniej 2 * N * 32-bitów. (Z wyjątkiem rozwiązań w językach, które pozwalają na wartości całkowite dłuższe niż 32 bity, takich jak rozwiązania Haskell i Ruby - ale te nadal będą wymagały dodatkowych bajtów do kodowania, gdy dane będą większe niż 16 KB).
Oto rozwiązanie, które wymaga jedynie pułapu N + (N / 32) +1 do przechowywania. To zbliża się do 1,03125 N dla dużych N i jest poniżej 1,1 N dla wszystkich N większych niż 20.
Chodzi o to, aby zapisać dodatkowy bit dla każdego węzła, gdzie 1 to „hasChildren”. Te bity są upakowane w N / 32 słowach z góry.
(ukończ implementację tutaj)
źródło
Ten program Haskell koduje drzewo n węzłów w n liczbach całkowitych. Sztuczka polega na tym, że koduje dane węzła podwójnie, a następnie używa bitu niższego rzędu, aby wskazać, czy jest to węzeł liścia czy węzeł wewnętrzny.
Technicznie rzecz biorąc,
Parser
monada tutaj jest nadmiernie zabijana, ponieważ utworzono tylko jeden parser,decoder
a ja mogłem umieścić logikę łańcuchową parsera bezpośrednio tam. Ale w ten sposób dekoder jest bardzo wyraźny, aParser
pomimo niewielkich rozmiarów jest rozsądną, prostą strukturą analizującą.Uruchomienie tego spowoduje:
źródło
W C.
Kod:
Dekodowanie:
Główny:
Uwaga. Każdy węzeł jest zakodowany jako dwie liczby całkowite (plus jedna liczba całkowita dla liczby węzłów).
Dostarczone drzewo koduje w ten sposób:
źródło
W Ruby, z takim samym kodowaniem jak @MtnViewMark :
Koszt to jedna liczba całkowita na węzeł (
data << 1 | has_childs
):źródło
Biorąc pod uwagę drzewo binarne z
n
węzłami, koduje je na liście2n + 1
liczb całkowitych. Algorytmy kodowania i dekodowania mająO(n)
złożoność.Używam liczby całkowitej 0 jako znacznika wartownika podczas kodowania, wskazując, kiedy rozwijam rekurencję. Następnie, kiedy dekoduję, umieszczam tworzone przeze mnie węzły na stosie (swego rodzaju) i używam zer na liście, aby śledzić, gdzie dodać następny węzeł. Nie próbowałem, ale jestem prawie pewien, że dekodowanie pękłoby, gdyby drzewo nie było kompletne.
Zapisano to jako
encode.c
skompilowane i wykonane. Ten program korzysta z podanego przez Ciebie drzewa przykładów i pomyślnie przetestowałem go na kilku innych.źródło
Mój kod koduje drzewo podczas przechodzenia w przedsprzedaży, każdy liść w dwóch liczbach wewnętrznych (jego dane, po których następuje 0), a każdy wewnętrzny węzeł w jednej liczbie wewnętrznej (po danych następuje lewe dziecko, potem jego prawo). Dla pełnego drzewa binarnego (jak go zdefiniujesz) z n węzłami, n musi być nieparzyste, i są (n + 1) / 2 liście i (n-1) / 2 wewnętrzne węzły, więc to jest 3n / 2 + 1 / 2 liczby całkowite do kodowania.
ostrzeżenie: niesprawdzone, wystarczy wpisać.
źródło
Oto moja próba. Przechowuje drzewo w tablicy o rozmiarze 2 ** głębokość + 1. Służy
a[0]
do przechowywania rozmiaru ia[size]
do przechowywania indeksu pierwszego „pustego węzła”, który napotyka podczas pierwszej głębokości. (Pusty węzeł to miejsce, w którym dziecko byłoby przechowywane, gdyby rodzic je miał). Każdy pusty węzeł zawiera indeks następnego pustego węzła, który zostanie napotkany.Ten schemat pozwala uniknąć rezerwowania bitów w celu oznaczenia elementów potomnych obecności, dzięki czemu każdy węzeł może korzystać z pełnego zakresu liczb całkowitych. Pozwala również na niezrównoważone drzewa - rodzic może mieć tylko jedno dziecko.
wynik:
Enkoder:
Dekoder:
(dzięki @ Daniel Sobral za naprawienie formatowania)
źródło
Scala:
Jest to podejście wykorzystujące przestarzałą składnię, ale kompiluje się bez błędów w Scali 2.9.1. Generuje Drzewo i dekoduje każde zakodowane Drzewo do tej samej Tablicy, której użyto do kodowania. Może dziś w jakiś sposób pozbyłem się przestarzałych ostrzeżeń.Wow - to było proste. Pierwszy pomysł zadziałał natychmiast.
źródło