Д. Кнут - Искусство программирования том 1 (1119450), страница 93
Текст из файла (страница 93)
Оно называешься естественным соответствием (вагита( соггеэропйепсе) между лесом и бинарными деревьями. В частности, оно задает соответствие между деревьями и особым классом бинарных деревьев, а именно — между бинарными деревьями с корнем, но без правого поддерева. (При этом можно было бы слегка изменить точку зрения и допустить, что корень дерева соответствует заголовку списка бинарного дерева. В таком случае получим взаимно однозначное соответствие между деревьями с п + 1 узлами и бинарными деревьями с п узлами.) Пусть г' = (ТыТш...,Т„) — -некоторый лес деревьев. Тогда бинарное дерево В(г'), соответствующее г', можно строго определить следующим образом. а) Если п = О, то В(г') пусто.
Ь) Если и ) О, то корень В(г) является корнем (Т,); В(Т1 ы Тки ... Тт) является левым поддеревом дерева В(г'), где Т1 ы Тш,.,,, Т, — поддеревья корня (Т,); В(Тш..., Т„) является правым поддеревом дерева В(Г). Эти правила строго определяют приведение схемы (1) к схеме (3). Иногда удобно изобра»~ать схему бинарного дерева в виде (2), без поворота на 45'. Тогда соответствующее виду (1) прошитое (йгеаНед) бинарное дерево будет выглядеть так: (4) (Ср. с рис.
24, повернув его на 45'.) Обратите внимание на то, что правые связнннто проходят от крайнего справа ребенка семья к его родителю. Левые связи-нити не имеют такой естественной интерпретации из-за отсутствия симметрии между левой и правой сторонами, Представленные в предыдущем разделе идеи обхода можно теперь применить к лесу (т. е. к деревьям). Хотя простой аналогии симметричного порядка обхода здесь нет из-за отсутствия очевидного места вставки корня среди его наследников, зато прямой и обратный порядки можно перенести самым очевидным образом. Для заданного непустого леса эти два основных способа обхода можно определить, как показано ниже. Обход в прямом порядке Посетить корень первого дерева Пройти поддеревья первого дерева Пройти оставшиеся деревья Обход в обратном порядке Пройти поддеревья первого дерева Посетить корень первого дерева Пройти оставшиеся деревья Чтобы понять значение этих двух методов обхода, рассмотрим следующее обозначение древовидной структуры на основе вложенных скобок: (Л(В,С(К)), 11(Е(Н), Г(У), а)).
(5) ((В, (К)С)А, ((Н)Е, (1)Р; С).0), (6) каждый узел располагается после своих наследников, а не перед ними. Определения прямого и обратного порядков обхода прекрасно согласуются с естественным соответствием деревьев и бинарных деревьев, поскольку поддеревья первого дерева отвечают левому бинарному поддереву, а оставшиеся деревья— правому бинарному поддереву. Сравнив эти определения с соответствующими определениями на с. 364, получим, что обход леса в прямом порядке выполняется точно ншк, как обход соответствующего бинарного дерева в прямом порядке.
Обход дерева в обратном порядке выполняется так же, как обход соответствующего бинарного дерева в симметричном порядке. Алгоритмы, рассмотренные в разделе 2.3.1, следовательно, могут быть использованы без изменений. (Обратите внимание, что обратный порядок обхода деревьев соответствует симметричному, а не обратному порядку обхода бинарных деревьев. И это в определенной степени можно считать везением, поскольку, как было показано выше, довольно трудно выполнить обход бинарных деревьев в обратном порядке.) Вследствие этой эквивалентности впоследствии мы будем использовать обозначение Рэ для последователя узла Р при Оно соответствует лесу (1). При этом сначала дерево представляется символом из его корня, а затем дается представление его поддеревьев. В результате представление непустого леса имеет вид заключенного в скобки списка представлений его деревьев, которые разделены запятыми.
Если обход осуществляется (1) в прямом порядке, то узлы посещаются в последовательности А ВСКИ ЕНг 10, которая идентична обозначению (5), но без скобок и запятых. Прямой порядок является естественным способом перечисления узлов дерева; сначала указывается корень, а затем — его потомки. Если древовидная структура представлена с помощью строк с отступами, как на рис. 20, (с), то строки располагаются в прямом порядке. В данной книге разделы нумеруются в прямом порядке (см. рис. 22).
Таким образом, например, за разделом 2.3 следует раздел 2.3.1, а затем — разделы 2.3.2, 2.3.3, 2.3.4, 2.3.4.1,..., 2.3.4.6, 2.3.5, 2.4 и т. д. Интересно отметить, что прямой порядок является освященным веками понятием династический порядок (Аупаэбс огас). После смерти короля, герцога или графа соответствующий титул передается первому (т. е. старшему) сыну, затем— наследникам первого сына и, если таковых нет, другим сыновьям семьи в том же порядке. (В Англии титул может точно так перейти и к дочери, но это возможно только после смерти (или при отсутствии) всех сыновей.) Теоретически родовой порядок всех узлов аристократических фамилий можно было бы переписать в прямом порядке. Тогда, рассматривая только живых представителей этих фамилий, можно получить порядок преснюлонаследоеанил (за исключением тех, кто лишен этого права по закону об отречении от престола).
В обратном порядке узлы (1) имеют последовательность ВКСА НЕ уг СЮ. Она аналогична прямому. порядку, но при использовании обозначения на основе скобок, обратном порядке обхода дерева; в то же время этот символ обозначает последователя узла Р при симметричном порядке обхода бинарного дерева.
В качестве примера эгспользования этих методов для решения практических задач рассмотрим некоторые операции с алгебраическими формулами. Такие формулы лучше всего представлять в виде древовидных структур, а не как одно- или двумерные конфигурации симнолов, и даже не как бинарные деревья. Например, формулу у = 3 1п(х + 1) — а/хз можно представить в виде дерева таким образом, 7) + !и Алгебраические выражения наподобие (8) и (9) имеют очень большое значение и называются польской системой обозначений, так как в виде (8) она впервые была В левой части рисунка показано обычное дерево, подобное представленному на рис.
21, в котором бинарные операторы +, —, х, / и 7 (последний символ обозначает возведение в степень) имеют по два поддерева, соответствующих их операндам. Унарный оператор !и имеет одно поддерево, а переменные и константы являются концевыми узлами. В правой части рисунка показано эквивалентное правопрошитое бинарное дерево, включающее дополнительный узел у, который является заголовком списка этого дерева.
Заголовок списка имеет вид, представленный условиями 2.3.1-(8). Важно отметить, что, хотя дерево. показанное в левой части (7), внешне очень похоже на бинарное дерево, здесь оно рассматривается как обычное дерево и представлено в виде совершенно иного бинарного дерева, чем то, которое показано в правой части (7). Программы для выполнения алгебраических операций можно было бы создать непосредственно на основе бинарных деревьев, т.
е. на основе так называемого трехадресного кода (спгее-аббгеээ соде) представления алгебраических формул. Однако на практике при использовании древовидного представления алгебраических формул применяются некоторые упрощения, подобно представлениям (7), поскольку обход дерева в обратном порядке выполняется проще в обычном дереве. При обходе узлов дерева в левой части (7) получим — х 3 !и х 1 / а 7 х 2 для прямого порядка; (8) 3 х 1 + х а х 2 7 / — для обратного порядка.
(9) использована польским логиком Яном Лукасевичем (Зап Ьцкзз1еичсх). Выражение (8) является ирефикснмм обозначением (ргебх по1апоп) формулы (7), а выражение (9) — се аостфикснммобозначением (роз(йх по1асвоп). В следующих главах эта система обозначений будет рассмотрена подробнее, а здесь лишь отметим, что польская система обозначений непосредственно связана с основными способами обхода деревьев. Предположим, что узлы в древовидных структурах, используемых для представления алгебраических формул, имеют следующий вид в программах для компьютера И1ус (10) (11) (12) (13) (14) (15) (16) (17) Р(х) Р(а) Р(1п и) Р(-и) Р(и + о) Р(и — и) Р(и х о) 1 О, где а в константа или переменная ф х Р(и)/и, где и — любая формула †.Р(и) Р(и) + Р(о) Р(и) — Р(о) Р(и) х о+ и х Р(о) Здесь поля ЕЕ1аК и Е11ИК имеют обычное значение, а значение поля ЕТАС является отрицательным для связей-нитей (что соответствует ЕТАС = 1 в выражениях алгоритма).
Поле ТУРЕ используется для того, чтобы можно было различать узлы разных типов. Например, ТУРЕ = О означает, что узел представляет константу, а поле 1ИРО содержит ес значение; ТУРЕ = 1 означает, что узел представляет переменную, а поле 1МГО содержит ее пятибуквенное имя; ТУРЕ ) 2 означает, что узел представляет оператор, а поле 1аРО содержит символьное имя этого оператора, т. е. значения ТУРЕ = 2, 3, 4..... используются для обозначения операторов +, —, к, / и т. д. Здесь нас меньше всего будет интересовать вопрос, как древовидная структура представлена в памяти компьютера, поскольку эта тема очень подробно анализируется в главе 10.
Предположим лишь, что дерево уже размещено в памяти компьютера, и отложим на потом все вопросы, связанные с операциями ввода и вывода. Рассмотрим классический пример выполнения алгебраических преобразований, а именно — поиск производной некоторого выражения как функции от х. Программы алгебраического дифференцирования, которые появились еще в 1952 году, были в числе первых программ для символьных вычислений. На примере процесса дифференцирования можно проиллюстрировать многие методы алгебраических преобразований. к тому же он имеет большое практическое значение для выполнения теоретических расчетов в различных областях науки и техники.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
