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

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

В заданиях группы Tree для языков платформы .NET, как и в заданиях группы Dynamic, мы встречаемся с двумя новыми видами данных: это объекты-узлы типа Node, а также древовидные динамические структуры, реализованные в виде наборов связанных друг с другом объектов-узлов. Класс Node не входит в стандартную библиотеку классов .NET Framework; он определен в задачнике Programming Taskbook, а точнее, в сборке pt4net.dll (или в файле pt4core.cs для среды VS Code).

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

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

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

Напомним, что программу-заготовку для решения задания можно создать с помощью модуля PT4Load. В созданный проект будет входить файл с именем Tree2; его расширение зависит от выбранного языка: .cs для C#, .vb для VB.NET и .fs для F#. Приведем текст этих файлов без начальных директив:

[C#]

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

[VB.NET]

Sub Solve()
    Task("Tree2")
End Sub

[F#]

let Solve = pt.Task "Tree2"

После запуска программы на экране появится окно задачника. На рисунке приводится вид окна в режиме с динамической компоновкой (в качестве языка программирования используется C#).

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

Начнем с описания того, как отображается на экране дерево. Для его вывода используется несколько экранных строк. На каждой строке изображаются вершины дерева, находящиеся на определенном уровне (номер уровня указывается слева от изображения дерева). Для каждой вершины выводится ее значение, т. е. значение свойства Data соответствующего объекта типа Node. Любая вершина соединяется линиями со своими дочерними вершинами, расположенными на следующем уровне дерева; левая дочерняя вершина изображается слева от родительской вершины, а правая — справа. Отсутствие у вершины одной или обеих дочерних вершин означает, что ее свойства Left и/или Right содержат нулевую ссылку (null в C# и F#, Nothing в VB.NET).

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

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

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

A₁ = Node

Здесь текст «A₁ =» является комментарием и выделяется, как обычный комментарий, светло-серым цветом, а текст «Node», выделенный желтым цветом, означает, что этот элемент исходных данных является объектом типа Node, который надо ввести в программу с помощью функции GetNode. Если в задании требуется передать задачнику некоторую ссылку, связанную с вершиной дерева, то необходимо использовать процедуру вывода Put. Более подробно работа с исходными и результирующими данными типа Node обсуждается в разделе, посвященном линейным динамическим структурам.

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

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

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

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

[C#]

static int NodeCount(Node a)
{
    return a == null ? 0 : 1 + NodeCount(a.Left) + NodeCount(a.Right);
}
public static void Solve()
{
    Task("Tree2");
    Put(NodeCount(GetNode()));
}

[VB.NET]

Function NodeCount(ByVal a As Node) As Integer
    If a Is Nothing Then
        Return 0
    Else
        Return 1 + NodeCount(a.Left) + NodeCount(a.Right)
    End If
End Function
Sub Solve()
    Task("Tree2")
    Put(NodeCount(GetNode()))
End Sub

[F#]

let Solve = pt.Task "Tree2"
let rec NodeCount(x : Node) =
    if x <> null then
        1 + NodeCount(x.Left) + NodeCount(x.Right)
    else
        0
pt.Put(NodeCount(pt.GetNode()))

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

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

Примечание 1. Начиная с версии 4.15, в вариант задачника для некоторых языков (в том числе для всех языков платформы .NET) включена группа GCTree, отличающаяся от группы Tree тем, что при выполнении заданий группы GCTree на удаление вершин дерева (эти задания имеют номера 40–43, 55) не требуется освобождать ресурсы, связанные с удаляемыми вершинами (предполагается, что эти действия автоматически выполняются специальным сборщиком мусора — Garbage Collector, GC).

Примечание 2. Приведем еще один вариант решения задачи для языка F#, в котором используется сравнение с образцом (pattern matching); при этом первая ветка данного сравнения обрабатывает непустой узел дерева, а вторая ветка содержит универсальный параметр _, позволяющий обработать все прочие ситуации:

[F#]

let Solve = pt.Task "Tree2"
let rec NodeCount x =
    match x with
    | (x : Node) when x <> null ->
        1 + NodeCount(x.Left) + NodeCount(x.Right)
    | _ -> 0
pt.Put(NodeCount(pt.GetNode()))

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

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

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

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

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

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

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

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

[C#]

static void SetParent(Node a, Node par)
{
    if (a == null)
        return;
    a.Parent = par;
    SetParent(a.Left, a);
    SetParent(a.Right, a);
}
public static void Solve()
{
    Task("Tree49");
    SetParent(GetNode(), null);
}

[VB.NET]

Sub SetParent(ByVal a As Node, ByVal par As Node)
    If a Is Nothing Then
        Return
    End If
    a.Parent = par
    SetParent(a.Left, a)
    SetParent(a.Right, a)
End Sub
Sub Solve()
    Task("Tree49")
    SetParent(GetNode(), Nothing)
End Sub

[F#]

let Solve = pt.Task "Tree49"
let rec SetParent (a : Node, par : Node) =
    if a = null then
        ()
    else
        a.Parent <- par
        SetParent(a.Left, a)
        SetParent(a.Right, a)
SetParent(pt.GetNode(), null)

Обратите внимание, что в языке F# выражение () обозначает возвращаемое значение типа unit; таким способом оформляются функции, не возвращающие значения (аналог void-функций для языка C#).

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

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

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

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

[C#]

Node a1 = GetNode();
SetParent(a1, a1);

[VB.NET]

Dim a1 = GetNode()
SetParent(a1, a1)

[F#]

let a1 = pt.GetNode()
SetParent(a1, a1)

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

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

Если переключиться в режим с фиксированной компоновкой (нажав клавишу [F4]), то окно изменится следующим образом:

В данном режиме все разделы с заданием имеют фиксированную высоту, равную 5 экранным строкам. Поэтому формулировка задания отображается частично, а справа от нее выводится полоса прокрутки. Кроме того, раздел результатов содержит дополнительные элемент — направленную вниз стрелку, расположенную рядом с номером уровня 3. Наличие этой стрелки означает, что в дереве имеются уровни, которые в данный момент не отображаются на экране. В нашем случае это уровень 4, который сместился за нижнюю границу раздела результатов из-за того, что первая строка этого раздела была отведена для вывода звездочки. Для отображения на экране этого уровня достаточно «прокрутить» изображение дерева (действия для прокрутки дерева аналогичны действиям для прокрутки текстовых файлов: можно использовать клавиши со стрелками, клавиши [Home], [End], [PgUp] и [PgDn], полосу прокрутки слева от изображения дерева, а также колесико мыши после наведения курсора мыши на раздел результатов). При прокрутке дерева вниз в окне задачника скрывается верхняя часть изображения дерева; в этом случае рядом с номером первого уровня, изображенного в окне, выводится направленная вверх стрелка, являющаяся признаком того, что для дерева доступна прокрутка вверх.

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

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

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

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

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

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

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

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

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

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

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

При формировании нового дерева будем использовать рекурсивную функцию CreateNode(a). Параметр a содержит вершину исходного дерева, копия которой создается при вызове функции. Возвращаемым значением функции является созданная вершина (как обычно, если исходная вершина a содержит нулевую ссылку, то функция не выполняет никаких действий и возвращает нулевую ссылку). Для создания дочерних вершин выполняется рекурсивный вызов этой функции. Заметим, что цепочка дочерних вершин может быть пустой (если вершина a является листом), содержать один элемент (если вершина a имеет только одного непосредственного потомка) или два элемента. Перед формированием цепочки дочерних вершин удобно занести ссылки на дочерние вершины вершины a во вспомогательные переменные a1 и a2. При этом в случае, если вершина a имеет только одного потомка (неважно, левого или правого), ссылка на этого потомка заносится в переменную a1, а переменная a2 остается равной null (Nothing в VB.NET). Благодаря использованию переменных a1 и a2, фрагмент кода, отвечающий за формирование списка дочерних вершин, удается сделать более кратким. Приведем текст программы, решающей задачу Tree86.

[C#]

static Node CreateNode(Node a)
{
    if (a == null)
        return null;
    Node res = new Node(a.Data),
        a1 = a.Left, a2 = a.Right;
    if (a1 == null)
    {
        a1 = a2;
        a2 = null;
    }
    // формирование списка дочерних вершин
    res.Left = CreateNode(a1);
    if (a1 != null)
        res.Left.Right = CreateNode(a2);
    return res;
}
public static void Solve()
{
    Task("Tree86");
    Put(CreateNode(GetNode()));
}

[VB.NET]

Function CreateNode(ByVal a As Node) As Node
    If a Is Nothing Then
        Return Nothing
    End If
    Dim res = New Node(a.Data), _
        a1 = a.Left, a2 = a.Right
    If a1 Is Nothing Then
        a1 = a2
        a2 = Nothing
    End If
    ' формирование списка дочерних вершин
    res.Left = CreateNode(a1)
    If Not a1 Is Nothing Then
        res.Left.Right = CreateNode(a2)
    End If
    Return res
End Function
Sub Solve()
    Task("Tree86")
    Put(CreateNode(GetNode()))
End Sub

[F#]

let Solve = pt.Task "Tree86"
let rec CreateNode(a : Node) =
    if a <> null then
        let res = new Node(a.Data)
        let mutable a1 = a.Left
        let mutable a2 = a.Right
        if a1 = null then
            a1 <- a2
            a2 <- null
        // формирование списка дочерних вершин
        res.Left <- CreateNode(a1)
        if a1 <> null then
            res.Left.Right <- CreateNode(a2)
        res
    else
        null
pt.Put(CreateNode(pt.GetNode()))

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

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

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