Основы программирования — второй семестр 08-09; Михалкович С.С.; IV часть — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Admin (обсуждение | вклад) (→Произвольные деревья) |
Admin (обсуждение | вклад) (→Произвольные деревья) |
||
Строка 64: | Строка 64: | ||
</source> | </source> | ||
− | <source lang="Pascal"> | + | <source lang="Pascal">root:=CreateRandomTree(3,4); |
− | root:=CreateRandomTree(3,4); | ||
root:=NewNode(Random(100), root, nil); | root:=NewNode(Random(100), root, nil); | ||
</source> | </source> |
Версия 00:12, 25 марта 2009
Содержание
Деревья
Дерево как совокупность узлов, связанных ребрами (ветвями). Корень, листья дерева.
Примеры: главы и пункты книги, дерево разбора выражений.
Рекурсивное определение дерева
Бинарные деревья. Идеально сбалансированное, полное бинарное дерево.
Порядки обхода деревьев
- Инфиксный (левое, корень, правое)
- Префиксный (корень, левое, правое)
- Постфиксный (левое, правое, корень)
Задачи на бинарные деревья
Класс 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;