Лекции по информатике (984119), страница 7
Текст из файла (страница 7)
Эти способы определяютс с рекурсивно, При обходах выполняются следующие действия 144~; 1. при прямом обходе (КЛП, ргеогс1ег, корень прежде): (а) если дерево пусто, то конец обхода;. (Ь) берется корень; (с) выполняется обход левого полдерева; (сЦ выполняется обход правого поддерева. 2, при обратном обходе (ЛКП, 1погс1ег, корень между): (а) если дерево пусто, то конец обхода; (Ь) выполняется обход левого поддерева; (с) берется корень; (с1) вьпюлняется обход правого полдерева. 3.
при концевом обходе (ЛПК, ровгогс1ег, корень в конце): (а) если дерево пусто, .то конец обхода; (Ь) выполняется обход левого поддерева; (с) выполняется обход правого полдерева; (сЦ берется корень. Для примера дерева, приведенного ниже, при прямом обходе узлы буд,ут взяты в таком порядке: А, В, С, П, Е, Г, С', 11; при обратном обходе узлы будут взяты в таком порядке С, В, Е, Р, А, Г, Н, С; при концевом обходе узлы будут взяты в таком порядка: С, Е, Р, В, Н, С, 1г, А. При обходе деревьев могут использоваться либо рекурсивные процедуры, либо программы с циклом., зависящим от состояния стека.
в котором отражается текущее положение в дереве (Зб1 Нерекурсивный обход дерева с явным использованием стека аналогичен 1эекурсивггому ис1голненило гга внут!генном стеке среды языка, обеспечиваклщем 1лекурсиго. Наконец, существукгг такие способы представления деревьев, при которых возможен итеративный обход! Теперь нетрудно составить рекурсивные процедуры выполнения трех различных ме; тодов обхода двоичного дерева: ргосес1пге ргеогс1еф: р); Ьеиш И 1 <> ш1 ФЬеп Ьеиш 1' обработка вершины: 1".да1а г=- ... или итйе!'1 .доХа) лГ ргеогс1ег(с ".1); ргеогс1ег!г, .г) епс1 епс1; 1ргеогдег~ ргосес1пге !погс1еф: р); Ьеиш Ы с <> и!1 с1геп Ьеиш пгогс1ег (1 ". ! ); 1' обработка вершины л! !погс1ег($ .г) епс1 «с !'л 1ег) ргосес1пге роагогс!ег(г; р); Ьеиш К г <> ш1 йеп Ьеи1п роа$огс1ег(г .1); роагогс1ег!г".г) 1' обрабопгка верилины л! епс1 епс1; 1роз1огдеглГ Во всех трех рекурсивных процедурах ссылка на, текущий корень дерева передается по значению, и заносится при рекурсивном выполнении во временной стек экземпляров локальной переменной.
Нри обходе изменение значений этой переменной не ггроизводится. Нерекурсивпое выполнение процедуры обхода может быть поддержано рекурсивной структурой данных типа стек. ргосес1пге !гюгс1ег2(ггее: р) чаг з$: огас!с; !' о1 р1 указателей корневых узлов, для которых начат, но есце не завершен обход левого поддерева лГ с1опе: Ьоо1еап; Ьеиш Сгеа1е!зс); с1опе: -- Га1ве; гер еаза 1' Рассматриваемые вершины дерева заносятся в сгпек до гав пор, пока не 274 встретится першино, с пустым, левым. поддеревом (лллспл или ве1лиина только с правьлм >лоплоллкг>лл) 3 1Г(1гее <'> ш1) сЬеп Ьен1п Рпв1>(зс, Ггее); 1' Указатель текушего узла гломещаегпся в стек >Г ггее: — Ггсгл> .1; 1' Для глродолж:еглгля обхода выбирается, указатель но, левое поддерево >Л епс1 е1ве Ы(Егггрсу(зГ)) СЬеп ~с В стеке нет веригин для обхода >Л с1опс: — $гпе лг Ус>пп>лосзксл глрг знака завериления итератллвного обхода >л е1ве Ьеи1п 1' В стеке есть отлоэлсенньле вершиньл для обхода >Г ггее: Тор(зг); 1' Вълбираем для обхода родителя текущего узла, находящегося в стеке вслед за потомком >Г Рор(зь); 1 Указатель родителя текущего узла удаляетс.я из стека.
В результате этой операции в вершину стека поднимаегпея родитель удаленного узла >Л 1' Здесь могла бы быть обработка узла! >Л сгее: =- сгее .г1~1>1; 1' Переход к обходу правого поддерева >Г епс1; ппЫ с1опе; ВезСгоу(зс); епс1; 5.10.3 Построение и визуализация дерева Типичный пример программы, в которой осуществляется обход дерева: рекурсивная процедура ступенчатой распечатки дерева. Но сначала надо создать дерево.
Очевидно, непосредствешю ввести его из текстового файла непросто. Но мы глоступим также, как при вводе многочлепа в Наскалыгрограьгьгу дифференцирования: введем «коэффициенты дерев໠— значения узлов в некотором регулярном порядке. Рассмотрим программу построения дерева из и вершин, значения которых поступают из входного текстового файла 1прШ. Если нам нужно построить из этих вершин какоенибулсь дерево, то можно вернуло из них сделать корнем, вторую правым поддеревом, третью правым поддеревом правого полдерева, и т, д, В результате получим линейное дерево (список) максимальной глубины (и). Интереснее ооратная задача: построить из этих же вершин дерево минималыгой глубины.
Для этого при построении дерева надо добиться его равноъгерного запо>шения (ау, сплошгюе турнирное представ>гение!), размещая приходящие вершины поровну слева и справа от каждой вершины по следуннцему рекурсивному(!) правилу: ° взять одну вершину в качестве корня„ ° построить тем же способом левое поддерево с пл = п с11ь' 2 вершинами: ° построить тем же способом правое почдерево с и„= и — гл~ — 1 вершиной. Этот алгоритм строит идеально сбалансированное дерево, поскольку число вершин в его левых и правых поддеревьях отличается нс, более, чем на 1.
Соответствунпцая программа на Паскале: 275 ргодгаш 1г!гвС'1'гее(!прог, ошриг); 1' Н. Бирггл 7' Суре р - пос1е; ггос1е --- гесогс1 !сеу: сЬаг; !,г:р епс1; айаг и: шСедег; гооС: р; ГппсС1оп Ьи!!с!Сгее(п: шСедег): р; айаг пос1е: р„ х, п!, ггг: шСецег; Ьеа:ш 1 посгпроенис идеально сба.лансглрованного дерева 7' Ы и:= О СЬеп пос1е:=- и11 е1ве Ьецш !' распределение вершин налево и направо 3 п1:== и с1Ь 2; пг: п — п1 — 1: геас1(х); пелгт!пос1е); ж1СЬ пос1е" с!о Ьедш 1сеу: х; !' псрепорученив построения двум по,лудсрсвьям гг 1: Ьи!1с1Сгее(п1): г: — Ьш 1с1Сгее (пг) епс1; епс1:, Ьи! !г1Сгее: — по с!е епс1; (Ьиг1ЙСтвс) ргосес1ше рг!пСГгее(С: р: Ь: шСедег); Ьееш !' спггуггеггнатая печать г7срсва с отстаупом„равнгям глубине узла гг 11 ! <> ш1 СЬеп ллг1СЬ С с1о Ьедш рг1псггее (1, Ь вЂ”; 1); ллг1Се1п('„': Ь вЂ”: 1, 1сеу: 3); рг!пСггее(г, Ь вЂ” , '1) епс1; епс1:, епс1; (ртлпССтсеу Ь ерш (ртоутат) геас1 !гг); гоог; — Ьп1!с!Сгее (п); ргппггее (гооС.
0) 1 (р'оу / Если на вход этой программы подать последовательность 21 8 9 11 15 19 20 21 7 3 2 1 5 6 4 13 14 10 12 .!7 16 18 то будет построено идеально сбалансированное дерево из 21 вершины: Программа напечатает т. н. АВСП-визуализацию дерева, лежащего на боку и без графических излишеств — ребер и вершинных кружков, но с сохранением топологии. Простота и ясность этой рекурсивной программы лучшее доказательство уместности рекурсии, рекурсия выполнения хорошо отражает рекурсия> структуры дерева.
В мелочах тоже все гладко: дерево из 0 элементов не строится и нс печатается. 5.10.4 Деревья выражений. Разнофиксные формы записи выра- жений Обходя дерево выражения разными способами, мы получим три различные очереди вершин ~43~: ° КЛП: ~ + а / Ь с — с1 ~ е Х; еЛКП а+Ь/сФс1 — еФХ; ° ЛПК: а Ь с / + с1 е Х Ф вЂ” Ф. которые представляют собой пи что иное, как широко используемые в информатике различные формы записи выражений: префиксную 1ассемблер, код операции ~г,еред (1>ге1 операндами, называемую также польской), привычную инфикспую (математическую, знак операции мелсду (гп) операндами), по без скобок, задающих порядок выполнения операций, и постфиксную (обратнун> польскук>). БесскоГх>чная форма записи представляет собой линейную последовательность действий, пригодную для выполнения обычным фон Неймановским кокшьютером, История бесскобочной записи такова: 277 «Польский математик и логик Ян Лукагпевич печатал в 1920 г.
свою докторскую диссс;ртапию на старой немецкой пиптущей машинке, у которой было не две клавиши переключения регистров, а три: строчные буквы и знаки препинания, прописные буквы, а также все скобки и другие специальные символы. Вместо того., чтобы вынужденно использовать все три клавиши переклю гения регистра (старая, с грохотом работавшая пишущая машинка, часто заедала, при переключении регистров), Лукашевич изобрел запись, которая не требовала применения скобок. Для этого обычная запись операнд оператпор оттеранд была, заменена на запись оператор оттеранд операнд.
Таким образом, обычная запись А -1 В провратилась в запись 1 А В» 186~. Рассмотрим программу построения и распечатки дерева выражения по его линейной скобочной (инфиксной) записи. ргоатагп ехрг2Сгее(шрпС, опСрп! ); /Лебедев А. В.) / Синтаксис выраотсения ехрт. — > Сегтгт / ехрг «- Сегта / етрг — Сегт Сегт — /асс / Сегт « /асС / Сетт,' /асС /асС вЂ” > /ехрг) / с1гдИ / 1еССег дтутй — > 0 / 1 / й / 3 / 4 / 5 / б / 7 / 8 / 9 1еССег — > а / 6 / Суре Сгее — "пос?е; пос1е - гесогс1 с1аса: сЬаг; 1, г: Сгее; епс1; ттаг ехрг?гее: тгее; ГппсС1оп 1яа1тппп(с?т: сЬаг): Ьоо1еап; Ьеи1п 1аа1пптп:-- ((с?т >-- 'а') апс1 (с?т <-- 'х')) ог ((с1т >-- 'О') апс1 (сй <-- '9')/ епс1; ГппсС1оп п1а1сепос1е(с: сЬаг: 1, г: Сгее): Сгее; ттаг С: Сгее; Ьеи1п пеи ®: С х1аса х с; С ".!: — 1; С .г:- 278 го а1сеп ос1е: епс1; ргосес1пге с1евСгоусгес(С: 1гве); чаг р: ггво; Ьефп ( рекурсивно — итеративное уничтонсение дерева) (рекурсивный спуск, влево внутри итперптивноао спуска вправо) жЬ11е С <> ги1 с1о Ьефп с1евтгоусгес1С .11; р: — С; Ст-С .г„ Йврове 1р~ епс1; епс1; ргосес1ш е рг1пССгее11,: Сгее); ргосес1пге рг1пС(С: Сгее; СаЬ: шСедег); чаг 1: шСедег; Ьедш 1Г г .г <> п11 СЬеп рг1пй1С .г, Сао -, Ц; Гог 1 и- О Со гаЬ вЂ” 1 с1о тчг1Се(' '); юг1Се1п1С .с1а!а); Г С .1 <> п11 СЬеп рг1п11С .1, СаЬ '- 1); епс1:, (полурекурсавная версия процедуры распечатка: рекурсивный спуск по правой ветке сочетается с итеративным по левой) (ртосЫите ртт1(1: Стев; СаЬ: 1пГедех); иат 1: 1п8едет; Ьедгп тереаС ю( С ".
т < > и Н У~еп рт1пЦ(1 х, Саб + 1); 1от 1:= (! Со СаЬ вЂ” 1 до гатгсе (' гопсе1п (С ". Наса); Саб::=- СаЬ 1„. ипСЙ С --- п11; Ьед1п (уменьшим вложенность рекурсии( 11' С <> ш! СЬеп ргшССС, О); епс1; ГппсСюп расее: сгее; ( разбор вы раоюения / чаг сЬ: сЬаг; СппсСюп ехрс: Сгее; 1осжагс1; ( разбор подвыражен я ~С (опережающее обаяв. ление процедуры для. косвенной рекурси'а егрг — > Сегт — > (асс — > екрг,с СппсС1оп 1асС: сгее; ( разбор множителя делимого~'делителя ( Ьефп геас1 ссЬ); 11' сЬ =- 'л ' СЬеп Ьед1п ( множитель содержит подвыражение ~С ГасС:==- ехрт; ( Ц сй <'> ')' й,еп диагностика отсутствия закрывающей скобки3 епс1 е1ае 11' 1аа1ппспСсЬ) СЬеп 1асс: — спа1сессос1еСсЬ, ш1, ш1) ( создание терминальной вершины, (листа) для переменной или константы 3 ( е1зе диагносспика некоррекспной .литеры) епс1; ЙшсСюп Сегпш Сгсе; ( Разбор слагаемого~'уменьшаамогогсгы читаемого г~ чаг Сш: Сгее; с1отп:: Ьоо1еап:, Ьее1п Спс: — брасс; с1опе:-- Га1ве1 лчЬ11е поС ео!п апс1 поС с1опе с1о Ьефп геас1 (сЬ); сс ссЬ -- 'э') ог ссЬ -- '(') сЬеп спс:-- спа1сепос1еСс1ц сш, 1асс) ( Подвеска поддерева подвыражения с рекурсивным разбором очередного подвъсражения ~ е1ве с1опе: — Сгпе; епс1., Сепп:=- сш; епс1; 280 КпгьсСюп ехрг: ( разбор тюдвыроьнсенияс рсьнее от,лоэюенное описание тпела процедуры ) чаг ех: 1гее; с1опе: Ьоо1еап; Ьедш сх; 1епи; с1опе: Га1не; ъч1п1е поС ео1п апс1 поС с1опе с1о Ьедш 11' 1с1ь - '-'') ог 1с1ь =- ' — ') СЬеп ех: — ьпа1.епос1еьс1ц ех, 1епп) ( Подвеска поддерева подвыражения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
