Основы программирования — второй семестр 08-09; Михалкович С.С.; IV часть — различия между версиями
Admin (обсуждение | вклад) (→Произвольные деревья) |
Juliet (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
[[Категория:Конспекты]] | [[Категория:Конспекты]] | ||
+ | |||
+ | <small>Лекция 8</small> | ||
+ | |||
== Деревья == | == Деревья == | ||
+ | '''Деревом''' назовем совокупность узлов, называемых '''''вершинами''''' дерева, соединенных между собой ребрами, называемыми '''''ветвями'''''. <br /> | ||
+ | <здесь будет рисунок дерева> <br /> | ||
+ | Количество уровней называется '''''глубиной''''' дерева. <br /> | ||
+ | Каждая вершина нижнего уровня соединяется ровно с одной вершиной предыдущего уровня. | ||
+ | |||
+ | Единственная вершина на уровне <tt>0</tt> называется '''корнем''' дерева. <br /> | ||
+ | Она не имеет вершин-предков. | ||
+ | |||
+ | Вершины, не имеющие потомков, называют '''листьями''' дерева, а совокупность всех листьев образует '''крону''' дерева. | ||
+ | |||
+ | ''<u>Примеры</u>.'' | ||
+ | |||
Дерево как совокупность узлов, связанных ребрами (ветвями). | Дерево как совокупность узлов, связанных ребрами (ветвями). |
Версия 22:06, 28 марта 2009
Лекция 8
Содержание
Деревья
Деревом назовем совокупность узлов, называемых вершинами дерева, соединенных между собой ребрами, называемыми ветвями.
<здесь будет рисунок дерева>
Количество уровней называется глубиной дерева.
Каждая вершина нижнего уровня соединяется ровно с одной вершиной предыдущего уровня.
Единственная вершина на уровне 0 называется корнем дерева.
Она не имеет вершин-предков.
Вершины, не имеющие потомков, называют листьями дерева, а совокупность всех листьев образует крону дерева.
Примеры.
Дерево как совокупность узлов, связанных ребрами (ветвями).
Корень, листья дерева.
Примеры: главы и пункты книги, дерево разбора выражений.
Рекурсивное определение дерева
Бинарные деревья. Идеально сбалансированное, полное бинарное дерево.
Порядки обхода деревьев
- Инфиксный (левое, корень, правое)
- Префиксный (корень, левое, правое)
- Постфиксный (левое, правое, корень)
Задачи на бинарные деревья
Класс TreeNode<T>
Создание идеально сбалансированного дерева.
Вывод узлов дерева в инфиксном, префиксном, постфиксном порядке.
Связь деревьев и рекурсии.
Определение глубины дерева.
Количество листов в дереве.
Поиск элемента в дереве.
Бинарные деревья поиска
Определение БДП.
Добавление в БДП. Инвариантность БДП относительно операции добавления.
Оценка количества операций при добавлении. Худший случай.
Сортировка деревом. Асимптотическая сложность алгоритма.
Поиск элемента в БДП.
Произвольные деревья
TreeNode = class
data: integer;
leftChild, rightSibling: TreeNode;
end;
function CreateRandomTree(n: integer; m: integer): TreeNode;
// n - количество сыновей, m - количество уровней
begin
Result := nil;
if m=0 then exit;
for var i:=1 to n do
Result := new TreeNode(Random(100), CreateRandomTree(Random(1,5), m-1), Result)
end;
root := CreateRandomTree(3,4);
root := new TreeNode(Random(100), root, nil);
procedure PrintTree(r: TreeNode);
begin
while r<>nil do
begin
write(r.data,' ');
PrintTree(r.leftChild);
r := r.rightSibling;
end
end;