Содержание

• Содержание
  • Способы представления деревьев
    • Представление корневого дерева
    • Представление бинарного дерева
  • Примеры использования деревьев
    • Дерево двоичного поиска
    • Дерево частотного словаря
    • Дерево синтаксического анализа
• Примечания

Способы представления деревьев

Поскольку любое дерево является графом, то его можно задавать любым из способов, перечисленных в п. «Способы представления графов». Однако существуют и специальные способы представления, предназначенные только для деревьев. Мы рассмотрим только два наиболее распространённых частных случая.

Представление корневого дерева

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

Разумеется, в общем случае значение переменной S (количество потомков) может достигать N-1 (N — количество всех вершин в дереве). Однако ясно, что в такой ситуации особого смысла в динамической древесной структуре нет: экономии памяти не получается. Гораздо лучше, если у всех вершин примерно одинаковое и заранее известное количество потомков.

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

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

Примеры использования деревьев

Здесь мы ограничимся только примерами использования бинарных корневых деревьев: именно такой вид графа чаще всего применяется в программировании.

Дерево двоичного поиска

Дерево двоичного поиска для множества чисел S — это размеченное бинарное дерево, каждой вершине которого сопоставлено число из множества S, причём все пометки удовлетворяют следующим условиям:

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

Если выражаться простым языком, то структура дерева двоичного поиска подчиняется простому правилу: «если больше — направо, если меньше — налево».

Например, для набора чисел 7, 3, 5, 2, 8, 1, 6, 10, 9, 4, 11 получится такое дерево (см. рис. 11.14).

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

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

Рис. 11.14.  Дерево двоичного поиска

Дерево частотного словаря

Дерево частотного словаря — это результат построения дерева двоичного поиска не для чисел, а для слов некоторого текста. Генерирование дерева частотного словаря полезно при подсчёте количества вхождений каждого слова в некоторый текст.

Приведём описание структуры этого дерева:

Дерево синтаксического анализа

Дерево синтаксического анализа арифметического выражения — это бинарное дерево, листьями которого служат операнды, а остальными вершинами — операции, причём уровень вершины соответствует приоритету выполнения операции: чем ближе к листьям, тем приоритет выше.

Например, на рис. 11.15 изображено дерево синтаксического анализа для выражения ((a / (b + c)) + (x * (y - z))).

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

Рис. 11.15.  Дерево синтаксического анализа

Примечания