Programming Taskbook


E-mail:

Пароль:

Регистрация пользователя   Восстановление пароля

English

ЮФУ SMBU

Электронный задачник по программированию

©  М. Э. Абрамян (Южный федеральный университет, Университет МГУ-ППИ в Шэньчжэне), 1998–2024

 

Задания | Группы заданий | Tree

PrevNext


Деревья (с применением указателей)

Все числа, используемые в заданиях на деревья, являются целыми. Все указатели имеют тип 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. Дан адрес P1 записи типа TNode с полями Data (целого типа), Left и Right (типа PNode — указателя на TNode). Эта запись (корень дерева) связана полями Left и Right с записями того же типа (левой и правой дочерней вершиной). Вывести значения полей Data корня, его левой и правой дочерних вершин, а также адреса левой и правой дочерних вершин в указанном порядке.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Tree24. Дан указатель P1 на корень непустого дерева. Вывести указатель P2 на последнюю вершину дерева с максимальным нечетным значением (вершины перебирать в инфиксном порядке). Если дерево не содержит вершин с нечетными значениями, то вывести 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°. Дан указатель P1 на корень непустого дерева. Создать копию данного дерева и вывести указатель P2 на корень созданной копии.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


PrevNext

 

Рейтинг@Mail.ru

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

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