Д. Кнут - Искусство программирования том 1 (1119450), страница 91
Текст из файла (страница 91)
(12) Более, того, деревья Т и Т' эквивалентны тогда и только тогда, когда 1п(о(и ) =!пГо(и') для 1 < л < п. (13) Обратите внимание, что 1 и г представляют собой дополнения к 1!АО и к!АО в прошитом дереве. Эта теорема характеризует любую бинарную древовидную структуру на основании двух последовательностей нулей и единиц. Доказательство. Ясно, что данное условие эквивалентности бинарных деревьев будет автоматически выполняться, если доказать заданное условие подобия. Более того, условия п = и' и (12), конечно же, необходимы, так как соответствующие узлы подобных деревьев должны занимать одинаковые позиции при прямом порядке обхода. Следовательно, достаточно доказать, что деревья Т и Т' подобны, если выполняется условие (12) и и = п'.
Доказательство осуществляется методом индукции по и с помощью следующего вспомогательного результата. Лемма Р. Пусть иы ию..., и„являются узламя непустого бинарного дерева в прямом порядке обхода, а 1(и) = 1(и) + г(и) — 1. Тогда 1'(и!) + 1'(иа)+ + 1(ил) = — 1 и у'(и!) + + 1(иь) > О, 1 < А < п.
(14) Ди!) + . + Диь) > 0 для 1 < А < пь ((и!) + + ((и„пы) = О, (15) и условие (14) снова становится очевидным. э (С другими теоремами, аналогичными лемме Р, можно ознакомиться при обсуждении польской системы обозначений в главе 10.) Для завершения доказательства теоремы А заметим, что она, очевидно, верна при и = О. Если п > О, то из определения прямого порядка с!!едует, что и! и и', являются соответствующими корнями этих деревьев и существуют такие п~ и п~~ (размеры левого поддерева), что иш ..,,и„, и ил,...,и'„+! — левые поддеревья деревьев Т и Т', ! иь +„, .., и„и и'„+„..., и'„— правые поддеревья деревьев Т и Т'. Доказательства.
Утверждение очевидно для и = 1. Если и > 1, бинарное дерево состоит нз корня и1 и других узлов. Если г'(и!) = О, то либо левое поддерево, либо правое поддерево является пустым, поэтому данное условие, очевидно, истинно по индукции. Если у(и!) = 1,предположим, что левое поддерево содержит ьл узлов; далее, используя метод индукции, получаем Доказательство этой теоремы можно завершить с помощью метода индукции, если показать, что и = п[. При этом возможны три таких случая: если !(и~) = О, то п~ — — 0 ч и[', если )(и~) = 1, г(и~) = О, то и, = и — 1 = и[., если!(и~) = г(и,) = 1, то по лемме Р можно найти такое наименьшее А > О, что ,((и~)+. +1(иь) = 0; и тогда п, = А — 1= и, '(см.
(15)). в Как следствие теоремы А, проверка эквивалентности или подобия двух прошитых бинарных деревьев может быть выполнена просто за счет прямого их обхода и проверки полей 1МРО и ТАО. Некоторые интересные расширения теоремы А получены А. Я. Бликлом [А. д. В1(к1е, Вп!!. с(е 1'Асвк), Ро!опазве <Ьв Вс!епсев, БеНе бев Бс!епсев МагЬ., Авве., Рагун., 14 (1966), 203-208]. Он рассмотрел бесконечный класс возможных порядков обхода, из которых только шесть (включая прямой порядок обхода) из-за их простых свойств были названы безадресными. Завершим этот раздел описанием типичного алгоритма для бинарных деревьев, который копирует бинарное дерево в другие ячейки памяти.
Алгоритм С (Копирование бинарного дерева). Пусть НЕАР— адрес заголовка списка бинарного дерева Т: таким образом, Т вЂ лев поддерево НЕАР, а 551МК(НЕАР)— его адрес. Пусть МОРЕ(О) †уз с пустым левым поддеревом. Этот алгоритм копирует Т, и копия становится левым поддеревом узла МОРЕ(О). В частности, если узел МОРЕ(О) является заголовком списка пустого бинарного дерева, алгоритм превращает пустое дерево в копию дерева Т.
С1. [Инициализация.] Установить Р е- НЕАР, Ц е- О. Перейти к шагу С4. С2. [Есть ли что-либо справау] Если МОРЕ(Р) имеет непу стае правое поддерево, установить Н ~ АЧА15 и присоединить МОРЕ®) справа к узлу МОРЕ(Ц). (В начале шага С2 правое поддерево узла МОРЕ(Ц) пусто.) СЗ. [Копирование 1МРО.] Установить 1МРО(Ц) е- 1МРО(Р).
(Здесь 1МРО обозначает все части узла, которые следует копировать, за исключением связей.) С4. [Есть ли что-либо слеваУ] Если МОРЕ(Р) имеет непустое левое поддерево, установить Н с.= АЧА15 и присоединить МОРЕ(Н) глева к узлу МОРЕ(Ц). (В начале шага С2 левое поддерево узла МОРЕ(Ц) пусто.) С5. [Продвижение вперед.] Установить Р е- Р*, Ц е- Ц*. С6. [Проверка завершения.] Если Р = НЕАР (или, что эквивалентно, если Ц Н51МК(О), при условии, что МОРЕ(Р) имеет непустое правое поддерево), выполнение алгоритма прекращается; в противном случае перейти к шагу С2. ! Этот простой алгоритм демонстрирует типичный пример использования метода обхода дерева.
В данном виде он может применяться для прошитых, непрошитых или частично прошитых деревьев. Для выполнения шага С5 требуется вычислить прямых последователей Рз и Цж Для непрошитых деревьев это обычно выполняется с помощью вспомогательного стека. Доказательство корректности алгоритма С представлено в упр. 29, а программа для компьютера Н11, соответствующая этому алгоритму для правопрошитого бинарного дерева, приводится в упр. 2.3.2 — 13. Для прошитых деревьев "присоединение" на шагах С2 и С4 выполняется с помощью алгоритма 1. В приведенных ниже упражнениях содержится довольно много интересных задач, имеющих отношение х теме данного раздела.
Хотя бннадные нлн дикотомнческне системы, в принципе, ОЕгупявны, онн являются едва лн не самыми неестественными типами упорядочения, которые только можно себе представить. — Омззыяав с89Ймсом, А тгеаг?ве оп гпе беодгаопу апб ставя?бсаг?оп ог Атта1в (1835) УПРАЖНЕНИЯ 1. [01] Пусть |ИРО(Р) в бинарном дереве (2) обозначает букву, йоторая хранится в узле ИООЕ(Р) .
Какой символ тогда хранится в узле 1ИРО 0 Ь?ИИ(ИЬ1ИК(21.1ИК(Т) ) ) )? ! 2. [11] Перечислите узлы бинарного дерева г з (а) в прямом порядке обхода; (Ь) в 4 5 б 7 симметричном порядке обхода; (с) в обратном порядке обхода. 3. [20] Справедливо ли следующее утверждение: "Концевые узлы бинарного дерева встречаются в одном и том же относительном порядке для прямого, симметричного и обратного обходов"? 4. [20] В данном разделе определяются три основных порядка обхода бинарного дерева.
В дополнение к ним можно предложить еще один альтернативный способ обхода: а) попасть в корень, Ь) пройти правое поддерево, с) пройти левое поддерево. Далее это правило применяется рекурсивно для всех непустых поддеревьев. Имеет ли такой порядок какую-либо простую связь с тремя другими рассмотренными выше поряд- ками? б. [22] Узлы бинарного дерева можно идентифицировать последовательностью нулей и единиц, используя обозначения, подобные десятичной системе обозначений Дьюи для деревьев, следующим образом. Корень (егли он существует) представляется последовательностью 1.
Корни (если они существуют) левого и правого поддеревьев узла о соответственно представляются последовательностями аО и а1. Например, узел Н дерева (1) в данной системе обозначений выглядел бы как 1110 (см. упр, 2.3 — 15). Покажите, что с помощью такой системы обозначений было бы удобно описывать прямой, симметричный и обратный порядки обхода. 6. [М22] Допустим, что бинарное дерево имеет и узлов, которые в прямом порядке обхода обозначаются как и~ из...
и, а в симметричном порядке — как игн яр~... ир„. Покажите, что перестановку р~рэ р„можно получить, передавая в стек последовательность 12... и, как в упр. 2.2.1-2. И наоборот, покажите, что любая перестановка р~рг ..р, которую можно получить с помощью стека, соответствует некоторому бинарному дереву. 7. [22] Покажите, что, зная прямой и симметричный порядки узлов бинарного дерева, можно восстановить структуру бинарного дерева. Можно ли это сделатгч зная прямой и обратный (вместо симметричного) порядки или симметричный и обратный порядки? 8. [20] Найдите все бинарные деревья, узлы которых располагаются в одинаковой последовательности (а) как в прямом, так и в симметричном порядках: (Ъ) как в прямом, так и в обратном порядках; (с) как в симметричном, так и в обратном порядках.
9. [М20] Сколько раз выполняются шаги Т1-Тб при обходе бинарного дерева с и узлами согласно алгоритму Т в зависимости от и? ь 10. [ЕО] Какое максимальное количество элементов может находиться в стеке во время выполнения алгоритма Т при работе с деревом с и узлами? (Ответ на этот вопрос очень важен при распределении памяти, когда стек располагается в последовательных ячейках памяти.) 11. [ИМА1] Найдите среднее значение для наибольшего размера стека при выполнении алгоритма Т в зависимости от числа узлов и при условии, что все бинарные деревья с и узлами рассматриваются как равновероятные. 12. [22] Напишите алгоритм, аналогичный алгоритму Т, который совершает обход бинарного дерева в прямом порядке, и докажите его корректность. ь 13.
[24] Напишите алгоритм, аналогичный алгоритму Т, который совершает обход бинарного дерева в обрашнам порядке, и докажите его корректность. 14. [22] Покажите, что если бинарное дерево с и узлами имеет вид (2), то общее количество Л-связей в таком представлении можно выразить с помощью простой функции от и. Эта функция не зависит от формы дерева 15. [)б] В прошитом представлении дерева (10) каждый узел, за исключением заголовка списка, имеет в точности одну связь, которая указывает на нее сверху вниз, а именно— связь от родителя этого узла. Некоторые узлы также имеют связи, которые указывают на них снизу вверх.
Например, узел С имеет два указателя, направленных на него снизу вверх, а узел Š— только один.". Существует ли простая зависимость между количеством связей, указывающих на данный узел, и другими основными свойствами узла? (Это нужно для того, чтобы при изменении структуры дерева знать количество связей, указывающих на узел.) ь 16. [Ей] Схемы, представленные на рис 24, позволяют предложить следующие интуитивно понятные правила расположения узла МОВЕ(Цэ) в бинарном дереве по отношению к узлу МОВЕ(Ц).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
