Сортировки массивов

Упражнения

Ввод-вывод во всех задачах может быть как стандартным, так и файловым.

SA: Сортировка слиянием (рекурсивная)

Дана последовательность целых чисел. Выведите эти числа в порядке возрастания. Эту задачу нужно решить с использованием рекурсивной реализации сортировки слиянием.

7 3 1 2 4 6 5

1 2 3 4 5 6 7

SB: Сортировка слиянием (нерекурсивная)

Реализуйте нерекурсивный алгоритм сортировки слиянием.

SD: Сортировка списка из 4 элементов

Реализуйте алгоритм сортировки списка из 4 элементов, выполняющий не более 5 сравнений в каждом случае.

Ваша программа должна быть оформлена специальным образом. Скачайте шаблон программы sort4.py. В этом шаблоне описан класс Integer, реализующий минималистичный интерфейс: ввод и вывод целого числа и сравнение целых чисел при помощи оператора “меньше”. При этом производится подсчет числа выполненных сравнений. Программа считывает список и преобразует его элементы к типу Integer. Затем вызывается функция Sort(A) для сортировки списка. Наконец, отсортированный список выводится на экран.

Вам необходимо модифицировать функцию Sort. Вы можете в функции Sort сравнивать объекты при помощи оператора “меньше”, обменивать значения объектов, а также создавать новые переменные — сcылки на уже существующие объекты типа Integer. Исправленная функция Sort должна сортировать список из 4 элементов выполняя не более 5 сравнений. Если число сравнений будет больше 5, будет сгенерирована исключительная ситуация (exception). При этом программа обработает это исключение, выдаст на стандартный поток сообщений об ошибках соответствующее сообщение и программа аварийно закончит работу.

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

3 2 1 4

1 2 3 4

SE: Сортировка списка из 5 элементов

Отсортируйте список из 5 элементов за 7 сравнений. Шаблон программы: sort5.py. Во всем остальном задача аналогична предыдущей.

SF: Незванные гости

За день к школьнику Васе пришло \(N\) незванных гостей. Вася записал время прихода и ухода каждого из гостей. По этим данным определите, какое максимальное число гостей одновременно находилось дома у Васи.

Первая строка входных данных содержит натуральное число \(N\le 10^5\). Далее идет \(N\) строчек, каждая из которых содержит два неотрицательных целых числа: время прихода и ухода каждого гостя. Время прихода каждого гостя не превосходит его время ухода и оба времени не превосходят \(10^9\). Считается, что гость находится дома у Васи с момента прихода до момента ухода включительно.

Программа должна вывести единственное число — максимальное количество гостей, которые одновременно находились дома у Васи.

4
1 4
3 5
0 2
4 5

3

SG: Забор

Как известно, красить забор Тому Сойеру помогали многочисленные друзья. Каждый друг покрасил неcколько подряд идущих досок, при этом какие-то доски могли быть покрашены несколько раз, а какие-то доски могли остаться непокрашенными. Определите общее количество покрашенных досок.

Первая строка файла содержит натуральное число \(N\le 10^5\) — количество друзей Тома Сойера. Далее идет \(N\) пар целых неотрицательных чисел — номер (от начала забора) доски, с которой друг начал красить забор и номер доски, на которой он закончил покраску. Каждый друг покрасил непрерывный участок забора, включая две заданные доски. Номера досок — целые числа от \(0\) до \(10^9\).

Программа должна вывести единственное число — суммарное количество покрашенных досок.

3
1 2
3 4
2 3

4

SH: Дипломы

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось \(n\) дипломов, причём, как оказалось, все они имели одинаковые размеры: \(w\) в ширину и \(h\) в высоту.

Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером \(w\times h\). Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Программа получает на вход три целых числа: \(w\), \(h\), \(n\) (\(1\le w, h, n \le 10^9\)).

Необходимо вывести ответ на поставленную задачу.

2 3 10

9

SI: Провода

Дано \(N\) отрезков провода длиной \(L_1\), \(L_2\), ..., \(L_N\) сантиметров. Требуется с помощью разрезания получить из них \(K\) равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить \(K\) отрезков длиной даже 1 см, необходимо вывести 0.

В первой строке входных данных находятся числа \(N\) и \(К\) (\(1\le N, K \le 10^4\)). В следующих N строках записаны длины проводов по одному числу в строке, не превосходящие \(10^7\).

Выведите одно число - максимально возможную длину куска.

4 11
802
743
457
539

200

SK: Предпраздничная суета

Ограничение по времени в этой задаче - 15 секунд.

Петя и Вася решили устроить одноклассницам чаепитие и заразили своей идеей еще \(K–2\) своих друзей. Они собрались вместе и выбрали в одном довольно известном супермаркете \(P\) тортиков. Настал черед рассчитываться за них.

В магазине есть \(N\) работающих касс, занумерованных числами от \(1\) до \(N\). Про \(i\)-ю кассу известно, что кассиру требуется \(A_i\) единиц времени на обработку одного товара и \(B_i\) единиц времени для того, чтобы рассчитаться с покупателем. Обойдя все кассы, школьники посчитали, что на обслуживание покупателей, уже стоящих в \(i\)-ю кассу, уйдет \(T_i\) единиц времени.

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

В первой строке записано одно число \(N\) — количество касс в супермаркете (\(1 \le N \le 100000)\). В следующих \(N\) строках записано по три числа \(A_i\), \(B_i\), \(T_i\) (\(0 \le A_i, B_i, T_i \le 100000\)). В последней строке записаны два числа — \(K\) и \(P\) — число школьников и покупок у них соответственно (\(0 \le P \le 100000\), \(2 \le K \le 100000\)). Все числа целые.

Выведите минимальное время выхода последнего школьника из магазина.

2
100 10 40
10 100 50
2 2

160

3
1 2 0
5 2 1
2 10 1
3 5

7

SL: Субботник

Ограничение по времени в этой задаче - 10 секунд.

В классе учатся \(N\) человек. Классный руководитель получил указание направить на субботник \(R\) бригад по \(С\) человек в каждой.

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

Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Классный руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Помогите ему в этом!

Рассмотрим следующий пример. Пусть в классе 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две бригады по три человека в каждой. Тогда одним из вариантов является такой:
1 бригада: люди с ростом 225, 205, 225
2 бригада: люди с ростом 160, 190, 170

При этом число неудобства первой бригады будет равно 20, а число неудобства второй — 30. Максимальное из чисел неудобств будет 30, и это будет наилучший возможный результат.

Сначала вводятся натуральные числа \(N\), \(R\) и \(C\) — количество человек в классе, количество бригад и количество человек в каждой бригаде (\(1 \le RC \le N \le 10^5\)). Далее вводятся \(N\) целых чисел — рост каждого из \(N\) учеников. Рост ученика — натуральное число, не превышающее \(10^9\).

Выведите одно число — наименьше возможное значение максимального числа неудобства сформированных бригад.

8 2 3
170
205
225
190
260
130
225
160

30

SM: Пирамидальная сортировка

Реализуйте нерекурсивный алгоритм пирамидальной сортировки.

SN: Очередь с приоритетами - увеличение приоритета

Дана очередь с приоритетами, представленная в виде кучи (вверху — наибольший элемент). Дана последовательность запросов на увеличение приоритета элементов этой кучи. Обработайте эти запросы.

Программа получает на вход число элементов в куче \(N\). Далее идет \(N\) чисел, при заполнении которыми массива подряд получается правильная куча. В третьей строке записано количество запросов \(K\). В следующих \(K\) строках даны запросы. Каждый запрос характеризуется индексом элемента в куче \(i\) и неотрицательным числом \(x\). Необходимо увеличить приоритет элемента A[i] на \(x\), затем выполнить процедуру подъема элемента. Гарантируются, что новый приоритет элемента также не равен приоритету ни одного из существующих элементов.

Для каждого запроса выведите индекс элемента в куче, на котором он оказался после подъема.

После обработки всех запросов выведите конечное состояние кучи.

6
12 6 8 3 4 7
2
4 11
2 6

0
2
15 12 14 3 6 7

SO: Очередь с приоритетами - уменьшение приоритета

Условия задачи аналогичны предыдущей, только в данном случае приоритет элемента уменьшается, после чего он опускается вниз.

Формат входных и выходных данных в этой задаче аналогичен предыдущей.

6
12 6 8 3 4 7
2
1 5
0 2

4
0
10 4 8 3 1 7

SP: Очередь с приоритетами

Требуется реализовать при помощи кучи очередь с приоритетами. Очередь поддерживает две операции: добавить элемент и удалить наибольший элемент.

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

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

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

В первой строке вводятся два числа – максимальный размер приоритетной очереди \(N\) и количество запросов \(M\).

Далее идут M строк, в каждой строке — по одному запросу. Первое число в запросе задаёт его тип, остальные числа (если есть) – пара метры запроса. Возможные типы запросов:
Тип 1 – извлечь максимальный элемент (без параметров),
Тип 2 – добавить новый элемент в очередь. Запрос имеет один параметр - целое число, которое записывается через пробел.

В ответ на запрос типа 1 следует вывести:
Если извлекать было нечего (очередь пуста), то -1.
Иначе – два числа: первое – индекс конечного положения элемента, который просеивался, после его просеивания (если же удалён был последний элемент и просеивать осталось нечего, вывести 0); второе – значение извлечённого элемента.

В ответ на запрос типа 2 следует вывести:
Если добавить нельзя (нет места, поскольку в очереди уже N элементов), то вывести -1. (При этом куча не должна измениться).
Иначе – индекс добавленного элемента.

Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.

4 7
1
2 9
2 4
2 9
2 9
2 7
1

-1
0
1
2
1
-1
1 9
9 4 9

SQ: Очередь с приоритетами с удалением

Условие этой задачи отличается от условия предыдущей лишь наличием ещё одного типа запроса – запроса на удаление заданного (не обязательно максимального) элемента. Это будет запрос типа 3 с единственным параметром, задающим индекс элемента, который требуется удалить из кучи.

В ответ на запрос типа 3 следует вывести:
-1, если элемента с таким индексом нет и удаление невозможно. (При этом куча не должна измениться).
Иначе – значение удаленного элемента.

4 10
1
2 9
2 4
2 9
2 9
2 7
1
3 3
2 1
3 2

-1
0
1
2
1
-1
1 9
-1
3
9
9 4 1

SR: Монополия

В новом варианте игры “Монополия” появилась возможность объединять несколько предприятий в одно для увеличения приносимого ими дохода. При это в игре действуют следующие правила:

1. За один ход можно объединить ровно два предприятия в одно. При этом стоимость нового предприятия равна сумме стоимостей двух предприятий до объединения.
2. За совершение операции по объединению предприятий необходимо заплатить налог в размере 5% от стоимости объединяемых предприятий.

Коля уже заработал в игре много денег и теперь хочет объединить все свои предприятия в одно. Он заметил, что общая сумма уплаченного налога зависит от того, в каком порядке будут объединяться предприятия. Например, пусть у Коли есть четыре предприятия стоимостью 10, 11, 12 и 13. Если Коля сначала объединит предприятия 10 и 11 (это обойдется ему в $1.05), потом результат - с 12 ($1.65), и затем - с 13 ($2.3), то всего он заплатит $5. Если же сначала отдельно объединить 10 и 11 ($1.05), потом - 12 и 13 ($1.25) и, наконец, объединить два полученных предприятия ($2.3), то в итоге он заплатит лишь $4.6.

Помогите Коле определить минимальную сумму денег, необходимую для объединения всех его предприятий в одно.

В единственной строке входного файла записано \(N\) натуральных чисел (\(2 \leq N \leq 200\,00\)), каждое из которых не превосходит 10000 - стоимости Колиных предприятий.

В выходной файл выведите минимальную сумму денег необходимую для объединения всех Колиных предприятий в одно.

10 11 12 13

4.60

SS: Тупики

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

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

Тупики пронумерованы числами от 1 до \(K\). Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером.

Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

В первой строке вводится число \(K\) - количество тупиков (\(1 \leq K \leq 20000\)). Далее следуют строки, описывающие события прибытия/отбытия электричек. Каждая электричка задаётся своей противоположной конечной станцией - строкой длины не более 15 из латинских букв и знаков подчёркивания. Событие +city означает, что прибывает электричка из города city, событие -city - что эта электричка отправляется обратно. Общее количество электричек, фигурирующих в условии - не более 20000, для каждой фигурирующей электрички присутствуют оба события.

Считается, что в нулевой момент времени все тупики на вокзале свободны.

Выведите по одному числу на каждую электричку - номер тупика, куда её поставят по прибытии. Если тупиков не достаточно для того, чтобы организовать движение электричек согласно расписанию, выведите в одной строке число 0, затем через пробел - название города первой из электричек, которая не сможет прибыть на вокзал.

3
+bologoe
+moscow
-bologoe
+stpetersburg
-stpetersburg
+samara
+saratov
-moscow
-samara
-saratov

bologoe 1
moscow 2
stpetersburg 1
samara 1
saratov 3

2
+kostroma
+sudislavl
+newvasyuki
-sudislavl
-kostroma
-newvasyuki

0 newvasyuki

ST: Очередь с приоритетами

Реализуйте структуру данных “очередь с приоритетами”, поддерживающую следующие операции:

1. Добавление элемента в очередь.
2. Удаление из очереди элемента с набольшим приоритетом.
3. Изменение приоритета для произвольного элемента, находящегося в очереди.

Программа получает на вход последовательность команд, по одной команде в каждой строке. Общее число команд не превосходит \(30\,000\). Команда может иметь один из следующих форматов:

ADD id priority - добавить в очередь новый элемент с идентификатором id и приоритетом priority. Гарантируется, что в очереди нет элемента с таким идентификатором.

POP- удалить из очереди элемент с наибольшим значением приоритета. Если таких элементов несколько, то удаляется один (любой) из них. Гарантируется, что очередь не пуста.

CHANGE id new_priority -- изменить значение приоритета элемента с идентификатором id на значение new_priority. Гарантируется, что в очереди есть элемент с таким идентификатором.

Идентификаторы элементов - строки, состоящие из строчных латинских букв длиной не более 10 символов. Приоритеты - произвольные целые числа.

В самом начале очередь пуста.

Для каждой команды типа POP выведите идентификатор удаленного элемента и, через пробел, значение его приоритета.

ADD one 1
ADD two 2
ADD three 3
POP
CHANGE one 5
POP
POP

three 3
one 5
two 2

Ссылочные реализации структур данных

Стек

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

push

Добавить (положить) в конец стека новый элемент

pop

Извлечь из стека последний элемент

top

Узнать значение последнего элемента (не удаляя его)

size

Узнать количество элементов в стеке

clear

Очистить стек (удалить из него все элементы)

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

Очередь

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

Дек

Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:

push_front

Добавить (положить) в начало дека новый элемент

push_back

Добавить (положить) в конец дека новый элемент

pop_front

Извлечь из дека первый элемент

pop_back

Извлечь из дека последний элемент

front

Узнать значение первого элемента (не удаляя его)

back

Узнать значение последнего элемента (не удаляя его)

size

Узнать количество элементов в деке

clear

Очистить дек (удалить из него все элементы)

Списки

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

LA: двусвязный список

Реализуйте список, элементами которого являются целые числа.

Список состоит из произвольного числа элементов. Один из элементов списка будем называть текущим. Также в качестве текущего элемента может выступать фиктивный элемент, находящийся за последним элементом списка - будем называть его концом списка. Этот фиктивный элемент нужен для того, чтобы можно было добавлять элементы в конец списка.

В самом начале список пустой, а текущим элементом является конец списка.

Список поддерживает следующие операции:

get

Вывести значение текущего элемента. Если текущим является конец списка, то вывести error.

set n

Установить значение текущего элемента в n. Вывести ok или error, если текущим является конец списка.

next

Переместиться на один элемент в сторону конца списка. Вывести значение нового текущего элемента, или end, если текущим элементом стал конец списка, или error, если текущим элементом уже был конец списка.

prev

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

insert n

Вставить новый элемент перед текущим и задать ему значение n. Новый элемент становится текущим. Программа выводит ok.

erase

Удалить текущий элемент. Программа выводит значение удаленного элемента или error, если текущим был конец списка. Текущим элементом становится элемент, следущий за текущим.

size

Программа должна вывести количество элементов в списке.

clear

Программа должна очистить список и вывести ok.

exit

Программа должна вывести bye и завершить работу.

insert 1
insert 2
insert 3
next
erase
get
set 4
prev
prev
erase
next
next
insert 5
prev
insert 6
next
erase
erase
get
size
clear
size
exit

ok
ok
ok
2
2
1
ok
3
error
3
end
error
ok
4
ok
4
4
5
error
1
ok
0
bye

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

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

Программа получает на вход последовательность натуральных чисел (типа int). Последовательность завершается число 0, которое означает конец ввода, и добавлять его в дерево не надо.

Вот пример построенного дерева для последовательности 7 3 2 1 9 5 4 6 8 0:

После построения дерева решите поставленную задачу.

LB: Высота дерева

Выведите высоту полученного дерева (реализуйте рекурсивную процедуру, возвращающую высоту дерева).

7
3
2
1
9
5
4
6
8
0

4

LC: Количество элементов

Подсчитайте количество элементов в получившемся дереве (реализуйте рекурсивную процедуру, возвращающую количество элементов в дереве).

1
2
3
1
0

3

LD: Второй максимум

Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.

7
3
2
1
9
5
4
6
8
0

8

1
1
1
2
2
2
0

1

LE: Обход

Выведите все элементы полученного дерева в порядке возрастания. Удобней это делать при помощи рекурсивной процедуры.

7
3
2
1
9
5
4
6
8
0

1 2 3 4 5 6 7 8 9

LF: Вывод листьев

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

7
3
2
1
9
5
4
6
8
0

1 4 6 8

LG: Вывод развилок

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

7
3
2
1
9
5
4
6
8
0

3 5 7

LH: Вывод веток

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

7
3
2
1
9
5
4
6
8
0

2 9

LI: Сбалансированность

Дерево называется сбалансированным, если для любой его вершины высота левого и правого поддерева для этой вершины различаются не более чем на 1. Определите, является ли дерево сбалансированным, выведите слово YES или NO.

7
3
2
1
9
5
4
6
8
0

YES

1
2
3
0

NO

LJ: Подсчет элементов

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

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

9
7
9
1
7
9
0

1 1
7 2
9 3

LK: Удаление элементов

Реализуйте процедуру удаления элементов из бинарного дерева поиска. Правила удаления следующие:

1. Если у удаляемого элемента нет потомков, то он просто удаляется.
2. Если у удаляемого элемента один потомок, то этот потомок становится на место удаляемого.
3. Если у удаляемого элемента два потомка, то на место удаляемого элемента ставится минимальный элемент из его правого поддерева.

Программа получает на вход последовательность целых чисел, заверщающаяся числом 0. При этом положительное число \(+d\) обозначает, что в дерево нужно добавить элемент со значением \(d\) (возможно, что он уже есть в дереве).

Отрицательное число \(-d\) означает, что из дерева нужно удалить элемент со значением \(d\), вполне возможно, что в дереве такого элемента нет (тогда дерево не модифицируется).

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

7
3
2
1
9
5
4
6
8
-2
-4
-7
0

1 0 0
3 1 5
5 0 6
6 0 0
8 3 9
9 0 0