Numeracja drzewa binarnego

Numeracja preorder

k), a następnie prawe poddrzewo.

"W dół" drzewa idziemy lewymi krawędziami, a "w górę" prawymi.

Korzeń drzewa binarnego jest zawsze pierwszym odwiedzonym wierzchołkiem.

W algorytmie preorder dla każdego wierzchołka posiadającego potomków najpierw odwiedzane jest lewe poddrzewo (poddrzewo. którego korzeniem jest lewy potome Wierzchołek otrzyma najniższy numer z numerów nadanych węzłom w obu poddrzewach.

Numeracja inorder

Jeśli przez drzewo binarne będziemy przesuwać linię pionową od strony lewej do prawej, to kolejno napotykane wierzchołki będą posiadały numerację zgodną ze sposobe Dla każdego wierzchołka drzewa posiadającego potomków najpierw odwiedzane jest lewe poddrzewo, następnie sam wierzchołek i praw poddrzewo.

m numerowania inorder

Numeracja postorder

Charakterystyczną cechą numeracji postorder jest to, iż korzeń drzewa posiada ostatni numer.

Dla każdego wierzchołka odwiedzamy najpierw lewe poddrzewo, następnie prawe poddrzewo i na końcu sam wierzchołek. Otrzyma on najwyższy numer z nume ów nadanych wierzchołkom w obu poddrzewach.

Zwróć uwagę, iż otrzymane numery są jakby "lustrzanym odbiciem" numerów nadanych wierzchołkom przez algorytm preorder.