4. Деревья

Конечное корневое дерево Т формально определяется как непустое конечное множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на 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 поддерева, также существует различие между левым и правым поддеревьями.

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

Почти все машинные представления деревьев основаны на связанном распределении данных. Каждый узел состоит из поля 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. Представление леса в виде бинарного дерева