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

Все числа, используемые в заданиях на деревья, являются целыми. Все объекты имеют тип Node, который определен в задачнике Programming Taskbook. В заданиях на деревья у объектов типа Node используются свойства Data, Left, Right и Parent, поэтому при выполнении заданий можно считать, что класс Node включает следующие открытые свойства и методы:

[PascalABC.NET]

// Конструкторы:
constructor Create;
constructor Create(aData: integer);
constructor Create(aLeft, aRight: Node; aData: integer);
constructor Create(aLeft, aRight: Node; aData: integer; aParent: Node);
// Свойства (доступны для чтения и для записи):
property Data: integer;
property Left: Node;
property Right: Node;
property Parent: Node;
// Метод, освобождающий ресурсы, используемые объектом:
procedure Dispose;

[C#]

// Конструкторы:
public Node();
public Node(int aData);
public Node(Node aLeft, Node aRight, int aData);
public Node(Node aLeft, Node aRight, int aData, Node aParent);
// Свойства (доступны для чтения и для записи):
public int Data;
public Node Left;
public Node Right;
public Node Parent;
// Метод, освобождающий ресурсы, используемые объектом Node:
public void Dispose();

[VB.NET]

' Конструкторы:
Public Sub New()
Public Sub New(aData As Integer)
Public Sub New(aLeft As Node, aRight As Node, _
aData As Integer)
Public Sub New(aLeft As Node, aRight As Node, _
aData As Integer, aParent As Node)
' Свойства (доступны для чтения и для записи):
Public Property Data() As Integer
Public Property Left() As Node
Public Property Right() As Node
Public Property Parent() As Node
' Метод, освобождающий ресурсы, используемые объектом Node:
Public Sub Dispose() Implements IDisposable.Dispose

[F#]

// Конструкторы:
public new()
public new(aData: int)
public new(aLeft: Node, aRight: Node, aData: int)
public new(aLeft: Node, aRight: Node, aData: int, aParent: Node)
// Свойства (доступны для чтения и для записи):
public Data: int
public Left: Node
public Right: Node
public Parent: Node
// Метод, освобождающий ресурсы, используемые объектом Node:
public Dispose()

[Java]

// Конструкторы:
Node();
Node(int aData);
Node(Node aLeft, Node aRight, int aData);
Node(Node aLeft, Node aRight, int aData, Node aParent);
// Методы для доступа к свойствам:
int getData();
void setData(int value);
Node getLeft();
void setLeft(Node value);
Node getRight();
void setRight(Node value);
Node getParent();
void setParent(Node value);
// Метод, освобождающий ресурсы, используемые объектом Node:
void dispose();

[Python]

# Конструкторы:
Node(data = 0)
Node.for_tree(data = 0, left = None, right = None, parent = None)
# Свойства (доступны для чтения и для записи):
Data
Left
Right
Parent
# Метод, освобождающий ресурсы, используемые объектом Node:
dispose()

[Ruby]

# Конструкторы:
Node.new()
Node.new(data)
Node.new(left, right, data)
Node.new(left, right, data, parent)
# Свойства (доступны для чтения и для записи):
data
left
right
parent
# Метод, освобождающий ресурсы, используемые объектом Node:
dispose()

[Julia]

# Конструкторы:
node()
node(data::Integer)
node(left::Node, right::Node, data::Integer)
node(left::Node, right::Node, data::Integer, parent::Node)
# Функции для доступа к свойствам (символ ! означает изменение свойства):
data(node::Node)
data!(node::Node, value::Integer)
left(node::Node)
left!(node::Node, value::Node)
right(node::Node)
right!(node::Node, value::Node)
parent(node::Node)
parent!(node::Node, value::Node)
# Функция, освобождающая ресурсы, используемые объектом Node:
dispose!(node::Node)

В большинстве заданий при работе с объектами типа Node требуются только свойства Data, Left и Right; свойство Parent используется лишь в заданиях на обработку дереьев с обратной связью.

Значением вершины дерева (т. е. объекта типа Node) считается значение ее свойства Data.

Так как во всех рассматриваемых языках принята ссылочная объектная модель, т. е. любая переменная объектного типа является ссылкой на ту область памяти, в которой фактически размещен данный объект, выражение «вывести ссылку на вершину дерева» в формулировках заданий всегда означает, что требуется вывести значение переменной типа Node, связанной с этой вершиной.

Значением вершины дерева (т. е. объекта типа Node) считается значение ее свойства Data.

Приведенные ниже формулировки ориентированы на язык C#; в вариантах для других языков используются имена нулевых ссылок, соответствующие этим языкам.

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

Tree1. Дан объект A₁ типа Node, имеющий открытые свойства Data (целого типа), Left и Right (типа Node). Свойства Left и Right этого объекта (корня дерева) содержат ссылки на левую и правую дочерние вершины (того же типа Node). Вывести значения свойств Data корня, его левой и правой дочерних вершин, а также ссылки на левую и правую дочерние вершины в указанном порядке.

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

Tree3. Дан корень A₁ непустого дерева и число K. Вывести количество вершин дерева, значение которых равно K.

Tree4. Дан корень A₁ непустого дерева. Вывести сумму значений всех вершин данного дерева.

Tree5. Дан корень A₁ непустого дерева. Вывести количество вершин дерева, являющихся левыми дочерними вершинами (корень дерева не учитывать).

Tree6°. Дан корень A₁ непустого дерева. Листом дерева называется его вершина, не имеющая дочерних вершин. Вывести количество листьев для данного дерева.

Tree7. Дан корень A₁ непустого дерева. Вывести сумму значений всех листьев данного дерева.

Tree8. Дан корень A₁ дерева, содержащего по крайней мере две вершины. Вывести количество листьев дерева, являющихся правыми дочерними вершинами.

Tree9°. Дан корень A₁ непустого дерева. Считается, что корень дерева находится на нулевом уровне, его дочерние вершины — на первом уровне и т. д. Вывести глубину дерева, т. е. значение его максимального уровня (например, глубина дерева, состоящего только из корня, равна 0).

Tree10. Дан корень A₁ непустого дерева. Для каждого из уровней данного дерева, начиная с нулевого, вывести количество вершин, находящихся на этом уровне. Считать, что глубина дерева не превосходит 10.

Tree11. Дан корень A₁ непустого дерева. Для каждого из уровней данного дерева, начиная с нулевого, вывести сумму значений вершин, находящихся на этом уровне. Считать, что глубина дерева не превосходит 10.

Tree12°. Дан корень A₁ непустого дерева. Вывести значения всех вершин дерева в инфиксном порядке (вначале выводится содержимое левого поддерева в инфиксном порядке, затем выводится значение корня, затем — содержимое правого поддерева в инфиксном порядке).

Tree13°. Дан корень A₁ непустого дерева. Вывести значения всех вершин дерева в префиксном порядке (вначале выводится значение корня, затем содержимое левого поддерева в префиксном порядке, затем — содержимое правого поддерева в префиксном порядке).

Tree14. Дан корень A₁ непустого дерева. Вывести значения всех вершин дерева в постфиксном порядке (вначале выводится содержимое левого поддерева в постфиксном порядке, затем — содержимое правого поддерева в постфиксном порядке, затем — значение корня).

Tree15. Дан корень A₁ непустого дерева и число N (> 0), не превосходящее количество вершин в исходном дереве. Нумеруя вершины в инфиксном порядке (см. задание Tree12, нумерация ведется от 1), вывести значения всех вершин с порядковыми номерами от 1 до N.

Tree16. Дан корень A₁ непустого дерева и число N (> 0), не превосходящее количество вершин в исходном дереве. Нумеруя вершины в постфиксном порядке (см. задание Tree14, нумерация ведется от 1), вывести значения всех вершин с порядковыми номерами от N до максимального номера.

Tree17. Дан корень A₁ непустого дерева и два числа N₁, N₂ (0 < N₁ < N₂), которые не превосходят количество вершин в исходном дереве. Нумеруя вершины в префиксном порядке (см. задание Tree13, нумерация ведется от 1), вывести значения всех вершин с порядковыми номерами от N₁ до N₂.

Tree18. Дан корень A₁ непустого дерева и неотрицательное число L. Используя любой из описанных в заданиях Tree12−Tree14 способов обхода дерева, вывести значения всех вершин уровня L, а также их количество N (если дерево не содержит вершин уровня L, то вывести 0).

Tree19. Дан корень A₁ непустого дерева. Вывести максимальное из значений его вершин и количество вершин, имеющих это максимальное значение.

Tree20. Дан корень A₁ непустого дерева. Вывести минимальное из значений всех его вершин и количество листьев, имеющих это минимальное значение (данное количество может быть равно 0).

Tree21. Дан корень A₁ непустого дерева. Вывести минимальное из значений его вершин, являющихся листьями.

Tree22. Дан корень A₁ дерева, содержащего по крайней мере две вершины. Вывести максимальное из значений его внутренних вершин (т. е. вершин, не являющихся листьями).

Tree23. Дан корень A₁ непустого дерева. Вывести ссылку A₂ на первую вершину дерева с минимальным значением (вершины перебирать в префиксном порядке).

Tree24. Дан корень A₁ непустого дерева. Вывести ссылку A₂ на последнюю вершину дерева с максимальным нечетным значением (вершины перебирать в инфиксном порядке). Если дерево не содержит вершин с нечетными значениями, то вывести null.

Формирование бинарного дерева

Tree25. Дано число N (> 0) и набор из N чисел. Создать дерево из N вершин, в котором каждая вершина (кроме корня) является правой дочерней вершиной. Каждой создаваемой вершине присваивать очередное значение из исходного набора. Вывести ссылку на корень созданного дерева.

Tree26. Дано число N (> 0) и набор из N чисел. Создать дерево из N вершин, в котором каждая внутренняя вершина имеет только одну дочернюю вершину, причем правые и левые дочерние вершины чередуются (корень имеет левую дочернюю вершину). Каждой создаваемой вершине присваивать очередное значение из исходного набора. Вывести ссылку на корень созданного дерева.

Tree27. Дано число N (> 0) и набор из N чисел. Создать дерево из N вершин, в котором каждая внутренняя вершина имеет только одну дочернюю вершину, причем если значение вершины является нечетным, то она имеет левую дочернюю вершину, а если четным, то правую. Каждой создаваемой вершине присваивать очередное значение из исходного набора. Вывести ссылку на корень созданного дерева.

Tree28. Дано четное число N (> 0) и набор из N чисел. Создать дерево из N вершин, в котором каждая левая дочерняя вершина является листом, а правая дочерняя вершина является внутренней. Для каждой внутренней вершины вначале создавать левую дочернюю вершину, а затем правую (если она существует); каждой создаваемой вершине присваивать очередное значение из исходного набора. Вывести ссылку на корень созданного дерева.

Tree29. Дано четное число N (> 0) и набор из N чисел. Создать дерево из N вершин со следующей структурой: если вершина дерева является внутренней, то в случае, если она имеет нечетное значение, ее левая дочерняя вершина должна быть листом, а в случае, если она имеет четное значение, листом должна быть ее правая вершина. Для каждой внутренней вершины вначале создавать дочернюю вершину-лист, а затем дочернюю внутреннюю вершину (если данная вершина существует); каждой создаваемой вершине присваивать очередное значение из исходного набора. Вывести ссылку на корень созданного дерева.

Tree30. Дано число N (> 0). Создать дерево, корень которого имеет значение N, а вершины обладают следующими свойствами: вершина с четным значением K имеет левую дочернюю вершину со значением K/2 и не имеет правой дочерней вершины; вершина со значением 1 является листом; вершина с любым другим нечетным значением K имеет две дочерние вершины: левую со значением K/2 и правую со значением K − K/2 (символ «/» обозначает операцию деления нацело). Вывести ссылку на корень созданного дерева.

Tree31. Даны положительные числа L, N (N > L) и набор из N чисел. Создать дерево глубины L, содержащее вершины со значениями из исходного набора. Вершины добавлять к дереву в префиксном порядке, используя алгоритм, который для каждой вершины уровня, не превышающего L, вначале создает саму вершину с очередным значением из исходного набора, затем ее левое поддерево соответствующей глубины, а затем ее правое поддерево. Если для заполнения дерева глубины L требуется менее N вершин, то оставшиеся числа из исходного набора не использовать. Вывести ссылку на корень созданного дерева.

Tree32°. Дано число N (> 0) и набор из N чисел. Создать идеально сбалансированное дерево из N вершин с заданными значениями (т. е. дерево, для каждой вершины которого количество вершин в его левом и правом поддереве отличается не более чем на 1) и вывести ссылку на его корень. Для создания дерева использовать рекурсивный алгоритм, который создает вершину дерева с очередным значением, после чего вызывается для создания левого поддерева с N/2 вершинами и правого поддерева с N − 1 − N/2 вершинами (символ «/» обозначает операцию деления нацело).

Tree33. Дано число N (> 0). Создать идеально сбалансированное дерево из N вершин и вывести ссылку на его корень. Значение каждой вершины положить равным уровню этой вершины (например, корень дерева должен иметь значение 0, его дочерние вершины — значение 1 и т. д.). При формировании дерева использовать алгоритм, описанный в задании Tree32.

Tree34°. Дан корень A₁ непустого дерева. Создать копию данного дерева и вывести ссылку A₂ на корень созданной копии.

Преобразование бинарного дерева

Tree35. Дан корень A₁ непустого дерева. Удвоить значение каждой вершины дерева.

Tree36. Дан корень A₁ непустого дерева. Для каждой вершины дерева с четным значением уменьшить ее значение в два раза.

Tree37. Дан корень A₁ непустого дерева. Добавить 1 к значению каждого листа дерева и вычесть 1 из значения каждой внутренней вершины.

Tree38. Дан корень A₁ непустого дерева. Для каждой вершины дерева, имеющей две дочерние вершины, поменять местами значения дочерних вершин (т. е. значения их свойств Data).

Tree39. Дан корень A₁ непустого дерева. Для всех внутренних вершин дерева поменять местами их левые и правые дочерние вершины (т. е. значения свойств Left и Right).

Tree40°. Дан корень A₁ непустого дерева. Удалить из дерева все вершины, кроме корня (свойствам Left и Right корня следует присвоить значение null). После удаления вершин освобождать ресурсы, которые они использовали, вызывая для этих вершин метод Dispose.

Tree41. Дан корень A₁ дерева, содержащего по крайней мере две вершины. Удалить каждую вершину дерева, являющуюся листом; при этом соответствующее свойство родительской вершины (Left или Right) следует положить равным null. После удаления вершин из дерева вызывать для них метод Dispose.

Tree42. Дан корень A₁ непустого дерева. Удалить вершины дерева, имеющие значения, меньшие значения корня, вместе со всеми их дочерними вершинами. После удаления вершин из дерева вызывать для них метод Dispose.

Tree43. Дан корень A₁ непустого дерева. Для вершин дерева, имеющих две дочерние вершины, удалить одну из дочерних вершин: правую, если родительская вершина имеет четное значение, и левую в противном случае (вершины дерева перебирать в префиксном порядке, при удалении вершины удалять и всех ее потомков). Для удаленных вершин вызывать метод Dispose.

Tree44. Дан корень A₁ непустого дерева. Ко всем вершинам дерева, которые являются листьями, добавить по две дочерние вершины-листа: левую со значением 10 и правую со значением 11.

Tree45. Дан корень A₁ непустого дерева. Ко всем вершинам дерева, которые являются листьями, добавить по одной дочерней вершине-листу; при этом к исходной вершине с нечетным значением добавляется левая дочерняя вершина, а к вершине с четным значением — правая. Значение каждой добавленной вершины положить равным значению ее родительской вершины.

Tree46. Дан корень A₁ непустого дерева. Ко всем вершинам дерева, которые содержат ровно по одной дочерней вершине, добавить еще одну дочернюю вершину-лист. Значение каждой добавленной вершины положить равным удвоенному значению ее родительской вершины.

Tree47°. Дан корень A₁ непустого дерева. Не изменяя глубины L исходного дерева, дополнить его до полного дерева, т. е. дерева, все листья которого находятся на уровне L. Значения всех добавленных вершин положить равными −1.

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

Tree48. Дана вершина дерева A₁ — объект типа Node, имеющий открытые свойства Data (целого типа), Left, Right и Parent (типа Node). Свойства Left и Right содержат ссылки на дочерние вершины, а свойство Parent — на родительскую вершину данной вершины (если вершина является корнем дерева, то ее свойство Parent равно null). Для данной вершины вывести ссылки A_L, A_R и A₀ на ее левую и правую дочерние вершины и родительскую вершину, а также ссылку A₂ на ее сестру, т. е. другую вершину дерева, имеющую в качестве родительской вершину A₀. Если некоторые из перечисленных вершин не существуют, то вывести для них значение null.

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

Tree50. Дана ссылка A₁ на одну из вершин дерева с обратной связью. Вывести ссылку A₂ на корень исходного дерева.

Tree51. Даны ссылки A₁, A₂, A₃ на три вершины дерева с обратной связью. Для каждой из данных вершин вывести ее уровень (корень дерева имеет уровень 0).

Tree52. Даны ссылки A₁ и A₂ на две различные вершины дерева с обратной связью. Вывести степень родства вершины A₁ по отношению к вершине A₂ (степень родства равна −1, если вершина A₂ не находится в цепочке предков для вершины A₁; в противном случае степень родства равна L₁ − L₂, где L₁ и L₂ — уровни вершин A₁ и A₂ соответственно).

Tree53°. Даны ссылки A₁ и A₂ на две различные вершины дерева с обратной связью. Вывести ссылку A₀ на вершину дерева, являющуюся ближайшим общим предком вершин A₁ и A₂.

Tree54. Дана ссылка A₁ на одну из вершин дерева с обратной связью. Создать копию данного дерева и вывести ссылку A₂ на корень созданной копии.

Tree55. Дана ссылка A₁ на вершину дерева с обратной связью, которая не является корнем. Если вершина A₁ имеет сестру, то удалить эту сестру вместе со всеми ее потомками (и вызвать для них метод Dispose); если вершина A₁ не имеет сестры, то создать сестру и всех ее потомков в виде копии поддерева с корнем A₁. Вывести ссылку A₀ на родительскую вершину вершины A₁.

Tree56. Даны положительные числа L, N (N > L) и набор из N чисел. Сформировать дерево глубины L с обратной связью, содержащее вершины со значениями из исходного набора. Вершины добавлять к дереву в префиксном порядке, используя алгоритм, который для каждой вершины уровня, не превышающего L, вначале создает саму вершину с очередным значением из исходного набора, затем ее левое поддерево соответствующей глубины, а затем ее правое поддерево. Если для заполнения дерева глубины L требуется менее N вершин, то оставшиеся числа из исходного набора не использовать. Вывести ссылку на корень созданного дерева.

Бинарные деревья поиска

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

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

Tree59°. Дан корень A₁ непустого дерева поиска без повторяющихся элементов и число K. Определить, содержит ли исходное дерево вершину со значением K. Если содержит, то вывести ссылку A₂ на эту вершину, в противном случае вывести null. Вывести также количество N вершин, которые потребовалось проанализировать для выполнения задания.

Tree60. Дан корень A₁ непустого дерева поиска и число K. Вывести количество C вершин исходного дерева, имеющих значение K, а также количество N вершин, которые потребовалось проанализировать для выполнения задания.

Tree61. Дан корень A₁ дерева поиска (если дерево является пустым, то A₁ = null). Также дано число K. Добавить к исходному дереву поиска новую вершину со значением K таким образом, чтобы полученное дерево осталось деревом поиска, и вывести ссылку A₂ на корень полученного дерева. Использовать следующий рекурсивный алгоритм для дерева с корнем A: если A = null, то создать лист со значением K и присвоить объекту A ссылку на созданный лист; если корень A существует, то в случае, если его значение больше K, выполнить алгоритм для свойства Left корня A, иначе выполнить алгоритм для его свойства Right.

Tree62. Дан корень A₁ дерева поиска без повторяющихся элементов (если дерево является пустым, то A₁ = null). Также дано число K. Добавить к исходному дереву поиска новую вершину со значением K таким образом, чтобы полученное дерево осталось деревом поиска без повторяющихся элементов, и вывести ссылку A₂ на корень полученного дерева. Если исходное дерево уже содержит вершину со значением K, то оставить дерево без изменений. Использовать следующий рекурсивный алгоритм для дерева с корнем A: если A = null, то создать лист со значением K и присвоить объекту A ссылку на созданный лист; если корень A существует, то в случае, если его значение больше K, выполнить алгоритм для свойства Left корня A, а в случае, если его значение меньше K, выполнить алгоритм для его свойства Right.

Tree63. Дано число N (> 0) и набор из N чисел, а также корень A₁ дерева поиска (если дерево является пустым, то A₁ = null). Добавить к исходному дереву поиска N новых вершин со значениями из исходного набора таким образом, чтобы полученное дерево осталось деревом поиска, и вывести ссылку A₂ на корень полученного дерева. Для добавления новых вершин использовать алгоритм, описанный в задании Tree61.

Tree64. Дано число N (> 0) и набор из N чисел, а также корень A₁ дерева поиска без повторяющихся элементов (если дерево является пустым, то A₁ = null). Добавить к исходному дереву поиска новые вершины со значениями из исходного набора таким образом, чтобы полученное дерево осталось деревом поиска без повторяющихся элементов, и вывести ссылку A₂ на корень полученного дерева. Для добавления новых вершин использовать алгоритм, описанный в задании Tree62.

Tree65°. Дано число N (> 0) и набор из N чисел. Отсортировать исходный набор чисел, создав для него дерево поиска (алгоритм добавления вершин к дереву поиска описан в задании Tree61). Вывести ссылку A₁ на корень полученного дерева, а также отсортированный набор чисел (для вывода набора чисел выполнить перебор вершин дерева в инфиксном порядке).

Tree66. Дано число N (> 0) и набор из N чисел. Получить отсортированный набор исходных чисел без повторений, создав для исходного набора дерево поиска без повторяющихся элементов (алгоритм добавления вершин к подобному дереву описан в задании Tree62). Вывести ссылку A₁ на корень полученного дерева, а также отсортированный набор чисел без повторений (для вывода набора чисел выполнить перебор вершин дерева в инфиксном порядке).

Tree67. Даны две ссылки: A₁ на корень непустого дерева поиска и A₂ на одну из вершин этого дерева, имеющих не более одной дочерней вершины. Удалить из исходного дерева вершину A₂ так, чтобы полученное дерево осталось деревом поиска (если удаляемая вершина A₂ имеет дочернюю вершину, то эту дочернюю вершину необходимо связать с родительской вершиной вершины A₂). Вывести ссылку A₃ на корень полученного дерева или null, если в результате удаления вершины A₂ дерево стало пустым.

Tree68. Даны два ссылки: A₁ на корень непустого дерева поиска и A₂ на одну из вершин этого дерева, имеющих две дочерние вершины. Удалить из исходного дерева вершину A₂ так, чтобы полученное дерево осталось деревом поиска. Удаление выполнять следующим образом: в левом поддереве вершины A₂ найти вершину A с наибольшим значением, присвоить это наибольшее значение вершине A₂, после чего удалить вершину A, действуя, как в задании Tree67 (поскольку вершина A будет иметь не более одной дочерней вершины).

Tree69. Даны два ссылки: A₁ на корень непустого дерева поиска и A₂ на одну из вершин этого дерева, имеющих две дочерние вершины. Удалить из исходного дерева вершину A₂ так, чтобы полученное дерево осталось деревом поиска. Удаление выполнять следующим образом: в правом поддереве вершины A₂ найти вершину A с наименьшим значением, присвоить это наименьшее значение вершине A₂, после чего удалить вершину A, действуя, как в задании Tree67 (поскольку вершина A будет иметь не более одной дочерней вершины).

Tree70°. Дана ссылка A₁ на одну из вершин непустого дерева поиска с обратной связью. Удалить из исходного дерева вершину A₁ таким образом, чтобы полученное дерево осталось деревом поиска с обратной связью, и вывести ссылку A₂ на корень полученного дерева или null, если в результате удаления дерево стало пустым. Если вершина A₁ имеет две дочерние вершины, то для ее удаления использовать алгоритм, описанный в задании Tree68.

Tree71. Дана ссылка A₁ на одну из вершин непустого дерева поиска с обратной связью. Удалить из исходного дерева вершину A₁ таким образом, чтобы полученное дерево осталось деревом поиска с обратной связью, и вывести ссылку A₂ на корень полученного дерева или null, если в результате удаления дерево стало пустым. Если вершина A₁ имеет две дочерние вершины, то для ее удаления использовать алгоритм, описанный в задании Tree69.

Бинарные деревья разбора выражений

Tree72. Дана строка S, содержащая описание непустого дерева в следующем формате:

<дерево> ::= <пусто> |
<вершина>(<левое поддерево>,<правое поддерево>)
<вершина> ::= <цифра>

Например, «4(2(,),6(,7(3(,),)))» (пробелы отсутствуют). Создать дерево по описанию, приведенному в S, и вывести ссылку на его корень.

Tree73. Дан корень A₁ непустого дерева. Вывести строку с описанием исходного дерева в формате, приведенном в задании Tree72.

Tree74°. Дана строка S, содержащая описание непустого дерева в следующем формате:

<дерево> ::= <вершина> |
<вершина>(<левое поддерево>,<правое поддерево>) |
<вершина>(<левое поддерево>) |
<вершина>(,<правое поддерево>)
<вершина> ::= <цифра>

Например, «4(2,6(,7(3)))» (пробелы отсутствуют, вид описания вершины зависит от того, имеет ли вершина непустое левое и/или правое поддерево). Создать дерево по описанию, приведенному в S, и вывести ссылку на его корень.

Tree75°. Дан корень A₁ непустого дерева. Вывести строку с описанием исходного дерева в формате, приведенном в задании Tree74.

Tree76°. Дана строка S, содержащая описание числового выражения в следующем формате:

<выражение> ::= <цифра> |
(<выражение><знак><выражение>)
<знак> ::= + | − | *

Пробелы в строке отсутствуют. Создать дерево, соответствующее исходному выражению (дерево разбора выражения): каждая внутренняя вершина дерева должна соответствовать одной из трех возможных арифметических операций и иметь значение −1 для операции сложения, −2 для операции вычитания и −3 для операции умножения; левое и правое дочерние поддеревья любой внутренней вершины-операции должны соответствовать выражениям слева и справа от знака операции; листьями полученного дерева должны быть выражения-цифры. Вывести ссылку на корень созданного дерева.

Tree77. Дана строка S, содержащая описание числового выражения в следующем формате (так называемый префиксный бесскобочный формат записи числового выражения):

<выражение> ::= <цифра> |
<знак> <выражение> <выражение>
<знак> ::= + | − | *

Выражения отделяются друг от друга и от знаков операций ровно одним пробелом. Создать дерево разбора выражения и вывести ссылку на его корень. Структура дерева разбора выражения описана в задании Tree76; для каждой вершины-операции ее левое поддерево должно соответствовать первому операнду данной операции, а правое поддерево — второму.

Tree78. Дана строка S, содержащая описание числового выражения в следующем формате (так называемый постфиксный бесскобочный формат записи числового выражения):

<выражение> ::= <цифра> |
<выражение> <выражение> <знак>
<знак> ::= + | − | *

Tree79°. Дан корень A₁ непустого дерева разбора выражения (структура дерева описана в задании Tree76). Вывести значение выражения, определяемого исходным деревом.

Tree80. Дан корень A₁ непустого дерева разбора выражения (структура дерева описана в задании Tree76). Вывести строковое представление соответствующего выражения в формате, приведенном в том же задании:

<выражение> ::= <цифра> |
(<выражение><знак><выражение>)
<знак> ::= + | − | *

Tree81. Дан корень A₁ непустого дерева разбора выражения. Вывести строковое представление соответствующего выражения в префиксном бесскобочном формате (см. задание Tree77).

Tree82. Дан корень A₁ непустого дерева разбора выражения. Вывести строковое представление соответствующего выражения в постфиксном бесскобочном формате (см. задание Tree78).

Tree83. Дана строка S, содержащая описание числового выражения в следующем формате (функция M возвращает максимальное из двух выражений, а m — минимальное):

<выражение> ::= <цифра> | M(<выражение> , <выражение>) |
m(<выражение> , <выражение>)

Пробелы в строке отсутствуют. Создать дерево разбора исходного выражения: каждая внутренняя вершина дерева должна соответствовать одной из двух возможных функций и иметь значение −1 для функции M и −2 для функции m; для каждой вершины-функции ее левое поддерево должно соответствовать первому аргументу функции, а правое поддерево — второму; листьями полученного дерева должны быть выражения-цифры. Вывести ссылку на корень созданного дерева.

Tree84. Дан корень A₁ непустого дерева разбора выражения (структура дерева описана в задании Tree83). Вывести значение выражения, определяемого исходным деревом.

Tree85. Дан корень A₁ непустого дерева разбора выражения (структура дерева описана в задании Tree83). Вывести строковое представление соответствующего выражения в формате, приведенном в том же задании:

<выражение> ::= <цифра> | M(<выражение> , <выражение>) |
m(<выражение> , <выражение>)

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

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

Tree87. Дан корень A₁ непустого дерева общего вида. Любая вершина исходного дерева имеет не более двух дочерних вершин. Создать бинарное дерево, соответствующее исходному дереву общего вида, и вывести ссылку A₂ на его корень. Считать, что первая дочерняя вершина любой вершины дерева общего вида соответствует левой дочерней вершине в бинарном дереве.

Tree88. Дан корень A₁ непустого дерева общего вида. Вывести глубину данного дерева, т. е. значение его максимального уровня, считая, что все вершины-сестры находятся на одном уровне, а корень дерева расположен на уровне 0.

Tree89. Дан корень A₁ непустого дерева общего вида. Для каждого из уровней данного дерева, начиная с уровня 0, вывести количество вершин, находящихся на этом уровне. Считать, что глубина исходного дерева общего вида не превосходит 10.

Tree90. Дан корень A₁ непустого дерева общего вида. Для каждого из уровней данного дерева, начиная с уровня 0, вывести сумму значений вершин, находящихся на этом уровне. Считать, что глубина исходного дерева общего вида не превосходит 10.

Tree91. Дан корень A₁ непустого дерева общего вида. Также дано неотрицательное число L. Перебирая дочерние вершины в заданном порядке (т. е. слева направо), вывести значения всех вершин уровня L и их количество N. Если дерево не содержит вершин уровня L, то вывести 0.

Tree92°. Дан корень A₁ непустого дерева общего вида. Вывести значения всех вершин дерева в инфиксном порядке: вначале выводится содержимое первого (левого) поддерева в инфиксном порядке, затем выводится значение корня, а затем — содержимое остальных поддеревьев в инфиксном порядке (поддеревья перебираются слева направо).

Tree93. Дан корень A₁ непустого дерева общего вида. Вывести значения всех вершин дерева в постфиксном порядке: вначале выводится содержимое каждого поддерева в постфиксном порядке (поддеревья перебираются слева направо), а затем — значение корня.

Tree94. Дан корень A₁ непустого дерева общего вида. Также дано неотрицательное число N. Вывести количество вершин исходного дерева, имеющих ровно N дочерних вершин. Если требуемые вершины отсутствуют, то вывести 0.

Tree95. Дан корень A₁ непустого дерева общего вида. Вывести ссылку A₂ на первую вершину дерева, имеющую наибольшее количество дочерних вершин. Вершины перебирать в инфиксном порядке (см. задание Tree92).

Tree96. Дан корень A₁ непустого дерева общего вида. Вывести ссылку A₂ на последнюю вершину дерева с наибольшей суммой значений дочерних вершин. Вершины перебирать в постфиксном порядке (см. задание Tree93).

Tree97. Дан корень A₁ непустого дерева общего вида. В каждом наборе вершин-сестер заменить все значения вершин (т. е. значения свойств Data) на максимальное из их исходных значений.

Tree98. Дан корень A₁ непустого дерева общего вида. В каждом наборе вершин-сестер изменить порядок следования их значений на противоположный, т. е. поменять местами значения свойства Data первой (левой) и последней (правой) сестры, второй и предпоследней сестры, и т. д.

Tree99. Дана строка S, содержащая описание непустого дерева общего вида в следующем формате:

<дерево> ::= <вершина> |
<вершина>(<список поддеревьев>)
<список поддеревьев> ::= <дерево> |
<дерево>,<список поддеревьев>
<вершина> ::= <цифра>

Например, «3(2,7(6,4,5),8(4(2,3),5(1)))» (пробелы отсутствуют, вершины-сестры перечисляются в порядке слева направо). Создать дерево общего вида по описанию, приведенному в S, и вывести ссылку на его корень.

Tree100. Дан корень A₁ непустого дерева общего вида. Вывести строку с описанием исходного дерева в формате, приведенном в задании Tree99.

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

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