Rysoowanie binarnego drzewa wyszykiwań. porządki


(Imysz01) #1

Witam. Mam takie pytanie, dla przykładowych liczb: 2,6,3,9,4,7

Jak będzie się różnił wygląd drzewa dla porządku: in-order i pre-order ?

można w ogóle zadać takie pytanie ? czy przy rysowaniu nie uwzględnia się tego ?

pozdrawiam


([alex]) #2

Wygląd będzie taki sam, porządek przeglądania inny.

in-order - kolejność przechodzenia Lewy, Sam, Prawy lub Prawy, Sam, Lewy

pre-order - kolejność przechodzenia Sam, Lewy, Prawy lub Sam, Prawy, Lewy


(Imysz01) #3

okej dziękuje za odpowiedź o to mi chodziło.

Jeszcze jedno pytanie odnośnie drzewa czerwono czarnego.

Czy gdy rysuję drzewa od zera, to jest z podanego ciągu losowych liczb jest jakaś różnica między stworzeniem bst a drzewa czerwono czarnego, czy rysuje się je tak samo a później tylko koloryzuje odpowiednie węzły na black i red ?

pozdrawiam


([alex]) #4

Nie każde drzewo BST jest drzewem RB ale każde drzewo RB jest drzewem BST.

Nie zawsze istnieje jeden sposób na pokolorowanie drzewa RB, może zależeć od kolejności dodawania węzłów (w nielicznych przypadkach).