Программа 5.14 Рекурсивный обход дерева

Деревья и их обход

 

Деревья – это математические абстракции, играющие огромную роль при разработке и анализе алгоритмов, поскольку

- Мы используем деревья для описания динамических свойств алгоритмов;

- Мы строим и используем явные структуры данных, которые являются конкретными реализациями деревьев.

Мы часто встречаемся с деревьями в повседневной жизни – это основное понятие хорошо знакомо. Например, многие люди отслеживают предков и наследников с помощью генеалогического дерева; как будет показано, значительная часть терминов заимствована именно из этой области применения. Ещё один пример – организация спортивных турниров; среди прочих, в исследовании этого применения принял участие Льюис Кэрролл. В качестве третьего примера можно привести организационную диаграмму большой корпорации; это применение отличается иерархическим разделением, характерным для алгоритмов типа “разделяй и властвуй”. Четвёртым примером служит дерево синтаксического разложения предложения английского (или любого другого языка) на составляющие его части; такое дерево близко связано с обработкой компьютерных языков.

Применительно к компьютерам, одно из наиболее известных применений структур деревьев — для организации файловых систем. Файлы хранятся в каталогах (иногда называемых также папками), которые рекурсивно определяются как последовательности каталогов и файлов. Это рекурсивное определение снова отражает естественное рекурсивное разбиение на составляющие и идентично определению определенного типа дерева.

Существует множество различных типов деревьев, и важно понимать различие
между абстракцией и конкретным представлением, с которым выполняется работа
для данного приложения. Соответственно, мы подробно рассмотрим различные типы
деревьев и их представления. Рассмотрение начнется с определения деревьев как абстрактных объектов и с ознакомления с большинством основных связанных с ними
терминов. Мы неформально рассмотрим различные типы деревьев, которые следует рассматривать в порядке сужения самого этого понятия:

• Деревья

• Деревья с корнем

• Упорядоченные деревья

• М-арные и бинарные деревья

После этого неформального рассмотрения мы перейдем к формальным определениям и рассмотрим представления и приложения.

Дерево (tree) — это непустая коллекция вершин и ребер, удовлетворяющих определенным требованиям. Вершина (vertex) — это простой объект (называемый также узлом (node)), который может иметь имя и содержать другую связанную с ним информацию; ребро (edge) — это связь между двумя вершинами. Путь (path) в дереве — это список отдельных вершин, в котором следующие друг за другом вершины соединяются ребрами дерева. Определяющее свойство дерева — существование только одного пути, соединяющего любые два узла. Если между какой-либо парой узлов существует более одного пути или если между какой-либо парой узлов путь отсутствует, мы имеем граф, а не дерево. Несвязанный набор деревьев называется бором (forest).

Дерево с корнем (единственным,rooted) — это дерево, в котором один узел назначен корнем (root) дерева. В области компьютеров термин дерево обычно применяется
к деревьям с корнем, а термин свободное дерево (free tree) — к более общим структурам, описанным в предыдущем абзаце. В дереве с корнем любой узел является корнем поддерева, состоящего из него и расположенных под ним узлов.

Существует только один путь между корнем и каждым из других узлов дерева.
Данное определение никак не определяет направление ребер; обычно считается, что
все ребра указывают от корня или к корню, в зависимости от приложения. Обычно
деревья с корнем рисуются с корнем, расположенным в верхней части (хотя на первый взгляд это соглашение кажется неестественным), и говорят, что узел у располагается под узлом x а x располагается над y ), если x находится на пути от yк корню (т.е., у находится под х и соединяется с х путем, который не проходит через корень). Каждый узел (за исключением корня) имеет только один узел над ним, который называется его родительским узлом (parent), узлы, расположенные непосредственно под данным узлом, называются его дочерними узлами (children). Иногда аналогия с генеалогическими деревьями расширяется еще больше, и тогда говорят об узлах-предках (grand parent) или родственных (sibling) узлах данного узла. Узлы, не имеющие дочерних узлов, называются листьями (leaves) или терминальными (оконечными, terminal) узлами. Для соответствия с последним применением узлы, имеющие хотя бы один дочерний узел, иногда называются нетерминальными (nonterminal) узлами. В этой главе мы уже встречались с примером утилиты, различающей эти типы узлов. В деревьях, которые использовались для представления структуры вызовов рекурсивных алгоритмов, нетерминальные узлы (окружности) представляют вызовы функций с рекурсивными вызовами, а терминальные узлы (квадраты) представляют вызовы функций без рекурсивных вызовов.

