Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 116
Текст из файла (страница 116)
Приведенный ниже алгоритм описывает процедуру обхода дерева в центрированном порядке (ОЦП). Обозначим левого сына вершины о аббревиатурой лс(о), а правого сына вершины о — аббревиатурой пс(о). Алгоритм обхода дерева в центрироваином порядке — ОЦП(корень) (1) Если лс(корень) существует, то ОЦП(лс(корень)). (2) Обработать(корень).
(3) Если пс(корень) существует, то ОЦП(пс(корень)). Рассмотрим дерево, изображенное на рис. 15.41. Начнем с ОЦП(+); первая инструкция вызывает ОЦП(х). Первая инструкция команды в ОЦП(х) вызывает РАЗДЕЛ тб.4. Обход бинарных деревьев 661 ОЦП(А). Поскольку А не имеет левого сына, то переходим к шагу 2 команды ОЦП(А) и обрабатывем (печатаем) А. Переходим к шагу 3 в ОЦП(А) и, поскольку ОЦП(А) не имеет правого сына, обработка ОЦП(А) закончена, и мы возвращаемся к шагу 2 в ОЦП(х). Здесь обрабатывается (печатается) х, а на шаге 3 вызывается ОЦП(В). Заметим, что результатом вызова ОЦП(А) была обработка (печать) листа А и возврат к родителю.
Поэтому впредь, если имеется ОЦП(Ь), где Ь вЂ” лист, то три шага соответствующего алгоритма будем сокращенно описывать как обработать лист Е. Используя это обозначение, печатаем В и возвращаемся к ОЦП(х). Теперь выполнена команда "обработать" (напечатать) Ах В. Команда ОЦП(х) выполнена, поэтому возвращаемся к ОЦП(+). (К настоящему моменту общая концепция уже вполне ясна, в дальнейшем будем говорить просто "обработать", понимая под этим "печатать". Находясь на шаге 2 в ОЦП(+), обрабатываем + и переходим к шагу 3 в ОЦП(+).
На этом этапе вызываем команду ОЦП( —:). На первом шаге ОЦП(ие) вызываем ОЦП(С), обрабатываем лист С и возвращаемся на шаг 2 в ОЦП( —:). Теперь обрабатываем +, после чего уже обработано А х В + С -: . Возвращаемся на шаг 3 в ОЦП( —:) и вызываем ОЦП( — ). На шаге! в ОЦП( — ) вызываем ОЦП(Р) и обрабатывем лист Р. Затем возвращаемся на шаг 2 в ОЦП( — ) и вызываем ОЦП(Е).
Обрабатываем лист Е, после чего возвращаемся к команде ОЦП( — ). Однако, команда ОЦП( — ) уже выполнена, поэтому возвращаемся к ОЦП( —:). Но эта команда тоже закончена, поэтому возвращаемся к ОЦП(+). Наконец, в завершение всего процесса выполняем команду ОЦП(+). Итак, получено выражение АхВ+С-;Р— Е. Е, Рис. 15.42 Это выражение, согласно изложенному в разделе 5.5, имеет инфиксную запись.
К сожалению, в отсутствие скобок выражение в том виде, в каком получено, не имеет смысла. Если вспомнить содержание раздела 5.5, то именно такая ситуация была основанием для перехода к префиксной (польской) или постфнксной (польской инверсной) записи выражений.
К счастью, два следующих способа обхода бинарных деревьев порождают именно такие формы записи выражений. Следует отметить, что инфиксный способ обхода в применении к бинарному дереву поиска дает обработку элементов в алфавитном порядке. Теперь рассмотрим обход в прямом порядке. Такой обход осуществим, например, для дерева, изображенного на рис. 15А2, где о — бинарная операция над выраже- О пнями Е, и Ез.
Эту операцию будем обрабатывать (или печатать) как оЕ,Ез. В результате получим выражение в префнксной форме. Такая форма записи широко используется в логике и хороша тем, что в ней не используются скобки. Приведенный ниже алгоритм описывает процедуру обхода в прямом порядке (ОПП). Как и раньше, будем сокращенно обозначать левого сына вершины и аббревиатурой лс(и), а правого сына вершины и — аббревиатурой пс(о). 662 ГПАВА 15. Деревья Алгоритм обхода дерева в прямом порядке — ОПП(корень) (1) Обработать(корень). (2) Если лс(корень) существует, то ОПП(лс(корень)). (3) Если пс(корень) существует, то ОПП(пс(корень)). Снова рассмотрим дерево (рис.
!5АЗ), Начнем с ОПП(+); первая инструкция обрабатывает +. Шаг 2 вызывает ОПП(х). Первая инструкция ОПП(х) обрабатывает х. Затем вторая инструкция вызывает (А). На шаге ОПП(А) обрабатываем А. На этом этапе уже обработано +хА. Поскольку А не имеет левого сына, переходим к шагу 3 в ОПП(А); так как нет и правого сына, возвращаемся к ОПП(х).
Опять замечаем, что, как и в случае ОЦП(А), результатом вызова ОПП(А) является обработка (печать) листа А и возврат к родителю. Поэтому впредь, если имеется ОПП(Ь), где 5 — лист, то три шага соответствующего алгоритма будем сокращенно описывать как обработать лист Е. Находясь на шаге 3 в ОПП(х), вызываем ОПП(В). Обрабатываем лист В и возвращаемся к ОПП(х). Это завершает ОПП(х), поэтому возвращаемся к ОПП(+). К этому моменту обработано (уже напечатано) +х АВ. Затем на шаге 3 в ОПП(+) вызываем ОПП(+). Первый шаг ОПП( —:) обрабатывает +. Второй шаг вызывает ОПП(С).
Обрабатываем лист С и возвращаемся на шаг 3 в ОПП(+). Эта инструкция вызывает ОПП( — ). Первый шаг в ОПП( — ) обрабатывает —. Шаг 2 вызывает ОПП(Р). Обрабатываем лист Р и возвращаемся на шаг 3 в ОПП( — ). На данном этапе уже обработано + х АВ+С вЂ” Р. Шаг 3 в ОПП( — ) вызывает ОПП(Е). Обрабатываем лист Е и возвращаемся к ОПП( — ). Но ОПП( — ) завершено, поэтому возвращаемся к ОПП( —:). Однако, ОПП( —:) также завершено, поэтому возвращаемся к ОПП(+). Наконец, ОПП(+) тоже завершен, и мы получаем результат +х АВяьС вЂ” РЕ, который, согласно изложенному в разделе 5.5, выражен префиксной, или польской записью. РАЗДЕП Гб.4. Обход бинарных деревьев 663 /' Е, Рис.
И44 И, наконец, рассмотрим обход в обратном порядке. Этот обход осуществим для дерева, изображеного на рис. 15.44, где о — бинарная операция над выражениями Е1 и Ез, которую будем обрабатывать (или печатать как ЕгЕзо. В результате получим выражение в постфиксной, или лольской инверсной записи, как описано в разделе 5.5. Всякий, кто пользовался калькулятором, знаком с постфиксной, или польской инверсной записью. Она обладает тем преимушеством, что позволяет без скобок, чем и объясняется ее популярность. Приведенный ниже алгоритм описывает процедуру обхода в обратном порядке (ООП).
Как и раньше, будем сокращенно обозначать левого сына вершины и аббревиатурой лс(и), а правого сына вершины и — аббревиатурой пс(и). Алгоритм обхода дерева в обратном порядке — ООП(корень) (1) Если лс(корень) существует, то ООП(лс(корень)). (2) Если пс(корень) существует, то ООП(пс(корень)). (3) Обработать(корень), Снова рассмотрим дерево, изображенное на рисунке !5.45. Начинаем с ООП(+); первая инструкция вызывает ООП(х). Первая инструкция в ООП(х) вызывает ООП(А).
Поскольку А не имеет левого сына, переходим к шагу 2 в ОПП(А). Но так как нет и правого сына, переходим к шагу 3 в ОПП(А), на котором обрабатываем А и возвращаемся к ООП(х). Опять замечаем, что, как и в случае ОЦП(А) и ОПП(А), результатом вызова команды ООП(А) является обработка (печать) листа А и возврат к родителю. Поэтому впредь, если имеется команда ООП(Е), где Ь вЂ” лист, то три шага соответствующего алгоритма будем сокращенно описывать как обработать лист 1., Находясь на шаге 2 команды ООП(х), вызываем ООП(В). Обрабатываем лист В и возвращаемся на шаг 3 в (х). Обрабатываем х и, поскольку это завершает ООП(х), возвращаемся к ООП(+). На этом этапе имеем обработанным АВ х.
Теперь мы на шаге 2 в ООП(+) вызываем ООП(+). Первый шаг ООП(+) вызывает ООП(С). Обрабатываем лист С и возвращаемся на шаг 2 в ООП(+). Эта 664 ГЛАВА 15. Деревья инструкция вызывает ООП( — ). Певый шаг команды ООП( — ) вызывает ООП(Р). Обрабатываем лист Р и возвращаемся на шаг 2 в ООП( — ). Второй шаг в ООП( — ) вызывает ООП(Е). Обрабатываем Е и возвращаемся на шаг 3 в ООП( — ). Обрабатываем — и возвращаемся на шаг 3 в ООП(+).
На этом этапе результатом обработки является АВ х СРŠ—. На шаге 3 в ООП( —:) обрабатываем + и возвращаемся на шаг 3 в (+). Обрабатываем + и завершаем процесс. В качестве результата обработки имеем АВ х СРŠ— —:+, т.е. выражение, преобразованное в постфиксиую запись. Умение обходить дерево дает возможность легко устанавливать изоморфность двух деревьев. Проходя два дерева одновременно, можно проверять наличие вершины у одного дерева при условии наличия ее у другого. При одновременном прохождении двух деревьев обработка вершин будет означать проверку обоих деревьев на наличие соответствующих вершин. В данном случае для прохождения деревьев представляется разумным использовать префиксный обход, так как это позволяет не интересоваться наличием сыновей, если один из родителей отсутствует. При обработке вершины У будем присваивать переменной наличие(У) значение Х, если вершина У отсутствует, и значение У, если вершина имеется.
Последующая проверка соответствующих вершин покажет, что если для одной вершины значение переменной наличие(У) равно У, а для другой вершины оно равно )ч', то два дерева не изоморфны. Введем переменную, названную Изо, которая будет принимать значения Т и Е. Изначально ей присваивается значение Т, но если на каком-то этапе выявляется, что деревья не изоморфны, то этой переменной присваивается значение Е. Итак, имеем следующий алгоритм для двух деревьев Т, и Тз с корнями г, и гз соответственно.
Пусть Изо = Т. Алгоритм проверки изоморфности бинарных деревьев — ИБД(гы гз) (1) Обработать г1 и гз. (2) Если наличие(г~) = У и наличие(гз) = Ю или наличие(гг) = )ч' и наличие(гз) = У, то Изо = Е. (3) Если Изо = Е, то завершить ИБД(тыгз). (4) Если наличие(гз) = У и наличие(гз) = У, то ИБД(лс(гг),лс(гз)). (5) Если наличие(гг) = У и наличие(гз) = У, то ИБД(пс(г1),пс(гз)). Испытаем этот алгоритм на деревьях Т, и Тз, изображенных на рис.
!5.46. т гг я~ А Р Риа 15.45 РДЗЛЕП 15.4. Обход бинарных деревьев 655 Обрабатываем г~ и гз. Поскольку наличие(г,) = У и наличие(г,) = У, переходим к шагу 3 ИБД(гь,гз). Здесь вызываем ИБД(лс(гз), лс(гз)), т.е. обрабатываем аь и аа. Поскольку наличие(аь) = У и наличие(аз) = У, переходим к шагу 3 алгоритма ИБД(ам аз). Здесь вызываем ИБД(лс(аь), лс(аз)), т.е.
обрабатываем 6ь и Ьз. Поскольку наличие(Ь,) = У и наличие(Ьз) = У, переходим к шагу 3 алгоритма ИБД (аь, аа). Здесь вызываем ИБД(лс(6|), лс(6з)), т.е. обрабатываем лс(Ьь) и лс(Ьа). А так как наличие(лс(Ьь)) = Аг и наличие(лс(Ьа)) = Аг, возвращаемся к шагу 4 алгортма ИБД(аь, аз), который вызывает ИБД(пс(а~), пс(аз)). Обрабатываем сд и пс(аз). Но наличие(сД = У и наличие(пс(аз)) = Аг, поэтому Изо = Г, и процесс прекращается. Таким образом, два рассмотренных дерева не изоморфны. ° УПРАЖНЕНИЯ 1.
Для дерева, изображенного на рис. 15.4?, а) приведите инфиксную запись вершин дерева; б) приведите префиксную запись вершин дерева; в) приведите постфиксную запись вершин дерева. Рис. 15.48 Рис. 15.47 2. Для дерева, изображенного на рис. 15.48, а) приведите инфиксную запись вершин дерева; б) приведите префиксную запись вершин дерева; в) приведите постфиксную запись вершин дерева. 3. Для дерева, изображенного на рис. 15.49, а) приведите инфиксную запись вершин дерева; б) приведите префиксную запись вершин дерева; в) приведите постфиксную запись вершин дерева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
