Структуры данных. Деревья - 9 стр.

UptoLike

Составители:

Рубрика:

Далее будем иметь дело только с двоичными деревьями, поэтому термин

“дерево” будет означать двоичное дерево.

3. ОСНОВНЫЕ ОПЕРАЦИИ С ДВОИЧНЫМИ ДЕРЕВЬЯМИ

3.1. Обход дерева

Наиболее распространенная задача обработки древовидных структур – вы-

полнение некоторой определенной операции над каждым элементом дерева. При

этом происходит “посещение” всех вершин, т.е. обход дерева. При обходе

каж-

дый узел проходится, по меньшей мере, один раз, а, вообще говоря, три раза.

Полное прохождение дерева дает линейную расстановку узлов. Если, обходя де-

рево, обрабатывать вершины при первой встрече, то ( см. рис. 4 б) ) получим по-

следовательность A, B, D, E, C, F ; если при второй встрече, то получим D, B, E,

A, C, F ; если при третьей встрече, то получим D, E, B, F, C, A.

Эти

три способа обхода называются соответственно

– обходом сверху вниз (в прямом порядке, префиксным обходом, preorder);

– обходом слева направо (в обратном порядке, инфиксным обходом,

inorder);

– обходом снизу вверх (в концевом порядке, постфиксным обходом,

postorder или endorder).