Zainspirowany ostatnim pytaniem dotyczącym SO ...
Napisz funkcję, aby wydrukować drzewo binarne w następującym formacie:
3
/ \
1 5
\ / \
2 4 6
- Dane wyjściowe powinny składać się z linii węzłów, po której następuje linia znaków
/
i\
znaków wskazujących relacje, po której następuje linia węzłów itp. - Możesz założyć, że wszystkie węzły są reprezentowane jako pojedynczy znak.
- Sąsiadujące węzły na najniższym poziomie powinny być oddzielone co najmniej jedną spacją, węzły dalej w górę powinny być odpowiednio oddzielone.
- Węzły z dwójką dzieci powinny być umieszczone dokładnie pośrodku ich bezpośrednich dzieci.
- Ukośniki relacji powinny znajdować się w połowie drogi między rodzicem a odpowiednim dzieckiem (w dowolnym kierunku).
Wejście:
Dane wejściowe zostaną przekazane jako argument funkcji. Nie podam dokładnej struktury drzewa, jednak musi on być użyteczny jako rzeczywiste drzewo binarne. Żadne „drzewa nie są reprezentowane w moim programie jako ciągi, które przypadkowo wyglądają jak oczekiwane wyniki”.
Możesz wydrukować do strumienia wyjściowego lub zwrócić ciąg zawierający dane wyjściowe, według własnego wyboru.
Punkty za najkrótszy kod, ale zdecydowanie wolałbym w pełni działające długie rozwiązanie niż 90% pracujące krótkie.
Aktualizacja nagrody
Jeśli chodzi o nagrodę, ja (Optymalizator) wprowadzam niewielkie zmiany:
- Dane wejściowe mogą pochodzić z argumentu STDIN, ARGV lub funkcji.
- Dane wyjściowe muszą być na STDOUT (lub
console.log
dla JS) - Możesz założyć, że dane wejściowe mają postać tablicy, na przykład.
[1,2,3]
lub[1 2 3]
Aktualizacja 2 - Drzewo binarne powinno być drzewem wyszukiwania binarnego. Ponieważ początkowo o tym nie wspominałem, pozwolę użytkownikom traktować konwersję normalnej tablicy na binarną tablicę drzewa wyszukiwania jako osobny program, a końcowa liczba bajtów będzie tylko dla programu, który pobierze tablicę jako argument i wydrukuje ją jak drzewo binarne.
źródło
30000,1000,499999
Odpowiedzi:
Fortran 77 - 1085 znaków
Drzewo jest reprezentowane w tablicy wejściowej
t
w zwykły sposób, root na 1, root-> left na 2, root-> right na 3 root-> left-> left o 4 ...Wyjście powinno mieścić się w konwencjonalnym terminalu o głębokości do 5 poziomów.
Używam dokładnie jednego ukośnika między każdą parą węzłów, co wygląda dość głupio u góry, gdy są cztery lub więcej poziomów. Pozwoliłem na maksymalnie trzycyfrowe węzły.
Pełny program z komentarzami i rusztowaniem uruchamiającym:
Dane wyjściowe z danymi wejściowymi równoważnymi z przykładem:
źródło
CJam,
10099 bajtówDane wejściowe muszą być listą znaków, bez znaków kontrolnych ASCII. Puste węzły są oznaczone spacją. Musi to być także idealne drzewo binarne z dokładnie 2 węzłami n -1.
Przykład:
Lub po prostu użyj ciągów:
Wynik:
Wyjaśnienie
Skrypt konwersji
Akceptuje znaki lub cyfry jednocyfrowe.
Przykłady (wszystkie są takie same):
Wynik:
Jest to prosta konstrukcja drzewa kartezjańskiego.
źródło
Python 2, 411 bajtów
Uwaga: Pierwszy poziom wcięcia to 1 spacja, drugi to jedna tabulacja.
Wywołanie
f
z listą ciągów lub znaków jednoznakowychNone
, np.f(['1',None,'3'])
. Lista nie może być pusta.To powinno być zgodne z zasadami nagrody.
Skrypt konwertera:
Konwertuje i tablicę na format używany przez drukarkę drzewa binarnego. Przykład:
-
Przykłady:
Aby je uruchomić, musisz mieć nazwę pliku głównego
bt.py
i nazwę pliku konwerteraconv.py
.źródło
['1','2','3','4','5','6','7','8','9']
tablicy nie są tym, co pokazałeś. Powinien mieć3
jako właściwe dziecko,2
którego właściwe dziecko1
jest elementem głównym.APL, 125 znaków
Przykład:
Testowane tutaj.
źródło
Rubinowy, 265 bajtów
Wersja @proudhaskeller, 269 bajtów
Wyjaśnienie
Pełna wersja:
Przykład
daje:
(Nie napisałem jeszcze skryptu konwersji).
źródło