|
Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр 4
Для обхода деревьев удобно применять рекурсивные процедуры. Рассмотрим пример создания бинарного дерева и выдачи на экран номеров его вершин во всех трех вариантах обхода. Program SozdTree; { создание и обходы бинарного дерева } Uses Crt; Type ukaz=^uzel; uzel=record Key: integer; Left, Right: ukaz; end; Var Kon, Root: ukaz; K, L, N: integer; Prizn: char; Procedure Sozd(T: ukaz); Begin if T<>Nil then begin Write('Введите номер вершины '); ReadLn(T^.Key); Write('У вершины ', T^.Key, ' имеется левый сын(д/н) ? '); ReadLn(Prizn); if Prizn='н' then T^.Left:=Nil else begin WriteLn('Переходим к левому сыну вершины ', T^.Key); New(Kon); T^.Left:=Kon end; Sozd(T^.Left); Write('У вершины ', T^.Key, ' имеется правый сын(д/н) ? '); ReadLn(Prizn); if Prizn='н' then T^.Right:=Nil else begin WriteLn('Переходим к правому сыну вершины ', T^.Key); New(Kon); T^.Right:=Kon end; Sozd(T^.Right) end End; Procedure PechPr(T: ukaz); Begin if T<>Nil then Begin WriteLn('Вершина ', T^.Key); PechPr(T^.Left); PechPr(T^.Right); end End; Procedure PechPo(T: ukaz); Begin if T<>Nil then Begin PechPo(T^.Left); PechPo(T^.Right); WriteLn('Вершина ',T^.Key); end End; Procedure PechIn(T: ukaz); Begin if T<>Nil then Begin PechIn(T^.Left); WriteLn('Вершина ', T^.Key); PechIn(T^.Right); end End; Begin ClrScr; New(Root); Sozd(Root); WriteLn('Дерево создано !'); ReadLn; { пауза } PechPr(root); WriteLn('Печать в порядке сверху вниз '); ReadLn; PechPo(Root); Writeln('Печать в порядке снизу вверх '); ReadLn; PechIn(Root); WriteLn('Печать в порядке слева направо '); ReadLn End. Здесь дерево представлено с помощью указателей. Можно представить дерево и массивом на основе следующих объявлений: Type uzel=record Key: integer; Left, Right: integer; {индексы в массиве вершин, -1 –признак листа} end; Var Ver: array[1..100] of uzel; {вершина с индексом 1 – корень дерева} Kon: integer; {число вершин, а также индекс последней вершины} Необходимые изменения текста программы можно произвести путем контекстной замены:
Полезно на примере дерева из 5-6 вершин рассмотреть работу одной из рекурсивных процедур (например, PechPr). Удобно в этом случае считать, что при каждом рекурсивном обращении в память загружается новая копия процедуры. 3. 2. Обход деревьев с помощью стека
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 { начало процедуры PechPrSt } 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. Номер вершины выдается на экран при первом посещении этой вершины, то есть при добавлении вершины в стек. Для реализации обхода снизу вверх требуются незначительные изменения. Сейчас номер вершины нужно выдавать при последнем ее посещении, то есть перед удалением из стека. Аналогично, при обходе слева направо выдача должна быть после посещения первого (левого) сына. 3.3. Пример программы с обходами деревьев В качестве примера рассмотрим задачу выбора элемента максимального веса (стоимости) на И-ИЛИ дереве. Дадим сначала необходимые пояснения. Многие объекты сложной природы удобно представлять с помощью И-ИЛИ графов и в частности И-ИЛИ деревьев. Таким способом кодируется, например, множество изделий некоторого класса технических объектов. И-ИЛИ деревом называется такое дерево, все вершины которого, не являющиеся листьями, разбиваются на два класса: И-вершины и ИЛИ-вершины. Элементами И-ИЛИ дерева считаются поддеревья специального вида. Поддерево R некоторого И-ИЛИ дерева является его элементом, если оно обладает следующими свойствами:
Изделие или техническое решение может быть представлено с помощью обычного дерева. Всему изделию ставится в соответствие корень дерева. Основным узлам, на которые разбирается изделие, соответствуют сыновья корня. Подобным образом строится все дерево. Деталям, считающимся неразборными, соответствуют листья дерева. С помощью И-ИЛИ дерева можно представить множество изделий. В этом дереве некоторая вершина V будет И-вершиной, если любое изделие содержит все узлы, соответствующие сыновьям вершины V. Если же в изделие входит только один сын вершины V, то V будет ИЛИ-вершиной. Например, опишем в упрощенном виде представление с помощью И-ИЛИ дерева множества велосипедов. Корень И-ИЛИ дерева имеет название "велосипед". Каждый велосипед содержит раму, руль, седло и колеса, поэтому корень дерева является И-вершиной. Рассмотрим сына корневой вершины, соответствующего раме. Пусть рамы могут быть таких типов, как "мужская", "женская", "разборная". Отдельный велосипед имеет определенный тип рамы, поэтому вершина дерева, соответствующая раме, является ИЛИ-вершиной. Если каждая разборная рама имеет одинаковые составляющие части, то вершина дерева с названием "разборная рама" будет И-вершиной. Аналогично рассматривая другие узлы велосипеда, можно построить все И-ИЛИ дерево. Элементы данного дерева будут описывать отдельные типы велосипедов. Рассмотрим следующую задачу. Задано И-ИЛИ дерево, соответствующее некоторому множеству изделий. В вершинах дерева в баллах от 0 до 15 даны экспертные оценки новизны узлов. Новизна изделия определяется как сумма оценок новизны всех вершин соответствующего элемента. Требуется:
Опишем укрупненно алгоритм решения задачи.
И-ИЛИ дерево кодируется с помощью бинарного дерева. Данная задача служит иллюстрацией методов представления в памяти деревьев, вариантов их обхода, применения рекурсивных процедур. Приведем текст соответствующей программы. 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 |
Loading
|