Организация связанного распределения на основе стеков и очередей

Связанное распределение стека такое же легкое, как и последовательное распределение. Сохраним t в качестве указателя ячейки, являющейся вершиной стека, и используем поле LINK элемента стека для указания элемента, находящегося под данным элементом в стеке.

Нижний элемент стека имеет пустой указатель L в поле LINK, и t = L означает пустой стек. Итак, имеем:

 

S Ü X       new(l); {заводится ячейка памяти}
INFO(l) X
LINK(l) t {t — вершина стека}
t l

X Ü S       if t = L then underflow
  else X INFO(t)

              t LINK(t)

 

Для очередей связанного распределения справедливо:

Q Ü X       new(l);

INFO(l) X

LINK(l) f

 {организация цикла}

LINK(r) l
r l

X Ü Q       if f = L then underflow
  else X INFO(f)

              LINK(r) LINK(f)

Деревья

 

Конечное корневое дерево Т формально определяется как непустое конечное множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на m ³ 0 поддеревьев Т₁, Т₂, …, Т _m.

 Узлы, не имеющие поддеревьев, называют листьями, остальные узлы называются внутренними узлами [3]. 

 

Рис. 2.7. Дерево с 11 узлами

 

Узлы D, E, F, H, J, K — листья, А — корень, остальные — внутренние.

Посредством деревьев представляются иерархические структуры, поэтому они являются наиболее важными нелинейными структурами данных.

В описании соотношений между узлами дерева будем использовать терминологию генеалогических деревьев. Т.е. говорим, что в дереве (или поддереве) все узлы, являются потомками его корня, и наоборот, корень есть предок всех своих потомков. Далее корень будем именовать отцом корней его поддеревьев, которые в свою очередь будем называть сыновьями корня. Например, на рис. 2.7 узел А является отцом узлов B, G, I; J и K — сыновья I, а C, E и F — братья и т.д. 

Все рассматриваемые деревья упорядочены, т.е. для них важен относительный порядок поддеревьев каждого узла. Т.е. деревья

 

 

считаются различными.

 

Определим лес как упорядоченное множество деревьев.

Важной разновидностью деревьев является класс бинарных деревьев. Бинарное дерево Т либо пустое, либо состоит из выделенного узла, называемого корнем, и двух бинарных поддеревьев: левого T _l и правого T _r.

Бинарные деревья, вообще говоря, не являются подмножеством множества деревьев, они полностью отличаются своей структурой, поскольку

 

есть разные бинарные деревья.

Различие между бинарным деревом и деревом состоит в том, что не бинарное дерево не может быть пустым, и каждый узел не бинарного дерева может иметь произвольное число поддеревьев. В то же время бинарное дерево может быть пустым и каждая его вершина может иметь 0, 1 или 2 поддерева, также существует различие между левым и правым поддеревьями.

 

 

Представление деревьев

 

Почти все машинные представления деревьев основаны на связанном распределении данных. Каждый узел состоит из поля INFO и полей для указателей (рис. 2.8). На рис. 2.8 показаны связи от потомков к предку.

Такая операция встречается редко, чаще требуется опуститься по дереву от предков к потомкам. Представление дерева (или леса) с использованием указателей, ведущих от предков к потомкам, довольно сложно из-за узла отца, который может иметь произвольно много сыновей. Другими словами, при таком представлении узлы должны различаться по размеру, что неудобно.

 

   

Рис. 2.8. Дерево, представленное с помощью узлов с полем INFO и указателем FATHER

 

Один из путей обхода этой трудности состоит в построении соответствия между деревьями и бинарными деревьям, поскольку бинарные деревья легко представить узлами фиксированного размера. Каждый узел при этом имеет три поля: LEFT - указатель местоположения корня левого поддерева, INFO - информационная часть содержимого узла и RIGHT - указатель местоположения корня правого поддерева.

 

Рис. 2.9. Представление бинарного дерева с помощью узлов с тремя полями LEFT, INFO, RIGHT

 

