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