На этом шаге мы рассмотрим различные способы обхода бинарных деревьев.
Для того, чтобы просмотреть информационные поля всех вершин построенного дерева, необходимо совершить обход дерева или, другими словами, посетить каждую его вершину.
В случае, когда бинарное дерево пусто, оно обходится без выполнения каких либо действий. В противном случае существует несколько алгоритмов обхода:
(1) левосторонний (нисходящий) обход (КЛП):
- посетите корень дерева;
- обойдите левое поддерево;
- обойдите правое поддерево.
Например, применяя алгоритм левостороннего обхода к деревьям
посетим вершины в следующем порядке:
I. A, B, D, M, N, E, C; II. B, D, C, E, R;
(2) концевой (восходящий) обход (ЛПК):
- обойдите левое поддерево;
- обойдите правое поддерево;
- посетите корень дерева.
При таком алгоритме обход вершин бинарных деревьев I и II происходит в следующем порядке:
I. M, N, D, E, B, C, A; II. D, E, R, C, B.
Замечание. Концевой обход чаще всего применяется для уничтожения всех узлов в бинарном дереве, когда процесс уничтожения можно было бы описать так: чтобы уничтожить все узлы в бинарном дереве, необходимо уничтожить левое дочернее поддерево корневого узла, затем правое дочернее дерево корневого узла, а затем сам корневой узел.
(3) обратный (смешанный) обход (ЛКП):
- обойдите левое поддерево;
- посетите корень дерева;
- обойдите правое поддерево.
Применяя этот алгоритм к бинарным деревьям I и II, обойдём вершины в следующем порядке:
I. M, D, N, B, E, A, C; II. D, B, E, C, R.
На следующем шаге мы рассмотрим представления бинарных деревьев поиска на языке Haskell.
