Witam,
Mam do zrobienia zadanie w Javie.
Podawane są na wejście pokolei liczby w preorderze (lub postorderze), potem lecą liczby w inorderze i moim zadaniem jest wypisanie pokolei liczb w postorderze (lub preorderze, w zależności co było podane najpierw). Głowię się tylko jak stworzyć drzewo z liczb w preorderze i inorderze. W necie mogę tylko znaleźć jak odczytywać dane z drzewa metodami, nie mogłem znaleźć jak stworzyć drzewo z tych metod.
Jak to zrobić?
Pozdrawiam,
Gregor
Skoro to zadanie akademicko-szkolne, to proponuję pisać od zera zamiast używać bibliotek. Musisz sobie zaimplementować graf. Graf, jak pewnie wiesz, składa się z wierzchołków i łuków. W tym przypadku łuki nie są jakoś specjalnie potrzebne, więc wystarczy Ci zbiór wierzchołków, składających się z danych i referencji do dzieci (kolejnych wierzchołków). Ewentualnie możesz dorobić referencję zwrotną dzieci do rodziców.
Później to już będzie Twoja sprawa, jak sobie zaimplementujesz przechodzenie grafu i wypełnianie posortowanego drzewa, ale jestem pewny, że znajdziesz do tego gotowe rekurencyjne algorytmy w pseudokodzie. Nie mogę dać Ci gotowca, bo zadanie polega głównie na zrozumieniu rekurencji i tego, że w wywołaniu rekurencyjnym korzeniem "podgrafu" może być dowolny węzeł grafu wejściowego.