Следующее представление дерева (или леса) в виде бинарного дерева будем называть естественным соответствием между деревьями и бинарными деревьями. Оно касается того, что в поле LEFT указывается самый левый сын данного узла, а в поле RIGHT — указывается следующий брат данного узла. Например, лес, показанный на рис. 2.10 преобразуется в бинарное дерево, показанное на рис. 2.11 следующим образом:

 

Рис. 2.10. Лес

 

Рис. 2.11. Представление леса в виде бинарного дерева

 

Прохождение деревьев, леса

Во многих приложениях необходимо пройти лес, заходя в узлы (т.е. обрабатывая их) некоторым систематическим образом. Посещение узла может быть связано с простой операцией, такой как печать содержимого узла, или со сложной, такой как вычисление функции. Единственное, что мы будет предполагать — это то, что при посещении узла структура дерева не меняется.

Основными способами прохождения дерева являются:

 

· в глубину (сверху вниз);

· в ширину (горизонтальный порядок);

· снизу вверх;

· в симметричном порядке (для бинарных деревьев).

 

При прохождении в глубину (прохождение в прямом порядке) узлы леса проходятся в соответствии со следующей рекурсивной процедурой:

 

1) посетить корень первого дерева;

2) пройти в глубину поддеревья первого дерева (если оно есть);

3) пройти в глубину оставшиеся деревья, если они есть.

 

Например, для леса, показанного на рис. 2.10, узлы будут проходиться в следующем порядке: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S.

Для бинарных деревьев эта процедура упрощается и выглядит следующим образом:

 

1) посетить корень;

2) пройти в глубину левое поддерево;

3) пройти в глубину правое поддерево.

 

Заметим, что прохождение леса в глубину в точности такое же, как и прохождение в глубину бинарного дерева, являющегося его представлением. Именно этот факт и делает указанное выше соответствие «естественным».

Прохождение снизу вверх (обратный порядок или концевой порядок) осуществляется согласно следующей рекурсивной процедуре:

1) пройти снизу вверх поддеревья первого дерева, если они есть;

2) посетить корень первого дерева;

3) пройти снизу вверх оставшиеся деревья, если они есть.

При этом порядке прохождения узлы леса рис. 2.10 проходятся в следующем порядке:

 

         B, D, E, F, C, G, J, I, K, L, H, A, O, P, N, R, Q, S, M.

 

Рекурсивная процедура прохождения снизу вверх применительно к бинарным деревьям имеет следующий вид:

 

1) пройти снизу вверх левое поддерево;

2) пройти снизу вверх правое поддерево;

3) посетить корень.

 

        F, E, D, K, J, L, I, H, G, C, B, P, O, R, S, Q, N, M, A.

 

Симметричный порядок для бинарных деревьев определятся рекурсивно следующим образом:

 

1) пройти в симметричном порядке левое поддерево;

2) посетить корень;

3) пройти в симметричном порядке правое поддерево.

 

Такой способ прохождения известен как лексикографический порядок или внутренний прядок.

Прохождение дерева снизу вверх эквивалентно прохождению в симметричном порядке бинарного дерева, соответствующего ему.

Последний способ прохождения дерева — горизонтальный порядок или в ширину. При таком способе узлы дерева проходятся слева направо уровень за уровнем от корня вниз. Т.о. узлы леса рис. 2.10 будут проходиться в следующем порядке:

 

A, M, B, C, G, H, N, Q, S, D, E, F, I, L, O, P, R, J, K.

 

Прямой порядок: A B D G C E H I F

Симметричный порядок: D G B A H E I C F

Обратный порядок: G D B H I E F C A

                    Прямой порядок: A B C E I F J D G H K L

                    Симметричный порядок: E I C F J B G D K H L A

                    Обратный порядок: I E J F C G K L H D B A

 

        Рис. 2.12. Прохождение бинарных деревьев

