Основы программирования — второй семестр 08-09; Михалкович С.С.; IV часть
Материал из Вики ИТ мехмата ЮФУ
Содержание
Деревья
Дерево как совокупность узлов, связанных ребрами (ветвями). Корень, листья дерева.
Примеры: главы и пункты книги, дерево разбора выражений.
Рекурсивное определение дерева
Бинарные деревья. Идеально сбалансированное, полное бинарное дерево.
Порядки обхода деревьев
- Инфиксный (левое, корень, правое)
- Префиксный (корень, левое, правое)
- Постфиксный (левое, правое, корень)
Задачи на бинарные деревья
Класс TreeNode<T>
Создание идеально сбалансированного дерева.
Вывод узлов дерева в инфиксном, префиксном, постфиксном порядке.
Связь деревьев и рекурсии.
Определение глубины дерева.
Количество листов в дереве.
Поиск элемента в дереве.
Бинарные деревья поиска
Определение БДП.
Добавление в БДП. Инвариантность БДП относительно операции добавления.
Оценка количества операций при добавлении. Худший случай.
Сортировка деревом. Асимптотическая сложность алгоритма.
Поиск элемента в БДП.
Произвольные деревья
TreeNode = record
data: integer;
leftChild, rightSibling: pTreeNode;
end;
function CreateRandomTree(n: integer; m: integer): PTreeNode;
// n - количество сыновей, m - количество уровней
begin
Result:=nil;
if m=0 then exit;
for i:=1 to n do
Result:=NewNode(Random(100), CreateRandomTree(Random(5)+1, m-1), Result)
end;
root:=CreateRandomTree(3,4);
root:=NewNode(Random(100), root, nil);
procedure PrintTree(r: pTreeNode);
begin
while r<>nil do
begin
write(r.data,' ');
PrintTree(r.leftChild);
r:=r.rightSibling;
end
end;