IPB

> Лекция №12.4: Алгоритмы на графах и деревьях
Чат
Форум
Загрузка...
 

страницы: 1 2 3 4 5 6

Содержание

Обход в ширину

Последовательность обхода
  1. Пометить вершину 0–го уровня (корень дерева).
  2. Пометить все вершины 1–го уровня.
  3. Пометить все вершины 2–го уровня.
  4. ...

Последовательность нумерации вершин при синтаксическом обходе  дерева

Рис. 12.4.  Последовательность нумерации вершин при синтаксическом обходе дерева

Замечание: Этот алгоритм может быть естественным образом распространён и на случай произвольного корневого дерева.

Алгоритм WideOrder
  1. Занести в очередь1 корень дерева.
  2. Пока очередь не станет пустой, повторять следующие действия:
    1. удалить первый элемент из головы очереди;
    2. добавить в хвост очереди всех потомков удалённой вершины.
Реализация

Для простоты реализации вновь пополним структуру дерева полем 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;

Последовательность нумерации вершин при обходе дерева в ширину

Рис. 12.5.  Последовательность нумерации вершин при обходе дерева в ширину

Древесная сортировка

Задача. Упорядочить заданный набор (возможно, с повторениями) некоторых элементов (чисел, слов, т.п.).

Алгоритм TreeSort
  1. Для сортируемого множества элементов построить дерево двоичного поиска:
    • первый элемент занести в корень дерева;
    • для всех остальных элементов: начать проверку с корня; двигаться влево или вправо (в зависимости от результата сравнения с текущей вершиной дерева) до тех пор, пока не встретится такой же элемент, либо пока не встретится nil. Во втором случае нужно создать новый лист в дереве, куда и будет записано значение нового элемента.
  2. Совершить синтаксический обход построенного дерева, печатая каждую встреченную вершину столько раз, сколько было её вхождений в сортируемый набор.
Реализация

Мы приведём реализацию первого шага алгоритма, сортирующего числа (для элементов другой природы потребуется изменить только процесс считывания):

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;

страницы: 1 2 3 4 5 6

Примечания

  1. ^ См. лекцию 9.
 
 К началу страницы 
 

Код для вставки: :: :: :: ГОСТ ::
Поделиться: //
 



-
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"