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

Анализ бинарного дерева: Tree2

В заданиях группы Tree, как и в заданиях группы Dynamic, мы встречаемся с двумя новыми видами данных: это древовидные динамические структуры, реализованные в виде наборов связанных друг с другом записей типа TNode, и указатели типа PNode на записи TNode. В языках C и C++ записи оформляются в виде структур (типов данных struct). Типы TNode и PNode не являются стандартными типами библиотеки C или C++; они определены в задачнике Programming Taskbook, а точнее, в подключаемом файле pt4.h.

Особенности, связанные с использованием новых типов данных, рассмотрим на примере задания Tree2.

Tree2°. Дан адрес P₁ записи типа TNode — корня дерева. Эта запись связана полями Left и Right с другими записями того же типа (дочерними вершинами), они, в свою очередь, — со своими дочерними вершинами, и так далее до записей, поля Left и Right которых равны NULL (у некоторых вершин может быть равно NULL одно из полей Left или Right). Вывести количество вершин дерева.

Создание программы-заготовки и знакомство с заданием

Напомним, что программу-заготовку для решения задания можно создать с помощью модуля PT4Load. Приведем текст функции Solve из файла Tree2.cpp, входящего в созданный проект (именно в эту функцию требуется ввести решение задачи):

[C/C++]

void Solve()
{
    Task("Tree2");
}

Аналогичным образом выглядит функция Solve из файла Tree2.c, входящего в проект для языка C.

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

Это окно содержит в качестве исходных и результирующих данных новые элементы: бинарные деревья и указатели.

Начнем с описания того, как отображается на экране дерево. Для его вывода используется несколько экранных строк (от двух до пяти). На каждой строке изображаются вершины дерева, находящиеся на определенном уровне (номер уровня указывается слева от изображения дерева). Для каждой вершины выводится ее значение, т. е. значение поля Data соответствующей структуры типа TNode. Любая вершина соединяется линиями со своими дочерними вершинами, расположенными на следующем уровне дерева; левая дочерняя вершина изображается слева от родительской вершины, а правая — справа. Отсутствие у вершины одной или обеих дочерних вершин означает, что ее поля Left и/или Right равны NULL.

Рассмотрим в качестве примера дерево, приведенное на рисунке. Корень этого дерева имеет значение 15, левая дочерняя вершина корня равна 58, правая дочерняя вершина равна 42, глубина дерева равна 4. Все листья дерева находятся на уровнях 3 и 4; листья на уровне 3 имеют значения 15 и 11, листья на уровне 4 — значения 38 и 84. Некоторые из внутренних вершин дерева имеют по две дочерние вершины (это корень и вершины со значениями 55 и 20), некоторые по одной: левой (вершины 42, 87 и 60) или правой (вершина 58).

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

Из текста, описывающего дерево, видно, что с его корнем связан указатель с именем P₁, который также содержится в наборе исходных данных (имя указателя находится под изображением той вершины дерева, с которой он связан). Описание этого указателя имеет вид

P₁ = ptr

Здесь текст «P₁ =» является комментарием и выделяется, как обычный комментарий, светло-серым цветом, а текст «ptr» означает, что этот элемент исходных данных является указателем, который надо ввести в программу с помощью функции ввода GetP. Для языка C++ можно также использовать функцию GetNode или поток ввода pt. Если в задании требуется передать задачнику адрес, связанный с некоторой вершиной дерева, то необходимо использовать функцию вывода PutP (для языка C++ можно также использовать поток вывода pt). Более подробно работа с исходными и результирующими данными типа указателя обсуждается в разделе, посвященном линейным динамическим структурам.

Решение задачи

Вернемся к заданию Tree2. В нем не требуется ни создавать, ни преобразовывать исходное дерево; его необходимо лишь проанализировать, а именно, определить количество его вершин.

Для выполнения этого задания, как и для подавляющего большинства других заданий на обработку деревьев, следует воспользоваться вспомогательной рекурсивной функцией. Рекурсивная природа алгоритмов, связанных с обработкой деревьев (в частности, бинарных деревьев), объясняется тем, что сами определения деревьев общего вида и бинарных деревьев являются рекурсивными. Так, дать словесное описание функции NodeCount(p), подсчитывающей число вершин дерева с корнем, с которым связан указатель p, можно следующим образом: если указатель p равен NULL, то следует вернуть значение 0; в противном случае следует вернуть значение 1 + NodeCount(p->Left) + NodeCount(p->Right) (в этом выражении первое слагаемое соответствует корню дерева, второе — его левому поддереву, а третье — его правому поддереву; при этом не требуется проверять, что указанные поддеревья существуют, так как при их отсутствии соответствующее слагаемое просто будет равно нулю):

[C/C++]

int NodeCount(PNode p)
{
    return p == NULL ? 0 : 1 + NodeCount(p->Left) + NodeCount(p->Right);
}