В определенных приложениях способ упорядочения дочерних узлов каждого узла
имеет значение; в других это не важно. Упорядоченное (ordered) дерево — это дерево
с корнем, в котором определен порядок следования дочерних узлов каждого узла.
Упорядоченные деревья — естественное представление: например, при рисовании дерева дочерние узлы размещаются в определенном порядке. Действительно, многие
другие конкретные представления имеют аналогично предполагаемый порядок; например, обычно это различие имеет значение при рассмотрении представления деревьев в компьютере.

Если каждый узел должен иметь конкретное количество дочерних узлов, появляющихся в конкретном порядке, мы имеем М-арное дерево. В таком дереве часто можно определить специальные внешние узлы, которые не имеют дочерних узлов. Тогда
внешние узлы могут действовать в качестве фиктивных, на которые ссылаются узлы,
не имеющие указанного количества дочерних узлов. В частности, простейшим типом
М-арного дерева является бинарное дерево. Бинарное дерево (binary tree) ~ это упорядоченное дерево, состоящее из узлов двух типов: внешних узлов без дочерних узлов
и внутренних узлов, каждый из которых имеет ровно два дочерних узла. Поскольку
два дочерних узла каждого внутреннего узла упорядочены, говорят о левом дочернем
узле (left child) и правом дочернем узле (right child) внутренних узлов. Каждый внутренний узел должен иметь и левый, и правый дочерние узлы, хотя один из них или оба
могут быть внешними узлами. Лист в М-арном дереве — это внутренний узел, все
дочерние узлы которого являются внешними.

Все это общая терминология. Далее рассматриваются формальные определения,
представления и приложения, в порядке расширения понятий;

• бинарные и M-арные деревья

• упорядоченные деревья

• деревья с корнем

• свободные деревья

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

Определение 5. 1 Бинарное дерево — это либо внешний узел, либо внутренний узел, связанный с парой бинарных деревьев, которые называются левым и правым поддеревьями этого узла.

Из этого определения становится понятно, что сами деревья - абстрактное математическое понятие. При работе с компьютерными представлениями мы работаем
всего лишь с одной конкретной реализацией этой абстракции. Эта ситуация не отличается от представления действительных чисел значениями типа float, целых чисел
значениями типа int и т.д. Когда мы рисуем дерево с узлом в корне, связанным ребрами с левым поддеревом, расположенным слева, и с правым поддеревом, расположенным справа, то выбираем удобное конкретное представление. Существует множество различных способов представления бинарных деревьев, которые поначалу кажутся удивительными, но вполне отражают сущность, как и можно было ожидать, учитывая абстрактный характер определения. Чаще всего применяется следующее конкретное представление при реализации программ, использующих и манипулирующих бинарными деревьями, — структура с двумя связями (правой и левой) для внутренних узлов. Эти структуры аналогичны связным спискам, но они имеют по две связи для каждого узла, а не по одной. Нулевые связи соответствуют внешним узлам. В частности, мы добавили связь к стандартному представлению связного списка, следующим образом:

struct node {Item item; node *l, *r;}

typedef node * link;

что представляет собой всего лишь код С++ для определения 5.1. Узлы состоят из элементов и пар указателей на узлы, и указатели на узлы называются также связями
Так, например, мы реализуем абстрактную операцию перехода к левому поддереву c
помощью ссылки на указатель типа х = х->1.

Это стандартное представление позволяет построить эффективную реализацию
операций, которые вызываются для перемещения по дереву вниз от корня, но не для
перемещения по дереву вверх от дочернего узла к его родительскому узлу. Для алгоритмов, требующих использования таких операций, можно добавить третью связь для
каждого узла, направленную к его родительскому узлу. Эта альтернатива аналогична двухсвязным спискам. Как и в случае со связными списками, в определенных ситуациях узлы дерева хранятся в массиве, а в качестве связей используются индексы, а не указатели. Для определенных специальных алгоритмов используются другие представления бинарных деревьев. Из-за наличия такого множества различных возможных представлений можно было бы разработать ADT (abstract data Туре) (абстрактный тип данных) бинарного дерева, инкапсулирующий важные операции, которые нужно выполнять, и разделяющий использование и реализацию этих операций. В данной книге данный подход не используется, поскольку

