AOP_Tom1 (1021736), страница 95

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 95)

Зб. [40) Дайте определение тройного дерева((егпагу (гее) (а в более общем случае — и арного дерева для произвольного 1 > 2), аналогичное определению бинарного дерева, и исследуйте воэможность обобщения для парных деревьев результатов, полученных в этом разделе и в упражнениях после него. 36. [ММЯ) В упр. 1.2,1-15 показано, что лексикографический порядок расширяет полное упорядочение множества 3 до полного упорядочения множеств из п элементов множества Я. В приведенном выше упр.

25 показано, что линейное упорядочение данных а узлах дерева может быть расширено до линейного упорядочения деревьев на основе аналогичного определения. Если отношение м приводит к полному упорядочению множества 3, то является ли расширенное отношение из упр. 25 полным упорядочением набора Т? ь 37. [24) (Задача Д, Фергюсона.) Если два слова в памяти компьютера обязательно долясны содержать два поля связи н поле 1МРО с данными, то в таком случае для представления дерева типа (2) с и узлами потребуется 2п слов. Создайте схему представления бинарных деревьев, для которой в памяти компьютера потребовалось бы выделить меньшее количество слов, предполагая, что одна связь и одно поле 1ИГО с данными могут уместиться в одном слове. 2.3.2.

Представление деревьев в виде бинарных деревьев Перейдем от бинарных деревьев к деревьям общего вида. Напомним следующие основные различия между деревьями и бинарными деревьями. 1) Дерево всегда имеет корень., т. е. оно никогда не бывает пустым; каждый узел может иметь О, 1, 2, 3, ... детей. 2) Бинарное дерево может быть пустым, а камсдый его узел может иметь О, 1 или 2 детей; мы будем различать левых и правых детей. Напомним также, что лес является упорядоченным набором некоторого количества деревьев (и даже равного нулю).

Поддеревья любого узла дерева образуют лес. Существует естественный способ представления любого леса в виде бинарного дерева. Рассмотрим следующий лес, состоящий из двух деревьев: Соответствующее бинарное дерево получим за счет связывания детей каждой семьи и удаления всех вертикальных связей, за исключением связи с родителем первого ребенка. Затем, наклонив зту схему под углом 45' и слегка откорректировав расположение узлов, получим такое бинарное дерево; И наоборот, после выполнения этих действий в обратном порядке становится очевидно, что любое бинарное дерево соответствует единственному лесу деревьев. Приведение схемы (1) к схеме (3) имеет чрезвычайно большое значение. Оно называется естественным соотеетсгпеием (па8ига1 соггеэропаепсе) между лесом и бинарными деревьями.

В частности, оно задает соответствие между деревьями и особым классом бинарных деревьев, а именно — между бинарными деревьями с корнем, но беэ правого поддерева. (При этом можно было бы слегка изменить точку зрения и допустить, что корень дерева соответствует заголовку списка бинарного дерева. В таком случае получим взаимно однозначное соответствие между деревьями с и + 1 узлами и бинарными деревьями с и узлами.) Пусть Г = (Ты Тэ,..., Т„) — некоторый лес деревьев. Тогда бинарное дерево В(Е), соответствующее Е, можно строго определить следующим образом. а) Если и = О, то В(Р) пусто. Ь) Если и ) О, то корень В(Е) является корнем (Т,); В(Т~ы Тщ,..., Т~ ) является левым поддеревол~ дерева В(г'), где Т ыТш,...,Т, — поддеревья корня (Т~); В(Тэ,..., Т„) является правым поддеревом дерева В(г').

