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

[Pascal]

type
PNode = ^TNode;
TNode = record
Data: integer;
Left: PNode;
Right: PNode;
Parent: PNode;
end;

[C/C++]

struct Node; typedef struct Node TNode; typedef struct Node *PNode; struct Node
{
int Data;
PNode Left;
PNode Right;
PNode Parent;
};

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

Значением вершины дерева (т. е. записи типа TNode) считается значение его поля Data.

Так как переменные типа «указатель» предназначены для хранения адресов, в формулировках заданий слова «указатель» (на вершину дерева) и «адрес» (вершины дерева) используются как синонимы.

В программах на языке Pascal для освобождения динамической памяти, связанной с указателем p типа PNode, следует использовать процедуру Dispose(p), в программах на языке C — функцию DeleteNode(p), в программах на языке C++ — оператор delete p или функцию DeleteNode(p).

Приведенные ниже формулировки ориентированы на язык Pascal; в варианте для языков C/C++ в качестве имени нулевого указателя используется NULL.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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°. Дан указатель P₁ на корень непустого дерева. Создать копию данного дерева и вывести указатель P₂ на корень созданной копии.

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

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

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

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

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

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

Tree40°. Дан указатель P₁ на корень непустого дерева. Удалить из дерева все вершины, кроме корня, и освободить память, которую занимали удаленные вершины (полям Left и Right корня следует присвоить значение nil).

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

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

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

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

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

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

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

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

Tree48. Дан адрес P₁ вершины дерева — записи типа TNode, содержащей поля Data (целого типа), Left, Right и Parent (типа PNode — указателя на TNode). Поля Left и Right указывают на дочерние вершины, а поле Parent — на родительскую вершину данной вершины (если вершина является корнем дерева, то ее поле Parent равно nil). Для данной вершины вывести указатели P_L, P_R и P₀ на ее левую и правую дочерние вершины и родительскую вершину, а также указатель P₂ на ее сестру, т. е. другую вершину дерева, имеющую в качестве родительской вершину с адресом P₀. Если некоторые из перечисленных вершин не существуют, то вывести для них значение nil.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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