Примечание. Для возможности использования макроса NULL в программах на языке C к ним надо подключить заголовочный файл <stddef.h>. Однако в программах, выполняющих задания из электронного задачника, это делать необязательно, так как к ним этот заголовочный файл подключается автоматически.

Цепочка рекурсивных вызовов функции NodeCount завершается при достижении терминальной вершины (листа), у которой поля Left и Right равны NULL. Благодаря наличию функции NodeCount, функция Solve становится очень простой: в ней считывается адрес p1 корня исходного дерева, после чего вызывается функция NodeCount(p1), возвращаемое значение которой сразу выводится:

[C/C++]

Task("Tree2");
PNode p1;
GetP(&p1);
PutN(NodeCount(p1));

Проверив программу на пяти тестовых наборах, мы получим сообщение «Задание выполнено!».

Если использовать функцию GetNode, определенную в задачнике для языка C++, все действия в функции Solve (ввод указателя на корень дерева, вызов функции NodeCount и вывод результата) можно объединить в единственном операторе:

[C++]

Task("Tree2");
PutN(NodeCount(GetNode()));

Еще короче (и с меньшим количеством скобок) записывается вариант решения для языка C++, в котором используется поток вывода pt:

[C++]

Task("Tree2");
pt << NodeCount(GetNode());

Бинарные деревья с обратной связью и деревья общего вида: Tree49, Tree86

Деревья с обратной связью

Рассмотренная выше реализация бинарных деревьев позволяет легко переходить от родительских вершин к их дочерним вершинам, но не допускает обратного перехода. В то же время, для некоторых задач, связанных с обработкой деревьев, возможность обратного перехода от потомков к их предку позволяет получить более простое решение. Ясно, что для обеспечения возможности обратного перехода каждую вершину дерева надо снабдить еще одним полем связи, в котором должна храниться ссылка на ее родительскую вершину. Это поле связи естественно назвать Parent. Поскольку корень дерева предка не имеет, его поле Parent должно быть равно NULL.

Деревья, вершины которых содержат информацию о своих родителях, будем называть деревьями с обратной связью. Особенности работы с подобными деревьями рассмотрим на примере задания Tree49.

Tree49°. Дан указатель P₁ на корень дерева, вершинами которого являются записи типа TNode, связанные между собой с помощью полей Left и Right. Используя поле Parent записи TNode, преобразовать исходное дерево в дерево с обратной связью, в котором каждая вершина связана не только со своими дочерними вершинами (полями Left и Right), но и с родительской вершиной (полем Parent). Поле Parent корня дерева положить равным NULL.

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

Обратите также внимание на то, что в области результатов отсутствуют какие-либо данные, кроме измененного дерева. Это означает, что в программе, решающей задачу, не требуется использовать функции или поток вывода; достаточно лишь преобразовать исходное дерево требуемым образом. Поскольку при таком преобразовании адрес корня дерева P₁ не изменится, задачник сможеть получить доступ к этому дереву и проверить его правильность.

Для преобразования исходного дерева в дерево с обратной связью необходимо задать правильные значения для полей Parent всех вершин дерева, перебирая эти вершины с помощью подходящей рекурсивной функции. В эту функцию удобно передавать в качестве параметров не только указатель p на текущую вершину, но и указатель par на предка этой вершины:

[C/C++]

void SetParent(PNode p, PNode par)
{
  if (p == NULL)
    return;
  p->Parent = par;
  SetParent(p->Left, p);
  SetParent(p->Right, p);
}

При стартовом запуске рекурсивной функции SetParent из функции Solve в качестве второго параметра указывается NULL):

[C/C++]

Task("Tree49");
PNode p1;
GetP(&p1);
SetParent(p1, NULL);

Отображение деревьев: дополнительные сведения

Обозначение для двойной связи может оказаться полезным при анализе ошибочного решения. Так, если в изображении дерева с обратной связью имеется вершина, соединенная со своей родительским вершиной не двойной, а одинарной линией, значит, у этой вершины поле Parent содержит ошибочное значение (например, равно NULL).

Специальное обозначение предусмотрено также для ситуации, когда корень дерева с обратной связью имеет значение, отличное от NULL. Эту ситуацию можно промоделировать с помощью приведенной выше программы, если изменить стартовый вызов функции SetParent, например, следующим образом:

[C/C++]

SetParent(p1, p1);

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

Признаком ошибочного значения поля Parent для корня полученного дерева является красная звездочка, отображаемая выше этого корня.

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

Деревья общего вида

С помощью связанных записей типа TNode можно моделировать не только бинарные деревья, но и произвольные упорядоченные деревья, вершины которых имеют любое число непосредственных потомков (будем называть такие деревья деревьями общего вида; для них также используется название «деревья с множественным ветвлением»). Рассмотрим задание Tree86 — первое из заданий, связанных с деревьями общего вида, в котором описываются особенности подобных деревьев.

Tree86°. Дерево общего вида (каждая вершина которого может иметь произвольное число дочерних вершин, расположенных в фиксированном порядке в направлении слева направо) реализуется с помощью набора связанных записей типа TNode следующим образом: для каждой внутренней вершины ее поле Left содержит указатель на ее первую (т. е. левую) дочернюю вершину, а поле Right — указатель на ее правую сестру, т. е. вершину, имеющую в дереве общего вида того же родителя. Поле Right корня дерева общего вида всегда равно NULL, так как корень сестер не имеет. Дан указатель P₁ на корень непустого бинарного дерева. Создать дерево общего вида, соответствующее исходному бинарному дереву, и вывести указатель P₂ на его корень.

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

Корень этого дерева (со значением 13) имеет три дочерние вершины (71, 73 и 29), причем вершина 71 не имеет потомков, вершина 73 имеет три непосредственных потомка (18, 93 и 92), а вершина 29 — два (24 и 84). На последнем уровне располагается вершина 46, являющаяся единственной дочерней вершиной вершины 93.

При ознакомительном запуске задания Tree86 на экране появится окно, подобное следующему.

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

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

При формировании нового дерева будем использовать рекурсивную функцию CreateNode(p). Параметр p содержит указатель на вершину исходного дерева, копия которой создается при вызове функции. Возвращаемым значением функции является указатель на созданную вершину (как обычно, если указатель p равен NULL, то функция не выполняет никаких действий и возвращает NULL). Для создания дочерних вершин выполняется рекурсивный вызов этой функции. Заметим, что цепочка дочерних вершин может быть пустой (если вершина p является листом), содержать один элемент (если вершина p имеет только одного непосредственного потомка) или два элемента. Перед формированием цепочки дочерних вершин удобно занести адреса дочерних вершин вершины p во вспомогательные переменные p1 и p2. При этом в случае, если вершина p имеет только одного потомка (неважно, левого или правого), адрес этого потомка заносится в переменную p1, а переменная p2 остается равной NULL. Благодаря использованию переменных p1 и p2, фрагмент кода, отвечающий за формирование списка дочерних вершин, удается сделать более кратким. Приведем реализацию данной рекурсивной функции:

[C/C++]

PNode CreateNode(PNode p) // вариант 1
{
    if (p == NULL)
        return NULL;
    PNode pnew = (PNode)malloc(sizeof(TNode));
    pnew->Data = p->Data;
    pnew->Right = NULL;
    PNode p1 = p->Left, p2 = p->Right;
    if (p1 == NULL)
    {
        p1 = p2;
        p2 = NULL;
    }
    // формирование списка дочерних вершин
    pnew->Left = CreateNode(p1);
    if (p1 != NULL)
        pnew->Left->Right = CreateNode(p2);
    return pnew;
}

Функция Solve включает, как обычно, ввод исходных данных, вызов вспомогательной рекурсивной функции и вывод результатов:

[C/C++]

Task("Tree86");
PNode p1;
GetP(&p1);
PutP(CreateNode(p1));

Описанный выше рекурсивный алгоритм решения задачи Tree86 является достаточно естественным, но имеет большой размер. Приведем еще один вариант рекурсивного алгоритма, в котором рекурсивной функции передается два параметра: указатель p на обрабатываемую вершину исходного бинарного дерева и указатель rightnew, используемый при определении поля Right создаваемой вершины (если эта вершина не равна NULL). Применение этого дополнительного параметра позволяет существенно сократить размер программного кода:

PNode CreateNode(PNode p, PNode rightnew) // вариант 2
{
    if (p == NULL)
        return rightnew;
    PNode pnew = (PNode)malloc(sizeof(TNode));
    pnew->Data = p->Data;
    pnew->Right = rightnew;
    pnew->Left = CreateNode(p->Left, CreateNode(p->Right, NULL));
    return pnew;
}

Обратите внимание на две интересные особенности данного алгоритма: наличие двух рекурсивных вызовов (обеспечивающих формирование цепочки из одной или двух дочерних вершин, связанных полями Right) и особая обработка ситуации p == NULL, при которой возвращается не значение NULL, а значение параметра rightnew (это позволяет правильно сформировать цепочку дочерних вершин в ситуации, когда левая дочерняя вершина отсутствует, а правая существует).

Примечание. Фрагмент дерева общего вида, содержащий все дочерние вершины некоторой вершины, можно рассматривать как односвязный список, элементы которого связаны между собой с помощью поля Right (у последнего элемента списка поле Right равно NULL). Каждый элемент подобного списка может содержать «подсписок» своих дочерних элементов; адрес начала этого подсписка хранится в поле Left данного элемента. Поэтому в алгоритмах, связанных с обработкой вершин деревьев общего вида, для перебора непосредственных потомков некоторой вершины удобно использовать цикл (как при переборе элементов списка), в то время как для обработки каждой дочерней вершины следует, как обычно, использовать рекурсию.

Разработка сайта:
М. Э. Абрамян, В. Н. Брагилевский

Последнее обновление:
01.01.2024