Деревья

Стеки и очереди

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

В обоих случаях операции включения и исключения производятся только на концах последовательности [11].

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

Правило работы со стеком: «Первым пришел — последним ушел».

Очередь — это последовательность, в которой все включения производятся на одном конце списка (в конце очереди), в то время как все исключения производятся на другом (в начале очереди).

Правило работы с очередью: «Первым пришел — первым ушел».

Стеки и очереди имеют важное значение в автоматизации работы с информационными структурами.

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

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

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

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

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

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

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

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

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

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

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

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

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