• чаще всего мы используем представление с двумя связями;

• мы используем деревья для реализации АОТ более высокого уровня, и хотим
сосредоточить внимание на этой теме;

• мы работаем с алгоритмами, эффективность которых зависит от конкретного
представления, — это обстоятельство может быть упущено в АОТ.

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

Анализируя связные списки, мы начали рассмотрение с элементарных операций
вставки и удаления узлов. При использовании стандартного представления бинарных деревьев такие операции необязательно являются элементарными из-за наличия второй связи. Если нужно удалить узел из бинарного дерева, приходится решать принципиальную проблему наличия двух дочерних узлов и только одного родительского, с которыми нужно работать после удаления узла. Существуют три естественных операции, для которых подобное осложнение не возникает вставка нового узла в нижней части дерева (замена нулевой связи связью с новым узлом), удаление листа (замена связи с ним нулевой связью) и объединение двух деревьев посредством создания нового корня, левая связь которого указывает на одно дерево, а правая — на другое. Эти операции интенсивно используются при манипулировании бинарными деревьями.

Определение 5.2 М-арное дерево — это внешний узел, либо внутренний узел, связанный с упорядоченной последовательностью М деревьев, которые также являются М-ар-
ными деревьями.

Обычно узлы в М-арных деревьях представляются либо в виде структур с М именованными связями (как в бинарных деревьях), либо в виде массивов М связей. В остальных случаях использование массивов для хранения связей вполне подходит, поскольку значение М фиксировано, хотя, как будет показано, при использовании такого представления особое внимание потребуется уделить интенсивному использованию памяти.

Определение 5.3 Дерево (также называемое упорядоченным деревом) — это узел (называемый корнем), связанный с последовательностью несвязанных деревьев. Такая последовательность называется бором.

Различие между упорядоченными деревьями и М-арными деревьями состоит в
том, что узлы в упорядоченных деревьях могут иметь любое количество дочерних
узлов, в то время как узлы в М-арных деревьях должны иметь точно M дочерних узлов. Иногда в контекстах, в которых требуется различать упорядоченные и М-арные
деревья, мы используем термин главное дерево (general tree).

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

Лемма 5.4 Существует однозначное соответствие между бинарными деревьями и упорядоченными борами.

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

Определение 5.4 Дерево с корнем (или неупорядоченное дерево) — это узел (называемый корнем), связанный с множественным набором деревьев с корнем. (Такой множественный набор называется неупорядоченным бором.)

Неупорядоченное дерево можно было бы представить в компьютере упорядоченным деревом; при этом приходится признать, что несколько различных упорядоченных деревьев могут представлять одно и то же неупорядоченное дерево. Действительно, обратная задача определения того, представляют ли два различные упорядоченные дерева одно и то же неупорядоченное дерево (задача изоморфизма дерева) трудно подается решению. Наиболее общим типом деревьев является дерево, в котором не выделен ни один корневой узел. Например, основные деревья, полученные в результате работы алгоритмов связности из главы 1, обладают этим свойством. Для правильного определения деревьев без корня, неупорядоченных деревьев и свободных деревьев потребуется начать с определения графов (graphsз).

Определение 5.5 Граф — это набор узлов с набором ребер, которые соединяют пары

отдельных узлов (причем любую пару узлов соединяет только одно ребро).

Представление упорядоченного дерева за счет поддержания связного списка дочерних узлов каждого узла эквивалентно представлению его в виде двоичного дерева. На схеме справа вверху показано представление в виде связного списка дочерних узлов для дерева, показанного слева вверху; при этом список реализован в правых связях узлов, а левая связь каждого узла указывает на первый узел в связном списке его дочерних узлов. На схеме справа внизу приведена несколько измененная версия верхней схемы; она представляет бинарное дерево, изображенное слева внизу. Таким образом, бинарное дерево можно рассматривать в качестве представления дерева. Представьте себе, что перемещаетесь вдоль ребра от одного какого-либо узла до другого, затем от этого узла к следующему и т.д. Последовательность ребер, ведущих одного узла до другого, когда ни один узел не посещается дважды, называется простым путем. Граф является связным (connected), если существует простой путь, связывающий любую пару узлов. Простой путь, у которого первый и последний узел совпадают, называется циклом (сус1е).

Каждое дерево является графом; а какие же графы являются деревьями? Граф считается деревом, если он удовлетворяет любому из следующих четырех условий:
- Граф имеет N - 1 ребер и ни одного цикла.
- Граф имеет N-1 ребер и является связным.

- Только один простой путь соединяет каждую пару вершин в графе.
- Граф является связным, но перестает быть таковым при удалении любого ребра.
Любое из этих условий — необходимое и достаточное условие для выполнения остальных трех. Формально, одно из них должно было бы служить определением свободного дерева', неформально, они все вместе служат определением. Мы представляем свободное дерево в виде коллекции ребер. Если представлять свободное дерево неупорядоченным, упорядоченным или даже бинарным деревом, придется признать, что в общем случае существует множество различных способов представления каждого свободного дерева. Абстракция дерева используется часто, и рассмотренные в этом разделе различия важны, поскольку знание различных абстракций деревьев — существенная составляющая определения эффективного алгоритма и соответствующих структур данных для решения данной задачи. Часто приходится работать непосредственно с конкретными представлениями деревьев без учета конкретной абстракции, но в то же время часто имеет смысл поработать с соответствующей абстракцией дерева, а затем рассмотреть различные конкретные представления. В книге приведено множество примеров этого процесса. Прежде чем вернуться к алгоритмам и представлениям, мы рассмотрим ряд основных математических свойств деревьев; эти свойства будут использоваться при разработке и анализе алгоритмов в виде деревьев.

Обход дерева

Когда количество внешних узлов является степенью 2, все внешние узлы в полном бинарном дереве располагаются наодном уровне. В противном случае
внешние узлы располагаются в двух уровнях при размещении внутренних узлов слева от внешних узлов предпоследнего уровня.Прежде чем рассматривать алгоритмы, конструирующие бинарные деревья и деревья, рассмотрим алгоритмы для реализации наиболее общей функции обработки деревьев — обхода дерева, при наличии указателя на дерево требуется систематически обработать все узлы в дереве. В связном списке переход от одного узла к другому выполняется за счет отслеживания единственной связи; однако, в случае деревьев приходится принимать решения, поскольку может существовать несколько связей, по которым можно следовать. Начнем рассмотрение с процесса для бинарных деревьев. В случае со связными списками имелись две основные возможности (см. программу 5.5): обработать узел, а затем следовать связи (в этом случае узлы посещались бы по порядку), или следовать связи, а затем обработать узел (в этом случае узлы посещались бы в обратном порядке). При работе с бинарными деревьями существуют две связи и, следовательно, три основных порядка возможного посещения узлов:

• Прямой обход (сверху вниз), при котором мы посещаем узел, а затем левое и правое поддеревья

• Поперечный обход (слева направо), при котором мы посещаем левое поддерево,
затем узел, а затем правое поддерево

• Обратный обход (снизу вверх), при котором мы посещаем левое и правое поддеревья, а затем узел.

Эти методы можно легко реализовать с помощью рекурсивной программы, как
показано в программе 5.14, которая является непосредственным обобщением программы 5.5 обхода связного списка. Для реализации обходов в других порядках достаточно соответствующим образом переставить вызовы функций в программе 5.14

Traverse E

Visit E

Traverse D

Visit D

Traverse B

Visit B

Traverse A

Visit A

Traverse *

Traverse *

Traverse C

Visit C

Traverse *

Traverse *

Traverse *

Traverse H

Visit H

Traverse F

Visit F

Traverse *

Traverse G

Visit G

Traverse *

Traverse *

Traverse *

Описанная в предыдущем абзаце схема является концептуальной, охватывающей
три метода обхода дерева, однако реализации, используемые на практике, несколько проще. Например, для выполнения прямого обхода не обязательно заталкивать
узлы в стек (мы посещаем корень каждого выталкиваемого дерева), поэтому можно
воспользоваться простым стеком, состоящим только из одного типа элементов (связей дерева), как это сделано в не рекурсивной реализации в программе 5.15. Системный стек, поддерживающий рекурсивную программу, содержит адреса возврата и значения аргументов, а не элементы или узлы, но фактическая последовательность
выполнения вычислений (посещения узлов) остается одинаковой для рекурсивного
метода и метода с использованием стека.

Деревья и их обход

 

Деревья – это математические абстракции, играющие огромную роль при разработке и анализе алгоритмов, поскольку

- Мы используем деревья для описания динамических свойств алгоритмов;

- Мы строим и используем явные структуры данных, которые являются конкретными реализациями деревьев.

Мы часто встречаемся с деревьями в повседневной жизни – это основное понятие хорошо знакомо. Например, многие люди отслеживают предков и наследников с помощью генеалогического дерева; как будет показано, значительная часть терминов заимствована именно из этой области применения. Ещё один пример – организация спортивных турниров; среди прочих, в исследовании этого применения принял участие Льюис Кэрролл. В качестве третьего примера можно привести организационную диаграмму большой корпорации; это применение отличается иерархическим разделением, характерным для алгоритмов типа “разделяй и властвуй”. Четвёртым примером служит дерево синтаксического разложения предложения английского (или любого другого языка) на составляющие его части; такое дерево близко связано с обработкой компьютерных языков.

Применительно к компьютерам, одно из наиболее известных применений структур деревьев — для организации файловых систем. Файлы хранятся в каталогах (иногда называемых также папками), которые рекурсивно определяются как последовательности каталогов и файлов. Это рекурсивное определение снова отражает естественное рекурсивное разбиение на составляющие и идентично определению определенного типа дерева.

Существует множество различных типов деревьев, и важно понимать различие
между абстракцией и конкретным представлением, с которым выполняется работа
для данного приложения. Соответственно, мы подробно рассмотрим различные типы
деревьев и их представления. Рассмотрение начнется с определения деревьев как абстрактных объектов и с ознакомления с большинством основных связанных с ними
терминов. Мы неформально рассмотрим различные типы деревьев, которые следует рассматривать в порядке сужения самого этого понятия:

• Деревья

• Деревья с корнем

• Упорядоченные деревья

• М-арные и бинарные деревья

После этого неформального рассмотрения мы перейдем к формальным определениям и рассмотрим представления и приложения.

Дерево (tree) — это непустая коллекция вершин и ребер, удовлетворяющих определенным требованиям. Вершина (vertex) — это простой объект (называемый также узлом (node)), который может иметь имя и содержать другую связанную с ним информацию; ребро (edge) — это связь между двумя вершинами. Путь (path) в дереве — это список отдельных вершин, в котором следующие друг за другом вершины соединяются ребрами дерева. Определяющее свойство дерева — существование только одного пути, соединяющего любые два узла. Если между какой-либо парой узлов существует более одного пути или если между какой-либо парой узлов путь отсутствует, мы имеем граф, а не дерево. Несвязанный набор деревьев называется бором (forest).

Дерево с корнем (единственным,rooted) — это дерево, в котором один узел назначен корнем (root) дерева. В области компьютеров термин дерево обычно применяется
к деревьям с корнем, а термин свободное дерево (free tree) — к более общим структурам, описанным в предыдущем абзаце. В дереве с корнем любой узел является корнем поддерева, состоящего из него и расположенных под ним узлов.

Существует только один путь между корнем и каждым из других узлов дерева.
Данное определение никак не определяет направление ребер; обычно считается, что
все ребра указывают от корня или к корню, в зависимости от приложения. Обычно
деревья с корнем рисуются с корнем, расположенным в верхней части (хотя на первый взгляд это соглашение кажется неестественным), и говорят, что узел у располагается под узлом x а x располагается над y ), если x находится на пути от yк корню (т.е., у находится под х и соединяется с х путем, который не проходит через корень). Каждый узел (за исключением корня) имеет только один узел над ним, который называется его родительским узлом (parent), узлы, расположенные непосредственно под данным узлом, называются его дочерними узлами (children). Иногда аналогия с генеалогическими деревьями расширяется еще больше, и тогда говорят об узлах-предках (grand parent) или родственных (sibling) узлах данного узла. Узлы, не имеющие дочерних узлов, называются листьями (leaves) или терминальными (оконечными, terminal) узлами. Для соответствия с последним применением узлы, имеющие хотя бы один дочерний узел, иногда называются нетерминальными (nonterminal) узлами. В этой главе мы уже встречались с примером утилиты, различающей эти типы узлов. В деревьях, которые использовались для представления структуры вызовов рекурсивных алгоритмов, нетерминальные узлы (окружности) представляют вызовы функций с рекурсивными вызовами, а терминальные узлы (квадраты) представляют вызовы функций без рекурсивных вызовов.

В определенных приложениях способ упорядочения дочерних узлов каждого узла
имеет значение; в других это не важно. Упорядоченное (ordered) дерево — это дерево
с корнем, в котором определен порядок следования дочерних узлов каждого узла.
Упорядоченные деревья — естественное представление: например, при рисовании дерева дочерние узлы размещаются в определенном порядке. Действительно, многие
другие конкретные представления имеют аналогично предполагаемый порядок; например, обычно это различие имеет значение при рассмотрении представления деревьев в компьютере.

Если каждый узел должен иметь конкретное количество дочерних узлов, появляющихся в конкретном порядке, мы имеем М-арное дерево. В таком дереве часто можно определить специальные внешние узлы, которые не имеют дочерних узлов. Тогда
внешние узлы могут действовать в качестве фиктивных, на которые ссылаются узлы,
не имеющие указанного количества дочерних узлов. В частности, простейшим типом
М-арного дерева является бинарное дерево. Бинарное дерево (binary tree) ~ это упорядоченное дерево, состоящее из узлов двух типов: внешних узлов без дочерних узлов
и внутренних узлов, каждый из которых имеет ровно два дочерних узла. Поскольку
два дочерних узла каждого внутреннего узла упорядочены, говорят о левом дочернем
узле (left child) и правом дочернем узле (right child) внутренних узлов. Каждый внутренний узел должен иметь и левый, и правый дочерние узлы, хотя один из них или оба
могут быть внешними узлами. Лист в М-арном дереве — это внутренний узел, все
дочерние узлы которого являются внешними.

Все это общая терминология. Далее рассматриваются формальные определения,
представления и приложения, в порядке расширения понятий;

• бинарные и M-арные деревья

• упорядоченные деревья

• деревья с корнем

• свободные деревья

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

Определение 5. 1 Бинарное дерево — это либо внешний узел, либо внутренний узел, связанный с парой бинарных деревьев, которые называются левым и правым поддеревьями этого узла.

Из этого определения становится понятно, что сами деревья - абстрактное математическое понятие. При работе с компьютерными представлениями мы работаем
всего лишь с одной конкретной реализацией этой абстракции. Эта ситуация не отличается от представления действительных чисел значениями типа float, целых чисел
значениями типа int и т.д. Когда мы рисуем дерево с узлом в корне, связанным ребрами с левым поддеревом, расположенным слева, и с правым поддеревом, расположенным справа, то выбираем удобное конкретное представление. Существует множество различных способов представления бинарных деревьев, которые поначалу кажутся удивительными, но вполне отражают сущность, как и можно было ожидать, учитывая абстрактный характер определения. Чаще всего применяется следующее конкретное представление при реализации программ, использующих и манипулирующих бинарными деревьями, — структура с двумя связями (правой и левой) для внутренних узлов. Эти структуры аналогичны связным спискам, но они имеют по две связи для каждого узла, а не по одной. Нулевые связи соответствуют внешним узлам. В частности, мы добавили связь к стандартному представлению связного списка, следующим образом:

struct node {Item item; node *l, *r;}

typedef node * link;

что представляет собой всего лишь код С++ для определения 5.1. Узлы состоят из элементов и пар указателей на узлы, и указатели на узлы называются также связями
Так, например, мы реализуем абстрактную операцию перехода к левому поддереву c
помощью ссылки на указатель типа х = х->1.

Это стандартное представление позволяет построить эффективную реализацию
операций, которые вызываются для перемещения по дереву вниз от корня, но не для
перемещения по дереву вверх от дочернего узла к его родительскому узлу. Для алгоритмов, требующих использования таких операций, можно добавить третью связь для
каждого узла, направленную к его родительскому узлу. Эта альтернатива аналогична двухсвязным спискам. Как и в случае со связными списками, в определенных ситуациях узлы дерева хранятся в массиве, а в качестве связей используются индексы, а не указатели. Для определенных специальных алгоритмов используются другие представления бинарных деревьев. Из-за наличия такого множества различных возможных представлений можно было бы разработать ADT (abstract data Туре) (абстрактный тип данных) бинарного дерева, инкапсулирующий важные операции, которые нужно выполнять, и разделяющий использование и реализацию этих операций. В данной книге данный подход не используется, поскольку

• чаще всего мы используем представление с двумя связями;

