Ориентированный граф (орграф) g — это упорядоченная пара G: = (V,A), для которой выполнены следующие условия
Деревья
Ориентированный граф (орграф) G — это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:
- V это множество вершин или узлов,
- A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.
Деревья
Дуга — это упорядоченная пара вершин (v,w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v w ведёт от вершины v к вершине w.
Деревья
Деревом называется орграф не содержащий циклы для которого :
1. Существует узел, в которой не входит не одной дуги. Этот узел называется корнем.
2. В каждую вершину, кроме корня, входит одна дуга.
Деревья
С точки зрения представления в памяти важно различать два типа деревьев: бинарные и сильноветвящиеся.
Деревья
Степенью узла в дереве называется количество дуг, которое из него выходит.
Степень дерева равна максимальной степени узла, входящего в дерево.
Cтепень узла бинарного дерева не превышает числа два. При этом листьями в дереве являются вершины, имеющие степень ноль.
Бинарные деревья
Бинарные деревья
Бинарные деревья
Строго бинарное дерево состоит только из узлов, имеющих степень два или степень ноль.
Нестрого бинарное дерево содержит узлы со степенью равной одному.
Бинарные деревья
Бинарные деревья
Бинарные деревья
Type
PTree = ^TTree;
TTree = record
Item: T; {элемент дерева}
Left, Right: PTree;
{указатели на поддеревья}
end;
где Left, Right равны nil, если соответствующие поддеревья пусты
Бинарные деревья
Пусть мы имеем дело с полным двоичным деревом, состоящим из n уровней.
Можно организовать такое хранение дерева в массиве Value: array[1..N] of T, что:
Value[1] – корень дерева;
Value[2*i] – левый сын вершины Value[i];
Value[2*i+1] – правый сын вершины Value[i].
Бинарные деревья
Адрес любой вершины в массиве вычисляется как
адрес = 2к-1+i-1,
где k-номер уровня вершины, i- номер на уровне k в полном бинарном дереве.
Адрес корня будет равен единице.
Для любой вершины можно вычислить адреса левого и правого потомков
адрес_L = 2к+2(i-1)
адрес_R = 2к+2(i-1)+1
Бинарные деревья
Прохождение бинарных деревьев
Пошаговый перебор элементов дерева по связям между предками-узлами и потомками-узлами называется обходом дерева
Прохождение бинарных деревьев
Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk),
а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk).
Прохождение бинарных деревьев
Существует также симметричный обход, при котором посещается сначало левое поддерево, затем узел, затем - правое поддерево,
и обход в ширину, при котором узлы просматриваются уровень за уровнем
(N-й уровень дерева - множество узлов с высотой N).
Каждый уровень обходится слева направо.
Прохождение бинарных деревьев
Первые три способа обхода рекурсивно можно определить следующим образом:
если дерево Tree является пустым деревом, то в список обхода заносится пустая запись
если дерево Tree состоит из одной вершины, то в список обхода записывается эта вершина;
если Tree дерево с корнем n поддеревьями Тrее1, Тrее2, …, Treek ,…
то :
Прохождение бинарных деревьев
при прохождении в прямом порядке сначала посещается корень и, затем в прямом порядке вершины поддерева
Тrее1
далее в прямом порядке вершины поддерева Тrее2 и т. д.
последними в прямом порядке посещаются вершины поддерева Тrееk
Прохождение бинарных деревьев
те, прямой порядок прохождения бинарного дерева можно определить следующим образом:
попасть в корень
пройти в прямом порядке левое поддерево
пройти в прямом порядке правое поддерево
Прохождение бинарных деревьев
Прохождение бинарных деревьев
procedure PreOrder(n: вершина);
{Обход дерева в прямом порядке}
begin
Занести в список обхода вершину n;
for для каждого потомка s вершины n в порядке слева направо do
PreOrder(s);
end;
Прохождение бинарных деревьев
при прохождении в обратном порядке сначала посещаются в обратном порядке вершины поддерева Тrее1
далее последовательно в обратном порядке посещаются вершины поддеревьев Тrее2 ..., Treek
последним посещается корень n;
Прохождение бинарных деревьев
Прохождение бинарного дерева в обратном порядке:
пройти в обратном порядке левое поддерево
пройти в обратном порядке правое поддерево
попасть в корень
Прохождение бинарных деревьев
Прохождение бинарных деревьев
procedure LastOrder(n: вершина);
{Обход дерева в обратном порядке}
begin
for для каждого потомка s вершины n в порядке слева направо do LastOrder(s);
Занести в список обхода вершину n;
end;
Прохождение бинарных деревьев
при прохождении в симметричном порядке сначала посещаются в симметричном порядке вершины поддерева Тrее1,
далее корень n,
затем последовательно в симметричном порядке вершины поддеревьев Тrее2 ..., Treek.
Прохождение бинарных деревьев
Симметричный порядок:
пройти в симметричном порядке левое поддерево
попасть в корень
пройти в симметричном порядке правое поддерево
Прохождение бинарных деревьев
Прохождение бинарных деревьев
procedure InOrder(n: вершина);
{Обход дерева в симметричном порядке}
begin
if n — лист then
begin
занести в список обхода узел n;
end
else
begin
InOrder(самый левый потомок вершины n);
Занести в список обхода вершину n;
for для каждого потомка s вершины n,
исключая самый левый,в порядке слева
направо do InOrder(s);
end;
end;
Сортировка с прохождением бинарного дерева
Дерево строится по следующим принципам: в качестве корня создается узел, в который записывается первый элемент массива.
Для каждого очередного элемента создается новый лист. Если элемент меньше значения в текущем узле, то для него выбирается левое поддерево, если больше или равен правое.
Сортировка с прохождением бинарного дерева
Сортировка с прохождением бинарного дерева
страница 1
скачать
Другие похожие работы: