Описание языка PascalABC.NET

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

Таким образом, решение задачи будет иметь следующий вид:

uses PT4;

function NodeCount(P: PNode): integer;

begin

if P = nil then

result := 0

else

result := 1 + NodeCount(P^.Left) + NodeCount(P^.Right);

end;

var P1: PNode;

begin

Task('Tree2');

read(P1);

write(NodeCount(P1));

end.

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

Запустив эту программу пять раз, мы получим сообщение Задание выполнено!".

Пример 2. Бинарные деревья с обратной связью

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

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

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

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

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

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

uses PT4;

procedure SetParent(P, Par: PNode);

begin

if P = nil then

exit;

P^.Parent := Par;

SetParent(P^.Left, P);

SetParent(P^.Right, P);

end;

var P1: PNode;

begin

Task('Tree49');

read(P1);

SetParent(P1, nil);

end.

При стартовом запуске рекурсивной процедуры SetParent в качестве второго параметра указывается nil.