• мы используем деревья для реализации АОТ более высокого уровня, и хотим
сосредоточить внимание на этой теме;

• мы работаем с алгоритмами, эффективность которых зависит от конкретного
представления, — это обстоятельство может быть упущено в АОТ.

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

Анализируя связные списки, мы начали рассмотрение с элементарных операций
вставки и удаления узлов. При использовании стандартного представления бинарных деревьев такие операции необязательно являются элементарными из-за наличия второй связи. Если нужно удалить узел из бинарного дерева, приходится решать принципиальную проблему наличия двух дочерних узлов и только одного родительского, с которыми нужно работать после удаления узла. Существуют три естественных операции, для которых подобное осложнение не возникает вставка нового узла в нижней части дерева (замена нулевой связи связью с новым узлом), удаление листа (замена связи с ним нулевой связью) и объединение двух деревьев посредством создания нового корня, левая связь которого указывает на одно дерево, а правая — на другое. Эти операции интенсивно используются при манипулировании бинарными деревьями.

Определение 5.2 М-арное дерево — это внешний узел, либо внутренний узел, связанный с упорядоченной последовательностью М деревьев, которые также являются М-ар-
ными деревьями.

Обычно узлы в М-арных деревьях представляются либо в виде структур с М именованными связями (как в бинарных деревьях), либо в виде массивов М связей. В остальных случаях использование массивов для хранения связей вполне подходит, поскольку значение М фиксировано, хотя, как будет показано, при использовании такого представления особое внимание потребуется уделить интенсивному использованию памяти.

Определение 5.3 Дерево (также называемое упорядоченным деревом) — это узел (называемый корнем), связанный с последовательностью несвязанных деревьев. Такая последовательность называется бором.

Различие между упорядоченными деревьями и М-арными деревьями состоит в
том, что узлы в упорядоченных деревьях могут иметь любое количество дочерних
узлов, в то время как узлы в М-арных деревьях должны иметь точно M дочерних узлов. Иногда в контекстах, в которых требуется различать упорядоченные и М-арные
деревья, мы используем термин главное дерево (general tree).

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

Лемма 5.4 Существует однозначное соответствие между бинарными деревьями и упорядоченными борами.

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

Определение 5.4 Дерево с корнем (или неупорядоченное дерево) — это узел (называемый корнем), связанный с множественным набором деревьев с корнем. (Такой множественный набор называется неупорядоченным бором.)

Неупорядоченное дерево можно было бы представить в компьютере упорядоченным деревом; при этом приходится признать, что несколько различных упорядоченных деревьев могут представлять одно и то же неупорядоченное дерево. Действительно, обратная задача определения того, представляют ли два различные упорядоченные дерева одно и то же неупорядоченное дерево (задача изоморфизма дерева) трудно подается решению. Наиболее общим типом деревьев является дерево, в котором не выделен ни один корневой узел. Например, основные деревья, полученные в результате работы алгоритмов связности из главы 1, обладают этим свойством. Для правильного определения деревьев без корня, неупорядоченных деревьев и свободных деревьев потребуется начать с определения графов (graphsз).

Определение 5.5 Граф — это набор узлов с набором ребер, которые соединяют пары

отдельных узлов (причем любую пару узлов соединяет только одно ребро).

Представление упорядоченного дерева за счет поддержания связного списка дочерних узлов каждого узла эквивалентно представлению его в виде двоичного дерева. На схеме справа вверху показано представление в виде связного списка дочерних узлов для дерева, показанного слева вверху; при этом список реализован в правых связях узлов, а левая связь каждого узла указывает на первый узел в связном списке его дочерних узлов. На схеме справа внизу приведена несколько измененная версия верхней схемы; она представляет бинарное дерево, изображенное слева внизу. Таким образом, бинарное дерево можно рассматривать в качестве представления дерева. Представьте себе, что перемещаетесь вдоль ребра от одного какого-либо узла до другого, затем от этого узла к следующему и т.д. Последовательность ребер, ведущих одного узла до другого, когда ни один узел не посещается дважды, называется простым путем. Граф является связным (connected), если существует простой путь, связывающий любую пару узлов. Простой путь, у которого первый и последний узел совпадают, называется циклом (сус1е).

Каждое дерево является графом; а какие же графы являются деревьями? Граф считается деревом, если он удовлетворяет любому и