лк_11нед_1_курс_АиП

Контрольные вопросы – в конце лекции.

Бинарные деревья

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

Деревья наилучшим образом приспособлены для решения задач искусственного интеллекта и синтаксического анализа. Деревья в информатике принято рисовать перевернутыми – растущими вниз.

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

Древовидная структура (дерево) определяется следующим образом: дерево (tree) с базовым типом Т– это:

• либо пустая структура;

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

Бинарное дерево – если с узлом связаны не более двух поддеревьев.

В дальнейшем мы будем рассматривать только бинарные деревья. Бинарное дерево изображено на рис.1.

Терминология, применяемая для описания деревьев:

узел(node) – это точка, где может возникнуть ветвь. На рис.1 узлы – это, например, 70 и 200 и т.д;

корень (root)– “верхний” узел дерева. Для дерева на рис.1 это узел 100;

ветвь (brunch)–отрезок, описывающий связь между двумя узлами;

лист (leaf)– узел, из которого не выходят ветви, т.е. не имеющий поддеревьев. На рис.1 это узлы 10, 90, 58, 65, 170, 210;

родительским (parent)– называется узел, который находится непосредственнонаддругим узлом;

дочерним (child)– называется узел, который находится непосредственноподдругим узлом;

предки данного узла – это все узлы на пути вверх от данного узла до корня. Например, предками узла 60 являются узлы 55, 50, 70, 100;

потомки – все узлы, расположенные ниже данного. Для узла 55 потомками являются узлы 60, 58, 65;

внутренний узел(internal node) – узел, не являющийся листом;

порядок узла(node degree) – количество его дочерних узлов;

глубина(depth)узла – количество его предков плюс единица;

глубина (высота) дерева –максимальная глубина всех узлов;

длина пути к узлу– количество ветвей, которые нужно пройти, чтобы дойди от корня к данному узлу;

длина пути дерева(длина внутреннего пути) – сумма длин путей всех его узлов.

В командной строке Windows вы можете использовать tree /F для просмотра дерева текущей папки и всех нисходящих файлов и папок.

tree C:\ | more - отобразить структуру каталогов от корневого каталога диска C: в постраничном режиме вывода на экран.

Основные операции с бинарными деревьями

Узел бинарного дерева

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

Узел дерева можно описать как переменную с фиксированной структурой, содержащую информационную часть (например, целое число) и две ссылки, указывающие на левое и правое поддеревья данного узла. Для этого подойдет тип – запись (record). Ссылка на пустое дерево должна быть равна nil.

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

Описание узла дерева может выглядеть так:

Type

PTree= ^TTree; // указатель на узел дерева

TTree = record

Inf :integer; // информационная часть (тип может быть любой)

Left, Right :PTree; // указатели на левое и правое поддеревья

end;

Обход бинарного дерева.

Для двоичных деревьев (и деревьев вообще) вводиться важная категория алгоритмов:

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

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

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

“Обработать корень” – действия, выполняемые над узлом.

Порядки обхода

Сверху вниз (PreOrder):

обработать корень;

обход левого поддерева;

обход правого поддерева;

Слева направо (InOrder):

обход левого поддерева;

обработать корень;

обход правого поддерева;

Снизу вверх(PosOrder):

обход левого поддерева;

обход правого поддерева;

обработать корень.

Для дерева на рис.1 три способа обхода дают следующий результат:

Эти три метода легко представить в виде рекурсивных процедур.

Контрольные вопросы

1. Чем определяется бинарная структура?

2. Что называется бинарным деревом?

3. Дайте определения понятиям узел, корень, ветвь, лист, внутренний узел.

4. Что называется глубиной дерева?

5. Перечислите алгоритмы обходов бинарных деревьев и поясните, в чем они состоят.