Обход деревьев с помощью стека
В языках без рекурсии для обхода деревьев используется стек. Фактически, и рекурсия реализуется на основе стека, но программист не принимает в этом непосредственного участия. Явное применение стека иногда целесообразно и в качестве альтернативного к рекурсии варианта, поскольку дает больший контроль в распределении памяти и не создает трудностей при отладке. Приведем процедуру выдачи на экран номеров вершин дерева в порядке обхода сверху вниз с явным использованием стека. Применяемые переменные были описаны в предыдущей программе.
Procedure PechPrSt(T: ukaz);
Type
Point = ^stek;
stek = record
Ver: ukaz;
Next: point;
Ns: integer; {номер сына, по которому пошли вниз}
end;
Var
Top, Kon: point;
K: ukaz;
Procedure Dob(P: ukaz);
Begin
New(kon);
Kon^.Ver:=P;
Kon^.Next:=Top;
Kon^.Ns:=0;
Top:=Kon;
End;
Procedure Udal;
Begin
Kon:=Top;
Top:=Top^.Next;
Dispose(Kon);
End;
Begin
Top:=Nil;
K:=T;
Dob(K); { занесение в стек корня }
WriteLn('Вершина ', Top^.Ver^.Key);
While Top<>Nil do
begin
Top^.Ns:=Top^.Ns+1;
case Top^.Ns of
1: if Top^.Ver^.Left<>Nil then
begin
Dob(Top^.Ver^.Left);
WriteLn('Вершина ', Top^.Ver^.Key);
end;
2: if Top^.Ver^.Right<>Nil then
begin
Dob(Top^.Ver^.Right);
WriteLn('Вершина ', Top^.Ver^.Key);
end;
3: Udal;
end;
end;
End;
Последовательность прохода по сыновьям обеспечивается счетчиком Ns. Номер вершины выдается на экран при первом посещении этой вершины, то есть при добавлении вершины в стек.
Для реализации обхода снизу вверх требуются незначительные изменения. Сейчас номер вершины нужно выдавать при последнем ее посещении, то есть перед удалением из стека. Аналогично, при обходе слева направо выдача должна быть после посещения первого (левого) сына.
|
|
|
Пример программы с обходами деревьев
В качестве примера рассмотрим задачу выбора элемента максимального веса (стоимости) на И-ИЛИ дереве. Дадим сначала необходимые пояснения.
Многие объекты сложной природы удобно представлять с помощью И-ИЛИ графов и в частности И-ИЛИ деревьев. Таким способом кодируется, например, множество изделий некоторого класса технических объектов. И-ИЛИ деревом называется такое дерево, все вершины которого, не являющиеся листьями, разбиваются на два класса: И-вершины и ИЛИ-вершины. Элементами И-ИЛИ дерева считаются поддеревья специального вида. Поддерево 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.
Прошитые деревья. Леса
Стек при обходе дерева требовался для возврата из листовых вершин. Пусть задан порядок обхода сверху вниз. В листе и левый, и правый сыновья отсутствуют. Заменим в этом случае правый пустой указатель ссылкой на вершину, которая должна быть следующей. Такая ссылка называется нитью, а дерево с подобными указателями называется прошитым. Нити помечаются специальным флагом. Признаком последней вершины являются оба пустых указателя.
Легко видеть, что для обхода прошитого дерева стек не нужен, однако корректировка таких деревьев существенно труднее. Например, при удалении поддерева с корнем в вершине, на которую указывает нить, требуется найти, откуда идет эта нить и куда направлена последняя нить удаляемого поддерева. Найденные вершины должны быть соединены новой нитью.
Прошивка чаще применяется для обхода сверху вниз, возможна для обхода слева направо, но требует дополнительного указателя для обхода снизу вверх. Действительно, при подъеме из вершины с обоими сыновьями свободного указателя для нити нет.
Множество деревьев называют лесом. Для представления леса помимо работы со списком деревьев иногда используют дополнительную вершину, сыновьями которой являются корни деревьев. Тогда обход всего леса сводится к обходу единственного дерева. Нужно только иметь в виду, что корень этого дерева – фиктивная вершина, добавленная для удобства обработки.
Графы
Дата добавления: 2018-11-24; просмотров: 388; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!