Правила форума
Лекция №12.4: Алгоритмы на графах и деревьяхСодержание
Обход в ширину
Последовательность обхода
- Пометить вершину 0–го уровня (корень дерева).
- Пометить все вершины 1–го уровня.
- Пометить все вершины 2–го уровня.
- ...
/12%2D4.gif)
Рис. 12.4. Последовательность нумерации вершин при синтаксическом обходе дерева
Замечание: Этот алгоритм может быть естественным образом распространён и на случай произвольного корневого дерева.
Алгоритм WideOrder
- Занести в очередь1 корень дерева.
- Пока очередь не станет пустой, повторять следующие действия:
- удалить первый элемент из головы очереди;
- добавить в хвост очереди всех потомков удалённой вершины.
Реализация
Для простоты реализации вновь пополним структуру дерева полем next : ukaz, которое будет служить для связки очереди:
head := root;
tail := root;
k := 0;
repeat
tail^.next := head^.left;
if head^.left <> nil then
tail := tail^.next;
tail^.next := head^.right;
if head^.right <> nil then
tail := tail^.next;
Inc(k);
head^.znachenie := k; {можно Write(head^.znachenie);}
head := head^.next
until head = nil;
tail := root;
k := 0;
repeat
tail^.next := head^.left;
if head^.left <> nil then
tail := tail^.next;
tail^.next := head^.right;
if head^.right <> nil then
tail := tail^.next;
Inc(k);
head^.znachenie := k; {можно Write(head^.znachenie);}
head := head^.next
until head = nil;
/12%2D5.gif)
Рис. 12.5. Последовательность нумерации вершин при обходе дерева в ширину
Древесная сортировка
Задача. Упорядочить заданный набор (возможно, с повторениями) некоторых элементов (чисел, слов, т.п.).
Алгоритм TreeSort
- Для сортируемого множества элементов построить дерево двоичного поиска:
- первый элемент занести в корень дерева;
- для всех остальных элементов: начать проверку с корня; двигаться влево или вправо (в зависимости от результата сравнения с текущей вершиной дерева) до тех пор, пока не встретится такой же элемент, либо пока не встретится nil. Во втором случае нужно создать новый лист в дереве, куда и будет записано значение нового элемента.
- Совершить синтаксический обход построенного дерева, печатая каждую встреченную вершину столько раз, сколько было её вхождений в сортируемый набор.
Реализация
Мы приведём реализацию первого шага алгоритма, сортирующего числа (для элементов другой природы потребуется изменить только процесс считывания):
New(root);
Read(f, root^.chislo);
root^.kol := 1;
root^.left := nil;
root^.right := nil;
while not Eof(f) do
begin
Read(f, x);
p := root;
while True do
begin
if x = p^.chislo then
begin
Inc(p^.kol);
Break
end;
if x > p^.chislo then
if p^.right <> nil then
p := p^.right
else
begin
New(p^.right);
p := p^.right;
p^.chislo := x;
p^.kol := 1;
p^.left := nil;
p^.right := nil;
Break
end
(* x < p^.chislo *)
else if p^.left <> nil then
p := p^.left
else
begin
New(p^.left);
p := p^.left;
p^.chislo := x;
p^.kol := 1;
p^.left := nil;
p^.right := nil;
Break
end
end;
end;
Read(f, root^.chislo);
root^.kol := 1;
root^.left := nil;
root^.right := nil;
while not Eof(f) do
begin
Read(f, x);
p := root;
while True do
begin
if x = p^.chislo then
begin
Inc(p^.kol);
Break
end;
if x > p^.chislo then
if p^.right <> nil then
p := p^.right
else
begin
New(p^.right);
p := p^.right;
p^.chislo := x;
p^.kol := 1;
p^.left := nil;
p^.right := nil;
Break
end
(* x < p^.chislo *)
else if p^.left <> nil then
p := p^.left
else
begin
New(p^.left);
p := p^.left;
p^.chislo := x;
p^.kol := 1;
p^.left := nil;
p^.right := nil;
Break
end
end;
end;
::
::
::