Многие алгоритмы и процессы, использующие бинарные деревья, распадаются на 2 фазы. В первой фазе строится бинарное дерево, а во второй оно проходится.

В качестве примера рассмотрим применение бинарного дерева для сортировки чисел. Входной файл содержит список чисел, нужно распечатать числа в возрастающем порядке. По мере того, как мы считываем число, оно помещается в бинарное дерево. Все совпадающие значения также помещаются в дерево. При сравнении числа с содержимым узлов дерева выбирается тот узел, у которого еще не занята правая или левая ветвь, которая в свою очередь выбирается таким образом, что слева записывается меньшее число, чем число в узле, а справа записывается большее число, чем в узле или

равное ему. Таким образом, если входной список равен 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5, то будет построено бинарное дерево, показанное на рис. 2.13.

Рис. 2.13. Бинарное дерево, построенное для сортировки

 

Такое бинарное дерево обладает тем свойством, что содержимое каждого узла в левом поддереве узла n меньше, чем содержимое узла n, а содержимое каждого узла в правом поддереве узла n больше или равно содержимому узла n. Таким образом, если дерево проходится в симметричном порядке (левое поддерево, корень, правое поддерево), то числа печатаются в возрастающем порядке, т.е. 3, 4, 4, 5, 5, 7, 9, 14, 14, 15, 16, 17, 18, 20.

Алгебраическая формула или логическая функция также могут быть представлены бинарным деревом. Например, на рис. 2.14 показано дерево, соответствующее арифметическому выражению a – b (c / d + e / f).

 

Рис. 2.14. Представление формулы в виде дерева

 

Используя дерево, легко выполнить переход от инфиксной (обычной) формы записи арифметического выражения (логической функции) к постфиксной (снизу вверх) и к префиксной (сверху вниз).

Например, A + B — инфиксная запись (левое поддерево, корень, правое поддерево);

     A B + — постфиксная запись (левое поддерево, правое поддерево, корень),

+ A B — префиксная запись (корень, левое поддерево, правое поддерево).

Итак, рис. 2.14 позволяет записать

- сверху вниз – a * b + / c d / e f (префиксная запись)

- снизу вверх a b c d / e f / + * – (постфиксная запись)

Такие формы представления позволяют оперировать без скобок, сохраняя правильность выполнения операций.

 

Высота дерева

Деревья используются не только как способ представления структур данных, но так же как средство для анализа поведения алгоритмов.

В этой связи возникает потребность в количественных измерениях различных характеристик деревьев и, в частности, бинарных деревьев.

Наиболее важные количественные характеристики деревьев связаны с уровнями узлов. Уровень p определяется рекурсивно и считается равным 0, если р — корень дерева Т; в противном случае уровень р определяется как 1+ уровень (FATHER (p)). Понятие уровня дает нам возможность просто определить высоту дерева Т: .

Высота дерева есть максимальное число ребер, образующих путь от корня к листу дерева.

Рис. 2.13. Бинарное дерево с длиной внешних путей, равной 21, а внутренних равной 9, h = 4

 

Прошитые бинарные деревья

Для прохождения бинарного дерева часто используют стек. Рассмотрим другой подход. Предположим, что верхний элемент стека указывает на тот узел, левое поддерево которого мы только что прошли. Предположим, что узел с правым поддеревом содержит вместо пустого указателя указатель на узел, который находится на вершине стека в данной точке алгоритма. Тогда не будет больше нужды в стеке, поскольку узел будет непосредственно указывать на своего преемника при проходе в симметричном порядке. Такой указатель называется нитью. На рис. 2.14 показано бинарное дерево со связями-нитями, заменяющими пустые указатели в узлах с пустыми правыми поддеревьями. Нити нарисованы штриховыми линиями. Такие деревья называются бинарными деревьями, симметрично прошитыми справа.

Рис. 2.14. Симметрично прошитое справа бинарное дерево

Алгоритмы на графах