Теорема А. Пусть

Ui,U2,...,Un И Ui,U2,...,U„

являются узлами бинарных деревьев Т и Т соответственно в прямом порядке обхода. Для любого узла и положим

1{и) = 1, если и имеет непустое левое поддерево, иначе 1{и) = 0; ц, г (и) = 1, если и имеет непустое правое поддерево, иначе г (и) =0;

Следовательно, Т и Т подобны тогда и только тогда, когда п = п и

1(и,) = Щ), гЮ=гЮ для1<;<п. (12)

Более того, деревья Т и Т эквивалентны тогда и только тогда, когда

info(uj) = info(u) для 1 < j < п. (13)

Обратите внимание, что /иг представляют собой дополнения к LTAG и RTAG в прошитом дереве. Эта теорема характеризует любую бинарную древовидную структуру на основании двух последовательностей нулей и единиц.

Доказательство. Ясно, что данное условие эквивалентности бинарных деревьев будет автоматически выполняться, если доказать заданное условие подобия. Более того, условия п = п и (12), конечно же, необходимы, так как соответствующие узлы подобных деревьев должны занимать одинаковые позиции при прямом порядке обхода. Следовательно, достаточно доказать, что деревья Т и Т подобны, если выполняется условие (12) и п = п. Доказательство осуществляется методом индукции по n с помощью следующего вспомогательного результата.

Лемма Р. Пусть Ui,U2,...,u„ являются узлами непустого бинарного дерева в прямом порядке обхода, а /(ы) = 1{и) -Ь г (и) - 1. Тогда

f{ui) + f{u2) + --- + f{Un) = -l и /(Ui) + --- + /(Ufc) >0, 1<к<п. (14)

Доказательство. Утверждение очевидно для n = 1. Если п > 1, бинарное дерево состоит из корня Ul и других узлов. Если f{ui) - О, то либо левое поддерево, либо правое поддерево является пустым, поэтому данное условие, очевидно, истинно по индукции. Если f{ui) = 1, предположим, что левое поддерево содержит щ узлов; далее, используя метод индукции, получаем

f{ui) + --- + fiuk)>0 для1< к <ni, /(ui) + --- + /(u„,+i) = 0, (15)

и условие (14) снова становится очевидным.

(С другими теоремами, аналогичными лемме Р, можно ознакомиться при обсуждении польской системы обозначений в главе 10.)

Для завершения доказательства теоремы А заметим, что она, очевидно, верна при n = 0. Если n > О, то из определения прямого порядка следует, что ui и ui являются соответствующими корнями этих деревьев и существуют такие П; и nj (размеры левого поддерева), что

«2, • • , "п,+1 и «2,..., ujj/i -левые поддеревья деревьев Г и Т;

и2 • • • 1 И !n - правые поддеревья деревьев Т и Т.

Доказательство этой теоремы можно завершить с помощью метода индукции, если показать, что п, = п,. При эТом возможны три таких случая:

если l{ui) = О, то п, = О nj;

если l{ui) = 1, r(ui) = О, то n, = n - 1 = nJ;

если l{ui) = r{ui) = 1, то по лемме Р можно найти такое наименьшее к > О, что f{ui) Н-----h f{uk) = 0; и тогда п, = fc - 1 = nJ (см. (15)).

Как следствие теоремы А, проверка эквивалентности или подобия двух прошитых бинарных деревьев может быть вьшолнена просто за счет прямого их обхода и проверки полей INFO и TAG. Некоторые интересные расширения теоремы А получены А. Я. Бликлом [А. J. Blikle, Bull, de iAcad. Polonaise des Sciences, Serie des Sciences Math., Astr., Phys., 14 (1966), 203-208]. Он рассмотрел бесконечный класс возможных порядков обхода, из которых только шесть (включая прямой порядок обхода) из-за их простых свойств были названы безадресными.

Завершим этот раздел описанием типичного алгоритма для бинарных деревьев, который копирует бинарное дерево в другие ячейки памяти.

Алгоритм С {Копирование бинарного дерева). Пусть HEAD - адрес заголовка списка бинарного дерева Т; таким образом, Т - левое поддерево HEAD, а LLINK(HEAD) - его адрес. Пусть NODE(U)-узел с пустым левым поддеревом. Этот алгоритм копирует Т, и копия становится левым поддеревом узла NODE(U). В частности, если узел NODE(U) является заголовком списка пустого бинарного дерева, алгоритм превращает пустое дерево в копию дерева Т.

С1. [Инициализация.] Установить Р <- HEAD, Q U. Перейти к шагу С4.

