Использование указателей для обработки деревьев
Графом называется совокупность объектов, называемых вершинами графа, и связей между ними, которые принято называть дугами графа. Граф, в котором каждая связь имеет направление, называется направленным графом. Принято изображать вершины графа точками на плоскости, а связи между ними - отрезками (направленные связи - стрелками). Путем на графе называется последовательность вершин, соединенных дугами. Для направленного графа направление пути должно совпадать с направлением каждой дуги пути.
Пара вершин направленного графа, соединенная стрелкой, называется главной и подчиненной вершиной (или хозяином и слугой, или отцом и сыном). Вершина может быть одновременно отцом и сыном. Циклом в направленном графе называется замкнутый путь, то есть путь, начало и конец которого совпадают. Если граф не имеет циклов, то обязательно имеется хотя бы одна вершина, в которую не входит ни одна стрелка. Такая вершина называется корневой. Граф, у которого ровно одна корневая вершина, является связным. В таком графе для каждой вершины существует путь из корневой вершины в данную. Наконец, деревом называется связный направленный граф без циклов, у каждой вершины которого не более одного хозяина. На самом деле в дереве все вершины, кроме корня, имеют хозяина. В каждую вершину дерева из корня ведет ровно один путь, то есть существует взаимно-однозначное соответствие между вершинами и путями. Если вершина не имеет подчиненных вершин, то она называется концевой вершиной или тупиком или листом.
Назовем корневую вершину вершиной первого уровня, ее сыновей - вершинами второго уровня, сыновей ее сыновей - вершинами третьего уровня и т.д. Максимальный уровень называется глубиной дерева. Далее, для каждой вершины перенумеруем дуги, выходящие из этой вершины. Можно ввести так называемый лексикографический порядок на множестве вершин дерева. Именно, для каждой пары вершин возьмем два пути, ведущие из корня в эти вершины. Тогда эти пути либо один продолжает другой, либо они расходятся с некоторой точки.
В первом случае будем предполагать, что более длинный путь следует за более коротким. Во втором случае порядок определяется номерами первых несовпадающих дуг путей.
Приведем пример дерева. В каждой вершине изобразим три цифры: уровень вершины дерева, номер в списке слуг хозяина данной вершины и общий номер в множестве вершин дерева.
 |
|||
 |
 |
|||
 |
|||
Тупиками являются вершины с номерами 4,5,7,9,10, 12,14,15,16,17,18.
Важным свойством дерева является свойство подобия, которое заключается в том, что множество всех потомков данного хозяина (сыновей, сыновей сыновей и т.д.) образуют дерево. Оно является поддеревом дерева с корнем в данной вершине. Такое поддерево иногда называют ветвью дерева. В частности, каждое дерево состоит из корня дерева и нескольких ветвей, корнями которых служат все вершины первого уровня дерева.
Деревом изображаются любые иерархические структуры, которые очень часто встречаются на практике. Например структура подразделений компании или структура административного деления регионов. Деревом является классификация видов животных или перечень номенклатуры изделий (и вообще, любая классификация). Иерархия объектов в реальной действительности приводит к иерархии описаний объектов в памяти компьютера.
Как и в случае списков, описание вершины дерева состоит из двух частей: содержательной информации (описания объекта) и структурной информации (положения объекта в дереве). В данный момент нас интересует структурная информация.
Ее состав зависит от функций, которые она должна обеспечивать. По крайней мере, необходимо уметь перечислить вершины дерева в порядк взрастания. Для этого можно предложить следующую схему. Для каждой вершины будем задавать структурную информацию в виде двух указателей. Первый указатель ссылается на первого по порядку слугу данной вершины. Если вершина тупиковая и слуг не имеет, то указатель пусть равен значению Nil. Второй указатель ссылается на следующего по порядку слугу среди слуг хозяина данной вершины. Если данная вершина последняя в списке слуг своего хозяина, то указатель пусть также равен значению Nil. Система вторых указателей превращает дерево в совокупность линейных однонаправленных списков слуг некоторого хозяина. Первый указатель при вершине содержит ссылку на начало списка
type
rec = record <поля данных> end; {запись данных}
ptree = ^tree; {тип указателя на элемент списка }
tree = record {тип элемента списка}
data: rec; {данные вершины дерева}
down: ptree {ссылка на 1-го слугу данной вершины}
right: ptree {ссылка на следующего слугу хозяина вершины}
end;
var root: ptree; {ссылка на корневую вершину дерева}
Пусть теперь дерево описывается в форме совокупности динамических переменных, каждая из которых задает вершины дерева. Приведем пример процедуры, выводящей в файл данные всех вершин дерева в лексикографическом порядке.
procedure write_tree (f: tpf); {f - файловая переменная типа tpf = file
of rec}
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])^.down<>Nil 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)=0, то текущая ситуация является искомой;
- если agree(x,y)=-1, то бессмысленно анализировать подчиненные ситуации, то есть с точки зрения поиска текущая ситуация тупиковая и необходимо сделать “шаг вправо”;
- если agree(x,y)=+1, то следует перейти к подчиненной ситуации, то есть сделать “шаг вниз”.
- y - расстановка ферзей на первых n горизонталях;
- agree(y)=-1, если ферзь на n-й горизонтали бьется другим ферзем;
- agree(y)=+1, если ферзи не бьют друг друга и n<8;
- agree(y)=0, если ферзи не бьют друг друга и n=8.
Предположим также, что мы умеем переходить от текущей ситуации как к ситуации?сына (вниз по дереву ситуаций), так и к ситуации, следующей за данной среди сыновей ситуации?отца для данной (вправо по дереву ситуаций). Тогда обход множества ситуаций в поисках нужной напоминает вышеприведенную процедуру обхода вершин дерева, причем стратегия обхода зависит от значения функции agree(x,y):
Обозначенный выше метод перебора ситуаций называется методом ветвей и границ. В качестве примера можно привести задачу расстановки на шахматной доске восьми ферзей таким образом, чтобы они не били друг друга.
Под ситуацией понимается расстановка ферзей на первых n горизонталях, а подчиненные ситуации - это расстановки ферзей на (n+1) горизонталях. Входные данные в этой задаче отсутствуют, то есть отсутствует переменная x, обозначающая анализируемый случай. Назовем клетку битой, если она бьется хотя бы одним ферзем из уже имеющейся расстановки. Ситуация тупиковая, если n<8
и все поля (n+1)-й горизонтали бьются ферзями из первых n горизонталей. “Шаг вниз” заключается в выборе первой слева небитой клетки (n+1)?й горизонтали. “Шаг вправо” заключается в выборе следующей с правой стороны небитой клетки в n?й горизонтали. С формальной точки зрения:
Тогда решение задачи полностью укладывается в схему метода ветвей и границ.
