Обратите также внимание на то, что в области результатов отсутствуют какие-либо данные, кроме измененного дерева. Это означает, что в программе, решающей задачу, не требуется использовать процедуры вывода; достаточно лишь преобразовать исходное дерево требуемым образом. Поскольку при таком преобразовании адрес корня дерева P1 не изменится, задачник сможеть получить доступ к этому дереву и проверить его правильность.
Для преобразования исходного дерева в дерево с обратной связью необходимо задать правильные значения для полей 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.
Примечание. Обозначение для двойной связи может оказаться полезным при анализе ошибочного решения. Так, если в изображении дерева с обратной связью имеется вершина, соединенная со своей родительским вершиной не двойной, а одинарной линией, значит, у этой вершины поле Parent содержит ошибочное значение (например, равно nil).
С помощью связанных записей типа TNode можно моделировать не только бинарные деревья, но и произвольные упорядоченные деревья, вершины которых имеют любое число непосредственных потомков (будем называть такие деревья деревьями общего вида; для них также используется название деревья с множественным ветвлением"). Рассмотрим задание Tree86 -- первое из заданий, связанных с деревьями общего вида, в котором описываются особенности подобных деревьев.
Tree86°. Дерево общего вида (каждая вершина которого может иметь произвольное число дочерних вершин, расположенных в фиксированном порядке в направлении слева направо) реализуется с помощью набора связанных записей типа TNode следующим образом: для каждой внутренней вершины ее поле Left содержит указатель на ее первую (т. е. левую) дочернюю вершину, а поле Right -- указатель на ее правую сестру, т. е. вершину, имеющую в дереве общего вида того же родителя. Поле Right корня дерева общего вида всегда равно nil, так как корень сестер не имеет. Дан указатель P1 на корень непустого бинарного дерева. Создать дерево общего вида, соответствующее исходному бинарному дереву, и вывести указатель P2 на его корень.
Приведем пример дерева общего вида, которое реализовано с помощью связанных записей типа TNode (аналогичным образом деревья общего вида изображаются в окне задачника):
Корень этого дерева (со значением 13) имеет три дочерние вершины (71, 73 и 29), причем вершина 71 не имеет потомков, вершина 73 имеет три непосредственных потомка (18, 93 и 92), а вершина 29 -- два (24 и 84). На последнем уровне располагается вершина 46, являющаяся единственной дочерней вершиной вершины 93.
При ознакомительном запуске задания Tree86 на экране появится окно, подобное следующему.
Обратите внимание на то, как выглядит одно и то же дерево в двух различных представлениях: вариант, соответствующий обычному бинарному дереву, приводится в разделе исходных данных, а вариант, соответствующий дереву общего вида, -- в разделе результатов. При переходе от бинарного дерева к дереву общего вида часть информации о структуре бинарного дерева теряется, поскольку в случае, если некоторая вершина дерева общего вида имеет только одного непосредственного потомка, нельзя определить, каким был этот потомок в исходном бинарном дереве -- левым или правым.
Напомним, что точки, обрамляющие значения вершин в разделе результатов, означают, что все эти вершины должны быть созданы программой учащегося (в отличие от вершин исходного дерева, созданных самим задачником при инициализации задания).
При формировании нового дерева будем использовать рекурсивную функцию CreateNode(P). Параметр P содержит указатель на вершину исходного дерева, копия которой создается при вызове функции. Возвращаемым значением функции является указатель на созданную вершину (как обычно, если P = nil, то функция не выполняет никаких действий и возвращает nil). Для создания дочерних вершин выполняется рекурсивный вызов этой функции. Заметим, что цепочка дочерних вершин может быть пустой (если вершина P является листом), содержать один элемент (если вершина P имеет только одного непосредственного потомка) или два элемента. Перед формированием цепочки дочерних вершин удобно занести адреса дочерних вершин вершины P во вспомогательные переменные P1 и P2. При этом в случае, если вершина P имеет только одного потомка (неважно, левого или правого), адрес этого потомка заносится в переменную P1, а переменная P2 остается равной nil. Благодаря использованию переменных P1 и P2, фрагмент кода, отвечающий за формирование списка дочерних вершин, удается сделать более кратким. Приведем текст программы, решающей задачу Tree86.
uses PT4;
function CreateNode(P: PNode): PNode;
var P1, P2: PNode;
begin
if P = nil then
begin
result := nil;
exit;
end;
New(result);
result^.Data := P^.Data;
result^.Right := nil;
P1 := P^.Left;
P2 := P^.Right;
if P1 = nil then
begin
P1 := P2;
P2 := nil;
end;
{ формирование списка дочерних вершин }
result^.Left := CreateNode(P1);
if P1 <> nil then
result^.Left^.Right := CreateNode(P2);
end;
var P1: PNode;
begin
Task('Tree86');
read(P1);
write(CreateNode(P1));
end.
Примечание. Фрагмент дерева общего вида, содержащий все дочерние вершины некоторой вершины, можно рассматривать как односвязный список, элементы которого связаны между собой с помощью поля Right (у последнего элемента списка поле Right равно nil). Каждый элемент подобного списка может содержать подсписок" своих дочерних элементов; адрес начала этого подсписка хранится в поле Left данного элемента. Поэтому в алгоритмах, связанных с обработкой вершин деревьев общего вида, для перебора непосредственных потомков некоторой вершины удобно использовать цикл (как при переборе элементов списка), в то время как для обработки каждой дочерней вершины следует, как обычно, использовать рекурсию.