Основы программирования — второй семестр 08-09; Михалкович С.С.; IV часть

Лекция 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;