Организация и функционирование компьютеров

var k: integer;

path: array [1..20] of tree;

begin

k := 1;

path [k] := root; {Начальная вершина дерева – корневая}

while (k>0) and (path[k]Nil) do

begin

write (f, (path[k])^.data);

if (path[k])^.downNil then

begin path [k+1] :=(path[k])^.down;

k:=k+1

end

else

begin while (k>0) and ( (path[k])^.right=Nil) do k:=k-1;

if k>0 then path [k] := (path[k])^.right

end

end

end;

Другой интересный случай – когда дерево составляют не объекты, а ситуации. Предположим, действительность описывается иерархической структурой ситуаций и нам нужно отыскать ситуацию, к которой относится рассматриваемый нами случай. Пусть мы умеем определять, описывает ли текущая ситуация данный случай или нет. Кроме того, если ситуация не соответствует нашему случаю, пусть мы умеем определять, может ли соответствовать случаю ситуация, подчиненная данной. Другими словами, если x – ситуация, а y – случай, то задана функция agree(x,y), которая возвращает:

• -1, если случай противоречит ситуации;

• +1, если случай может быть согласован с ситуацией;

• 0, если случай полностью соответствует ситуации.

Предположим также, что мы умеем переходить от текущей ситуации как к ситуации сына (вниз по дереву ситуаций), так и к ситуации, следующей за данной среди сыновей ситуации отца для данной (вправо по дереву ситуаций). Тогда обход множества ситуаций в поисках нужной напоминает вышеприведенную процедуру обхода вершин дерева, причем стратегия обхода зависит от значения функции agree(x,y):

• если agree(x,y)=0, то текущая ситуация является искомой;

• если agree(x,y)=-1, то бессмысленно анализировать подчиненные ситуации, то есть с точки зрения поиска текущая ситуация тупиковая и необходимо сделать “шаг вправо”;

• если agree(x,y)=+1, то следует перейти к подчиненной ситуации, то есть сделать “шаг вниз”.

Обозначенный выше метод перебора ситуаций называется методом ветвей и границ. В качестве примера можно привести задачу расстановки на шахматной доске восьми ферзей таким образом, чтобы они не били друг друга. Под ситуацией понимается расстановка ферзей на первых n горизонталях, а подчиненные ситуации – это расстановки ферзей на (n+1) горизонталях. Входные данные в этой задаче отсутствуют, то есть отсутствует переменная x, обозначающая анализируемый случай. Назовем клетку битой, если она бьется хотя бы одним ферзем из уже имеющейся расстановки. Ситуация тупиковая, если n

• y – расстановка ферзей на первых n горизонталях;

• agree(y)=-1, если ферзь на n-й горизонтали бьется другим ферзем;

• agree(y)=+1, если ферзи не бьют друг друга и n

• agree(y)=0, если ферзи не бьют друг друга и n=8.

Тогда решение задачи полностью укладывается в схему метода ветвей и границ.

4.13.5. Использование деревьев для индексирования.

Дерево называется бинарным, если каждая вершина имеет не более двух подчиненных (не более двух слуг). Бинарные деревья принято задавать иначе, чем произвольные деревья. Вместо ссылок от вершины “вниз” и “вправо” структура дерева задается ссылками к первому (“левому”) и второму (“правому”) слуге данного хозяина. Если один или оба слуги отсутствуют, соответствующие ссылки равны Nil. Путь на бинарном дереве от корня до любой вершины кодируется последовательностью нулей и единиц: нуль соответствует переходу к левому слуге, а единица – к правому. Классификация с помощью бинарного дерева называется бинарной классификацией.

Бинарные деревья играют особую роль в организации баз данных, так как на их основе происходит логическое упорядочение данных. Пусть имеется база данных, состоящая из большого количества записей, причем данные в ней неупорядочены. Для баз данных можно определить минимальный список функций, которые в любой базе данных обязаны выполняться: