Remote Training on Programming

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

Вставка нового элемента x в дерево начинается с корневого узла. Сравним x с ключом в корне. Если они равны, то делать ничего не надо – вставка закончена. Если x меньше ключа в корне, то идём в левое поддерево, если больше – в правое. Продолжаем делать так до тех пор, пока идти станет больше некуда – в этом случае создаём новый листовой узел.

На рисунке показано дерево, полученное из пустого дерева после вставки элементов 8, 5, 7, 11, 9, 3, 6.

Все узлы дерева можно разбить на уровни. Корень лежит на уровне ноль. Его дети лежат на уровне 1, их дети – на уровне 2, и так далее.

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