Пример программы с обходами деревьев

В качестве примера рассмотрим задачу выбора элемента максимального веса (стоимости) на И-ИЛИ дереве. Дадим сначала необходимые пояснения.

Многие объекты сложной природы удобно представлять с помощью И-ИЛИ графов и в частности И-ИЛИ деревьев. Таким способом кодируется, например, множество изделий некоторого класса технических объектов. И-ИЛИ деревом называется такое дерево, все вершины которого, не являющиеся листьями, разбиваются на два класса: И-вершины и ИЛИ-вершины. Элементами И-ИЛИ дерева считаются поддеревья специального вида. Поддерево R некоторого И-ИЛИ дерева является его элементом, если оно обладает следующими свойствами:

· R содержит корень дерева;

· если R включает некоторую И-вершину, то вместе с ней в R входят все сыновья данной вершины;

· если R включает некоторую ИЛИ-вершину, то вместе с ней в R входит ровно один сын данной вершины.

Изделие или техническое решение может быть представлено с помощью обычного дерева. Всему изделию ставится в соответствие корень дерева. Основным узлам, на которые разбирается изделие, соответствуют сыновья корня. Подобным образом строится все дерево. Деталям, считающимся неразборными, соответствуют листья дерева.

С помощью И-ИЛИ дерева можно представить множество изделий. В этом дереве некоторая вершина V будет И-вершиной, если любое изделие содержит все узлы, соответствующие сыновьям вершины V. Если же в изделие входит только один сын вершины V, то V будет ИЛИ-вершиной.

Например, опишем в упрощенном виде представление с помощью И-ИЛИ дерева множества велосипедов. Корень И-ИЛИ дерева имеет название "велосипед". Каждый велосипед содержит раму, руль, седло и колеса, поэтому корень дерева является И-вершиной. Рассмотрим сына корневой вершины, соответствующего раме. Пусть рамы могут быть таких типов, как "мужская", "женская", "разборная". Отдельный велосипед имеет определенный тип рамы, поэтому вершина дерева, соответствующая раме, является ИЛИ-вершиной. Если каждая разборная рама имеет одинаковые составляющие части, то вершина дерева с названием "разборная рама" будет И-вершиной.

Аналогично рассматривая другие узлы велосипеда, можно построить все И-ИЛИ дерево. Элементы данного дерева будут описывать отдельные типы велосипедов.

Рассмотрим следующую задачу. Задано И-ИЛИ дерево, соответствующее некоторому множеству изделий. В вершинах дерева в баллах от 0 до 15 даны экспертные оценки новизны узлов. Новизна изделия определяется как сумма оценок новизны всех вершин соответствующего элемента. Требуется:

· обеспечить ввод И-ИЛИ дерева с клавиатуры;

· найти элемент с максимальной новизной.

Опишем укрупненно алгоритм решения задачи.

1. Ввод И-ИЛИ дерева в порядке сверху вниз.

2. Расчет для каждой вершины в порядке обхода снизу вверх максимальной оценки новизны среди элементов поддерева, висящего на данной вершине. Выбор для каждой ИЛИ вершины сына с максимальной оценкой новизны и простановка признаков запрета для других сыновей.

3. Печать в порядке сверху вниз незапрещенных вершин дерева.

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

Program Tree;

Uses Crt;

Type

ukaz=^uzel;

uzel=record { информация о вершине дерева }

Pr: char; { вид вершины: 'a'-И, 'o'-ИЛИ, 'l'-лист }

Name: string; { название }

Nov: 0..15; { баллы новизны }

Left, Right: ukaz; { левый и правый сыновья бинарного дерева }

SumNov: integer;

{ максимальная суммарная новизна среди элементов }

{ поддерева, висящего на данной вершине }

Zapret: char { признак запрета: 'z'-есть,'r'-нет }

end;

Var

Prizn: char;

M, K: integer;

Kon, Root, Rab: ukaz;

Namer: string;

Procedure Sozd(T: ukaz); { ввод И-ИЛИ дерева }

Begin

if T<>Nil then

begin

Write('Введите название ');

ReadLn(T^.Name);

Write('Введите показатель новизны ');

ReadLn(T^.Nov);

T^.SumNov:=0;

T^.Zapret:='r'; { пока все разрешено }

Write('Вершина ', T^.Name, ' лист дерева(д/н) ? ');

ReadLn(Prizn);

if Prizn='д' then { лист }

begin

T^.Left:=Nil;

T^.Pr:='l'

end

else { не лист }

begin

Write('Это ИЛИ-вершина (д/н) ? ');

ReadLn(Prizn);

if Prizn='д' then T^.Pr:='o'

else T^.Pr:='a';

WriteLn('Переходим к левому сыну вершины ', T^.Name);

New(Kon);

T^.Left:=Kon

end;

Sozd(T^.Left);

if T=Root then

begin

T^.Right:=Nil;

Exit { правого соседа корня не может быть }

end;

Write('У вершины ', T^.Name, ’ имеются правые соседи(д/н) ? ');

Readln(Prizn);

if Prizn='н' then T^.Right:=Nil

{ 'н'-признак отсутствия соседей }

else

begin

WriteLn('Переходим к правому соседу вершины ', T^.Name);

New(Kon);

T^.Right:=Kon;

end;

Sozd(T^.Right)

end

End;

Procedure Rasch(T: ukaz); { см. п.2 алгоритма }

Begin

if T<>Nil then

Begin

Rasch(T^.Left);

Rasch(T^.Right);

if T^.Left<>Nil then { не лист }

if T^.Pr='a' then { И-вершина }

begin

Kon:=T^.Left;

While Kon<>Nil do

begin

T^.SumNov:=T^.SumNov+Kon^.SumNov;

Kon:=Kon^.Right

end

end

else { ИЛИ-вершина }

begin

Kon:=T^.Left;

M:=-1;

While Kon<>Nil do

begin

Kon^.Zapret:='z'; { сначала запрет }

if Kon^.SumNov>M then

begin

M:=Kon^.SumNov;

Rab:=Kon

end;

Kon:=Kon^.Right { следующий сын }

end;

T^.SumNov:=M;

Rab^.Zapret:='r'; { оставили лучшую вершину }

end;

T^.SumNov:=T^.SumNov+T^.nov; { учет возможной оценки отца }

end

End;

Procedure Pech(T: ukaz);

{ печать сверху вниз лучшего (незапрещенного) элемента }

Begin

if T <> Nil then

begin

if T^.Pr='a' then Namer:=' (И-вершина) '

else if T^.Pr='o' then Namer:=' (ИЛИ-вершина) '

else Namer:=' (лист дерева) ';

if T^.Zapret<>'z' then

begin

Write(T^.Name,Namer);

WriteLn(' оценка новизны - ', T^.SumNov);

end;

Pech(T^.Left);

Pech(T^.Right)

end

End;

Begin

ClrScr;

New(Root);

Sozd(Root);

WriteLn('Дерево создано !');

ReadLn; { пауза }

Rasch(Root);

WriteLn('Расчет проведен !');

ReadLn;

WriteLn('Лучший элемент !');

Pech(Root);

ReadLn

End.

Графы