Новиков Ф.А. Дискретная математика для программистов (860615), страница 58
Текст из файла (страница 58)
Если трактовать открывающую скобкукак 1, а закрывающую — как 0, то последовательность скобок, содержащихся встроке, образует код дерева. Алгоритм очевидным образом проверяет выполнениеусловия (*), то есть проверяет допустимость этого кода.•ОБОСНОВАНИЕПример Строка a(b(d)(e))(c(f)(g)(h{i)))является естественной записью с помощью правильной скобочной структуры дерева на рис. 9.11, слева.9.3.5. Представление бинарных деревьевВсякое свободное дерево можно ориентировать, назначив один из узлов корнем.
Всякое ордерево можно произвольно упорядочить. Для потомков одногоузла (братьев) упорядоченного ордерева определено отношение старше-младше(левее-правее). Всякое упорядоченное дерево можно представить бинарным деревом, например, проведя правую связь к старшему брату, а левую — к младшемусыну. Таким образом, достаточно рассмотреть представление в программе бинарных деревьев. Это наблюдение объясняет, почему представлению бинарныхдеревьев в программах традиционно уделяется особое внимание при обучениипрограммированию.310Глава 9.
ДеревьяПример На рис. 9.11 приведены диаграммы упорядоченного и соответствующего ему бинарного деревьев.ЗАМЕЧАНИЕИз данного представления следует, что множество бинарных деревьев взаимно-однозначносоответствует множеству упорядоченных лесов упорядоченных ордеревьев. Действительно, в указанном представлении одиночному упорядоченному ордереву всегда соответствует бинарное дерево, у которого правая связь корпя пуста, а упорядоченному лесу —бинарное дерево, у которого правая связь корня не пуста.Обозначим через п(р) объем памяти, занимаемой представлением бинарного дерева, где р — число узлов.
Наиболее часто используются следующие представления бинарных деревьев:1. Списочные структуры: каждый узел представляется записью типа N, содержащей два поля (I и г) с указателями на левый и правый узлы и еще однополе г для хранения указателя на информацию об узле. Дерево представляется указателем на корень. Тип N обычно определяется следующим образом:N = record i : info; I,г :end record, где тип info считается заданным.Для этого представления п(р) = 3р.ЗАМЕЧАНИЕПоскольку в бинарном дереве, как и в любом другом, q = р - 1, то из 2р указателей,отводимых для хранения дуг, р+1 всегда хранит значение nil, то есть половина связейпе используется.9.3.
Представление деревьев в программах3112. Упакованные массивы: все узлы располагаются в массиве, так что все узлыподдерева данного узла располагаются вслед за этим узлом. Вместе с каждым узлом хранится индекс, узла, который является первым узлом правогоподдерева данного узла. Дерево Т обычно определяется следующим образом:Т : array [l..p] of record i : info, к : l..p end record, где тип info считаетсязаданным.
Для этого представления п(р) = 2р.3. Польская запись: аналогично, но вместо связей фиксируется «размеченнаястепень» каждого узла (например, 0 означает, что это лист, 1 — есть леваясвязь, но нет правой, 2 — есть правая связь, но нет левой, 3 — есть обе связи). Дерево Т определяется следующим образом: Т : array [l..p] of recordг: info, d : 0..3 end record, где тип info считается заданным. Для этого представления п(р) = 2р.
Если степень узла известна из информации, хранящейсяв самом узле, то можно пе хранить и степень. Такой способ представлениядеревьев называется польской записью и обычно используется для представления выражений. В этом случае представление дерева оказывается наиболеекомпактным: объем памяти п(р) = р.Пример Покажем, как выглядят в памяти бинарные деревья в разных представлениях. В приводимых ниже таблицах первая группа столбцов соответствуетполям списочных структур, вторая — упакованным массивам и третья — польской записи с явными размеченными степенями. Условные адреса — это целыечисла, а пустой указатель — 0.1.
Бинарное дерево па рис. 9.9, слева; считаем, что верхний узел содержит а,а нижний — Ь.Адрес12i 1 га 2 0Ь 0 0г ка 0Ь 0г dа 1Ь 02. Бинарное дерево на рис. 9.9, справа; считаем, что верхний узел содержит а,а нижний — Ь.Адрес12i 1 га 0 2Ь 0 0г ка 2Ь 0г dа 2Ъ 03. Бинарное дерево па рис. 9.7, слева.Адрес2г+а3*14512Г0034 5Ъ 0 0с 0 0г+ак305Ь 0с 0*г+аd*330Ь 0с 04.
Бинарное дерево на рис. 9.11, справа.г I г г k i dАдрес1а 2 0 а 0 a 12Ь 3 5 Ъ 5 b 33d 0 4 d 4 d 24е 0 0 е 0 e 05с 6 0 с 0 с 16f 0 7 f 7 f 279 0 8 9 8 9 28h 9 0 h 0 h 1i 0 0 i 0 i 099.3.6. Обходы бинарных деревьевБольшинство алгоритмов работы с деревьями основаны па обходах. Возможныследующие основные обходы бинарных деревьев.Прямой (префиксный, левый) обход:Внутренний (инфиксный, симметричный) обход:Концевой (постфиксный, правый) обход:попасть в корень,обойти левое поддерево,обойти правое поддерево.обойти левое поддерево,попасть в корень,обойти правое поддерево.обойти левое поддерево,обойти правое поддерево,попасть в корень.Кроме трёх основных, возможны еще три соответствующих обхода, отличающихся порядком рассмотрения левых и правых поддеревьев.
Этим исчерпываютсяобходы, если в представлении фиксированы только дуги, ведущие от отцов ксыновьям.ЗАМЕЧАНИЕЕсли кроме связей «отец-сын» в представлении есть другие связи, то возможны и другие (более эффективные) обходы. Деревья, в которых пустые поля / и г в структуре Nиспользуются для хранения дополнительных связей, называются прошитыми деревьями.Пример Концевой обход дерева выражения а + Ь*с дает обратную польскуюзапись этого выражения: abc * +.ОТСТУПЛЕНИЕПольская запись выражений (прямая или обратная) применяется в некоторых языкахпрограммирования непосредственно и используется в качестве внутреннего представления программ во многих трансляторах и интерпретаторах.
Причина заключается в том, чтотакая форма записи допускает очень эффективную интерпретацию (вычисление значения)9.4. Деревья сортировки313выражений. Например, значение выражения в обратной польской записи может быть вычислено при однократном просмотре выражения слева направо с использованием одногостека. В таких языках, как Forth и PostScript, обратная польская запись используется какосновная.9.3.7.
Алгоритм симметричного обходабинарного дереваРеализация обходов бинарного дерева с помощью рекурсивных процедур невызывает затруднений. В некоторых случаях из соображений эффективностиприменение явной рекурсии оказывается нежелательным. Следующий очевидный алгоритм реализует наиболее популярный симметричный обход без явнойрекурсии, по с использованием стека.Алгоритм 9.6 Алгоритм симметричного обхода бинарного дереваВход: бинарное дерево, представленное списочной структурой, г — указатель накорень.Выход: последовательность узлов бинарного дерева в порядке симметричногообхода.Т : = 0 ; р: = г { вначале стек пуст и р указывает на корень дерева }М : { анализируем узел, на который указывает р }if р = nil thenif Т = 0 thenstop { обход закончен }end ifpT { левое поддерево обойдено }yield p { очередной узел при симметричном обходе }р: =р.г { начинаем обход правого поддерева }elseр —> Т { запоминаем текущий узел...}р: = р.1 { ...
и начинаем обход левого поддерева }end ifgoto М9.4. Деревья сортировкиВ этом разделе обсуждается одно конкретное применение деревьев в программировании, а именно деревья сортировки (также называемые деревьями упорядочивания). При этом рассматриваются как теоретические вопросы, связанные, например, с оценкой высоты деревьев, так и практическая реализация алгоритмов,а также целый ряд прагматических аспектов применения деревьев сортировкии некоторые смежные вопросы.314Глава 9. Деревья9.4.1.
Ассоциативная памятьВ практическом программировании для организации хранения данных и доступак ним часто используется механизм, который обычно называют ассоциативнойпамятью. При использовании ассоциативной памяти данные делятся на порции (называемые записями), и с каждой записью ассоциируется ключ. Ключ —это значение из некоторого линейно упорядоченного множества, а записи могутиметь произвольную природу и различные размеры. Доступ к данным осуществляется по значению ключа, которое обычно выбирается простым, компактными удобным для работы.ПримерыАссоциативная память используется во многих областях жизни:1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