Эти правила строго определяют приведение схемы (1) к схеме (3). Иногда удобно изображать схему бинарного дерева в виде (2), без поворота на 45~. Тогда соответствующее виду (1) прошитое (1Лгеааед) бинарное дерево будет выглядеть так: (4) (Ср. с рис. 24, повернув его на 45'.) Обратите внимание на то, что правые связннятп проходят от крайнего справа ребенка семья к его родителю. Левые связи-нити не имеют такой естественной интерпретации из-за отсутствия симметрии между левой и правой сторонами. Представленные в предыдущем разделе идеи обхода можно теперь применить к лесу (т. е. к деревьям). Хотя простой аналогии симметричного порядка обхода здесь нет из-за отсутствия очевидного места вставки корня среди его наследников, зато прямой и обратный порядки можно перенести самым очевидным образом.

Дли заданного непустого леса зти два основных способа обхода можно определить, как показано ниже. Обход в прямом порядке Посетить корень первого дерева Пройти поддеревья первого дерева Пройти оставшиеся деревья Обход в обратном порядке Пройти поддеревья первого дерева Посетить корень первого дерева Пройти оставшиеся деревья Чтобы понять значение этих двух методов обхода, рассмотрим следующее обозначение древовидной структуры на основе вложенных скобок: (5) Оно соответствует лесу (1). При этом сначала дерево представляется символом нз его корня, а затем дается представление его поддеревьев. В результате представление непустого леса имеет вид заключенного в скобки списка представлений его деревьев, которые разделены запятыми.

Е<ши обход осуществляется (1) в прямом порядке, то узлы посещаются в последовательности А НСКР ЕНг з С, которая идентична обозначению (5), но без скобок и запятых. Прямой порядок является естественным способом перечисления узлов дерева: сначала указывается корень, а затем — его потомки. Если древовидная структура представлена с помощью строк с отступами, как на рис. 20, (с), то строки располагаются в прямом порядке.

В данной книге разделы нумеруются в прямом порядке (см. рис. 22), Таким образом, например, за разделом 2.3 следует раздел 2.3.1, а затем — разделы 2.3.2, 2.3.3, 2.3.4, 2.3А.1,..., 2.3.4,6, 2.3.5, 2.4 и т. д. Интересно отметить, что прямой порядок является освященным веками понятием династический порядок (йупаэ11с обжег). После смерти короля, герцога или графа соответствующий титул передается первому (т. е.

старшему) сыну, затем— наследникам первого сына и, если таковых нет, другим сыновьям семьи в том же порядке. (В Англии титул может точно так перейти и к дочери, но это возможно только после смерти (или при отсутствии) всех сыновей.) Теоретически родовой порядок всех узлов аристократических фамилий можно было бы переписать в прямом порядке. Тогда, рассматривая только живых представителей этих фамилий, можно получить порядок престолонаследования (за исключением тех, кто лишен этого права по закону об отречении от престола). В обратном порядке узлы (1) имеют последовательность В К САНЕ 1г С Р. Она аналогична прямому порядку, но при использовании обозначения на основе скобок, (6) каждый узел располагается после своих наследников, а не перед ними.

Определения прямого и обратного порядков обхода прекрасно согласуются с естественным соответствием деревьев и бинарных деревьев. поскольку полдеревья первого дерева отвечают левому бинарному поддереву, а оставшиеся деревья— правому бинарному поддереву. Сравнив эти определения с соответствующими определениями на с. 364, получим, что обход леса в прямом порядке выполняется точно так, как обход соответствующего бинарного дерева в прямом порядке.

Обход дерева в обратном порядке выполняется так же, как обход соответствующего бинарного дерева в симметричном порядке. Алгоритмы, рассмотренные в разделе 2.3.1, следовательно, могут быть использованы без изменений. (Обратите внимание, что обратный порядок обхода деревьев соответствует симметричному, а ке обратному порядку обхода бинарных деревьев. И это в определенной степени можно считать везением, поскольку, как было показано вьппе, довольно трудно выполнить обход бинарных деревьев в обратном порядке.) Вследствие этой эквивалентности впоследствии мы будем использовать обозначение рз для последователя узла Р при обрашном порядке обхода дерева; в то же время этот символ обозначает последователя узла Р при симмет1)ичном порядке обхода бинарного дерева.

В качестве примера непользования этих методов для решения практических задач рассмотрим некоторые операции с алгебраическими формулами. Такие формулы лучше всего представлять в виде древовидных структур, а не как одно- или двумерные конфигурации символов, и даже не как бинарные деревья. Например, формулу у = 31п(х+ 1) — а/х можно представить в виде дерева таким образом.

7) В левой части рисунка показано обычное дерево, подобное представленному на рис. 21, в котором бинарные операторы +, —, х, / и 7 (последннй символ обозначает возведение в степень) имеют по два полдерева, соответствующих их операндам. Унарный оператор 1и имеет одно поддерево, а переменные и константы являются концевыми узлами. В правой части рисунка показано эквивалентное правопрошитое бинарное дерево, включающее дополнительный узел у, который является заголовком списка этого дерева. Заголовок списка имеет вид, представленный условиями 2.3.1 — (8). Важно отметить, что, хотя дерево, показанное в левой части (7), внешне очень похоже на бинарное дерево, здесь оно рассматривается как обычное дерево и представлено в виде совершенно иного бинарного дерева, чем то, которое показано в правой части (7).

Программы дпя выполнения алгебраических операций можно было бы создать непосредственно на основе бинарных деревьев, т. е. на основе так называемого трехвдресного кода (слгее-а44геээ соде) представления алгебраических формул. Однако на практике при использовании древовидного представления алгебраических формул применяются некоторые упрощения, подобно представлениям (7), поскольку обход дерева в обратном порядке выполняется проще в обычном дереве.

При обходе узлов дерева в левой части (7) получим — х 3 1п + х 1 / а 3 * 1 + 1п х а х 2 х 2 для прямого порядка; (8) / — для обратного порядка. (9) Алгебраические выражения наподобие (8) и (9) имеют очень большое значение и называются польской системой обозначений, так как в виде (8) она впервые была использована польским логиком Яном Лукасевичем (зап лцказ~евч1сх). Выражение (8) является префиксным обозначением (ргебх па1абоп) формулы (7), а выраже. ние (9) — ее посгпфикснллм.рбозначением (розлдх по1аслоп). В следующих главах эта система обозначений будет рассмотрена подробнее, а здесь лишь отметим, что польская система обозначений непосредственно связана с основными способами обхода деревьев. Предположим, что узлы в древовидных структурах, используемых для представления алгебраических формул, имеют следующий вид в программах для компьютера М11а (10) (11) (12) (18) (14) (15) (16) (17) Р(х) .Р(а) Р(1п и) Р( — и) Р(и+ и) Р(и — и) Р(и х е) 1 О, где а в константа или переменная ф х Р(и)/и, где и — любая формула -Р( ) Р(и) + Р(и) Р(и) — Р(и) Р(и) х е+ и х Р(и) Здесь поля КЕТМК и ЕЕ1МК имеют обычное значение, а значение поля КТАС является отрицательным для связей-нитей (что соответствует КТАС = 1 в выражениях алгоритма).

Характеристики

Список файлов книги