Основные понятия о древовидных структурах

Основные определения

Структуры данных типа «дерево» исключительно широко используются в программной индустрии. В отличие от списковых структур деревья относятся к нелинейным структурам. Любое дерево состоит из элементов — узлов или вершин, которые по определенным правилам связаны друг с другом рёбрами. В списковых структурах за текущей вершиной (если она не последняя) всегда следует только одна вершина, тогда как в древовидных структурах таких вершин может быть несколько. Математически дерево рассматривается как частный случай графа, в котором отсутствуют замкнутые пути (циклы).

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

Рекурсивное определение дерева с базовым типом Т — это:

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

Отсюда видно, что в любом непустом дереве есть одна особая вершина — корень дерева, которая как бы определяет «начало» всего дерева. С другой стороны, существуют и вершины другого типа, не имеющие связанных с ними поддеревьев. Такие вершины называют терминальными или листьями.

Классификацию деревьев можно провести по разным признакам.

1. По числу возможных потомков у вершин различают двоичные (бинарные) или недвоичные (сильноветвящиеся) деревья.

Двоичное дерево: каждая вершина может иметь не более двух потомков.

Недвоичное дерево: вершины могут иметь любое число потомков.

2. Если в дереве важен порядок следования потомков, то такие деревья называют упорядоченными. Для них вводится понятие левый и правый потомок (для двоичных деревьев) или более левый/правый (для недвоичных деревьев). В этом смысле два следующих простейших упорядоченных дерева с одинаковыми элементами считаются разными:

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

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

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

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

• · добавление новой вершины
• · удаление некоторой вершины
• · обход всех вершин дерева
• · поиск заданной вершины