Drzewa BST - język C.

Archi · Post autor: **Archi** » 1 cze 2011, o 20:53

Mam do wykonania program o treści :

"Dokonano dwóch obiegów pewnego drzewa BST o różnych wartościach węzłów
całkowitych. Pierwszy obieg w porządku preorder a drugi w porządku postorder.
Następnie kolejno napotykane wartości umieszczono w dwóch tablicach.

Napisz program, który wczyta z dwóch plików dwie tablice liczb całkowitych
stanowiących domniemaną reprezentację drzewa zgodnie z ww. założeniami. Sprawdzić
czy z podanych danych uda się odtworzyć to drzewo. Jeżeli tak to zaproponuj
wizualizację drzewa."

Potrzebuje kilku wskazówek, bo nie wiem jak się za to zabrać. Wyobrażam to sobie tak:
Mając dane drzewo, zapisuje wartości węzłów do 2 tablic przez obieg preorder i postorder otrzymyjąc dwie tablice z tymi samymi danymi, tylko inaczej posortowane - do tej pory nie widzę wiekszych problemów.
Dalej nie dokońca rozumiem polecenie, prosiłbym o jakieś instrukcjie albo pseudokod.

paladin · Post autor: **paladin** » 2 cze 2011, o 18:50

Zaraz, ale przecież nie masz danego drzewa, tylko dwie tablice. Drzewo musisz dopiero skonstruować.

Jeśli to ma być drzewo z własnością BST, to zadanie nie jest trudne: pierwszy węzeł w kolejności preorder to korzeń drzewa, wszystkie mniejsze od niego to lewe poddrzewo, wszystkie większe to prawe poddrzewo. Wystarczy zatem tablicę "preorder" podzielić na dwie części i wywołać się na nich rekurencyjnie.
Tablica "postorder" nie jest w tym wypadku w ogóle potrzebna.

abc666 · Post autor: **abc666** » 2 cze 2011, o 21:20

Ja to zadanie rozumiem jeszcze tak, że np. tablica preorder i postorder mogą reprezentować różne drzewa tzn. że jest źle itp.. Ogólnie obie tablice powinny odtwarzać to samo drzewo.