Строение ДСД: набор узлов, объединенных с помощью ссылок. Вид узла: Данные+ссылки на другие узлы. Типы структур: Списки, деревья, графы.
Дерево – это структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг), причем в каждый узел (кроме корневого) ведет ровно одна дуга.
Корень – это начальный узел дерева.
Лист – это узел, из которого не выходит ни одной дуги.
Основные понятия:
Предок узла x – это узел, из которого существует путь по стрелкам в узел x.
Потомок узла x – это узел, в который существует путь по стрелкам из узла x.
Родитель узла x – это узел, из которого существует дуга непосредственно в узел x.
Сын узла x – это узел, в который существует дуга непосредственно из узла x.
Брат узла x (sibling) – это узел, у которого тот же родитель, что и у узла x.
Высота дерева – это наибольшее расстояние от корня до листа (количество дуг).
Ключ – это характеристика узла, по которой выполняется поиск (чаще всего – одно из полей структуры).
Как искать ключ, равный x:
1)если дерево пустое, ключ не найден;
2)если ключ узла равен x, то стоп.
3)если ключ узла меньше x, то искать x в левом поддереве;
если ключ узла больше x, то искать x в правом поддереве
Рекурсивное определение:
1.Пустая структура – это дерево.
2.Дерево – это корень и несколько связанных с ним деревьев.
Двоичное (бинарное) дерево – это дерево, в котором каждый узел имеет не более двух сыновей.
1.Пустая структура – это двоичное дерево.
2.Двоичное дерево – это корень и два связанных с ним двоичных дерева (левое и правое поддеревья).
Применение:
1)поиск данных в специально построенных деревьях
(базы данных);
2)сортировка данных;
3)вычисление арифметических выражений;
4)кодирование (метод Хаффмана).
type PNode = ^Node; { указатель на узел }
Node = record
data: integer; { полезные данные }
left, right: PNode; { ссылки на левого и правого сыновей }
end;
Обход дерева – это перечисление всех узлов в определенном порядке.(ЛКП, ПКЛ, КЛП, ЛПК)
{Процедура LKP – обход дерева в порядке ЛКП (левый – корень – правый)
Вход: Tree - адрес корня }
procedure LKP(Tree: PNode);
begin
if Tree = nil then Exit;
LKP(Tree^.left);
write(' ', Tree^.data);
LKP(Tree^.right);
end;
23.