С2. [Есть ли что-либо справа?] Если NODE(P) имеет непустое правое поддерево, установить R < AVAIL и присоединить NODE(R) справа к узлу NODE(Q). (В начале шага С2 правое поддерево узла NODE(Q) пусто.)

СЗ. [Копирование INFO.] Установить INFO(Q) INFO(P). (Здесь INFO обозначает все части узла, которые следует копировать, за исключением связей.)

С4. [Есть ли что-либо слева?] Если NODE(P) имеет непустое левое поддерево, установить R AVAIL и присоединить NODE(R) слева к узлу NODE(Q). (В начале шага С2 левое поддерево узла NODE(Q) пусто.)

С5. [Продвижение вперед.] Установить Р Р*, Q 4- Q*.

Сб. [Проверка завершения.] Если Р = HEAD (или, что эквивалентно, если Q = RLINK (и), при условии, что NODE(U) имеет непустое правое поддерево), вьшолнение алгоритма прекращается; в противном случае перейти к шагу С2.

Этот простой алгоритм демонстрирует типичный пример использования метода обхода дерева. В данном виде он может применяться для прошитых, непрошитых или частично прошитых деревьев. Для выполнения шага С5 требуется вычислить прямых последователей Р* и Q*. Для непрошитых деревьев это обычно вьшолняется с помощью вспомогательного стека. Доказательство корректности алгоритма С представлено в упр. 29, а программа для компьютера MIX, соответствующая этому алгоритму для правопрошитого бинарного дерева, приводится в упр. 2.3,2-13. Для прошитых деревьев "присоединение" на шагах С2 и С4 вьшолняется с помощью алгоритма I.

в приведенных ниже упражнениях содержится довольно много интересных задач, имеющих отношение й. теме данного раздела.

хотя бинацные или дихотомические системы, в принципе, регулярны, они являются едва ли не самыми неестественными типами упорядочения,

которые только можно себе представить.

- ВИЛЬЯМ свэйнсон, А Treatise on the Geograptiy and Classification of Animals (1835)

УПРАЖНЕНИЯ

1. [01] Пусть INFO(P) в бинарном дереве (2) обозначает букву, которая хранится в узле NODE(P). Какой символ тогда хранится в узле INFO (LLINK (RLINK (RLINK (Т)))) ?

2. [и] Перечислите узлы бинарного дерева ® (а) в прямом порядке обхода; (Ь) в

симметричном порядке обхода; (с) в обратном порядке обхода.

3. [20] Справедливо ли следующее утверждение: "Концевые узлы бинарного дерева встречаются в одном и том же относительном порядке для прямого, симметричного и обратного обходов"?

► 4. [20] В данном разделе определяются три основных порядка обхода бинарного дерева. В дополнение к ним можно предложить еще один альтернативный способ обхода:

a) попасть в корень,

b) пройти правое поддерево,

c) пройти левое поддерево.

Далее это правило применяется рекурсивно для всех непустых поддеревьев. Имеет ли такой порядок какую-либо простую связь с тремя другими рассмотренными выще порядками?

5. [22] Узлы бинарного дерева можно идентифицировать последовательностью нулей и единиц, используя обозначения, подобные десятичной системе обозначений Дьюи для деревьев, следующим образом. Корень (если он существует) представляется последовательностью 1. Корни (если они существуют) левого и правого поддеревьев узла а соответственно представляются последовательностями qO и q1. Например, узел Н дерева (1) в данной системе обозначений выглядел бы как ШО (см. упр. 2.3-15).

Покажите, что с помощью такой системы обозначений было бы удобно описывать прямой, симметричный и обратный порядки обхода.

6. [М22] Допустим, что бинарное дерево имеет п узлов, которые в прямом порядке обхода обозначаются как ui иг •. Ип, а в симметричном порядке - как Up Up ... Ир„ Покажите, что перестановку pip2 ... р„ можно получить, передавая в стек последовательность 12... п, как в упр. 2.2.1-2. И наоборот, покажите, что любая перестановка piP2 .. Рп, которую можно получить с помощью стека, соответствует некоторому бинарному дереву.

7. [22] Покажите, что, зная прямой и симметричный порядки узлов бинарного дерева, можно восстановить структуру бинарного дерева. Можно ли это сделать, зная прямой и обратный (вместо симметричного) порядки или симметричный и обратный порядки?

8. [20] Найдите все бинарные деревья, узлы которых располагаются в одинаковой последовательности (а) как в прямом, так и в симметричном порядках; (Ь) как в прямом, так и в обратном порядках; (с) как в симметричном, так и в обратном порядках.

9. [М20] Сколько раз выполняются шаги Т1-Т5 при обходе бинарного дерева с п узлами согласно алгоритму Т в зависимости от п?