Wpis z mikrobloga

Skopiuj link

konto usunięte 16.01.2016, 20:38:11

#2137 skończyłem dzisiejsze #programowanie i wcale nie czuję że wiem coś więcej niż początkowo...
Ktoś podpowie jak zrobić drzewo danych w #js?

Cronox

AhoCorasick

16.01.2016, 20:44:00 via Android

Najłatwiej zrobić klasę (w js najłatwiej przy użyciu prototypów - nie jest to do końca klasa, ale nie ma to dla Ciebie znaczenia), która zawiera dwa pola - lewego i prawego syna (właściwie to przynajmniej trzy pola, bo jeszcze chcesz coś tam trzymać). Każdy syn jest znowu drzewem zawierającym lewego i prawego syna. W ten sposób otrzymujesz drzewo binarne (każdy węzeł o stopniu max dwa). Każde drzewo o stopniu większym niż dwa

konto usunięte

e.....3

konto usunięte 16.01.2016, 20:45:29

@AhoCorasick:
function Tree (val) {
this.value = val
this.children = []
}
boom ok
I teraz jak zrobić szukanie?

AhoCorasick

16.01.2016, 20:47:26 via Android

szukanie czego? zazwyczaj najłatwiej użyć algorytmu dfs używając rekurencyjnych funkcji - wchodzisz do węzła, jak znalazłeś to co chciałeś to zwijasz stos. jak nie to wchodzisz rekurencyjnie do każdego dziecka.

konto usunięte

e.....3

konto usunięte 16.01.2016, 20:55:51

@AhoCorasick:
Problem mam taki, znajdź najbliższy wspólny wierzchołek dla "bD" i "aC", no wiadomo "A"

var root = new Tree("A")
root.children.push(new Tree("aB"))
root.children.push(new Tree("aC"))
root.children[0].push(new Tree("bD"))

Zatem brakuje mi jakiegoś find() tylko się gubię jak zrobić tę rekurencję. Możesz mi podrzucić jakąś literaturę pod to?

AhoCorasick

16.01.2016, 21:03:33 via Android

problem nazywa sie najniższy wspólny przodek. Istnieje tysiąc algorytmów w zależności jakie masz limity czasowe. Tak super najłatwiej to zapamiętać na jakim poziomie (licząc od góry) jest każdy węzeł. Następnie bierzesz węzeł znajdujący się bliżej korzenia, a dla drugiego węzła idziesz kilka razy w górę, żeby mieć przodka na poziomie tego drugiego węzła. potem z każdego węzła idziesz o jeden do góry aż trafisz na ten sam węzeł. złożoność obliczeniowa i czasowa