Генерация тестовых случаев | Набор 6 (случайное невзвешенное двоичное дерево)

Создание случайного невзвешенного двоичного дерева :

• Поскольку это дерево, план генерации тестовых данных таков, что цикл не формируется.
• Количество ребер на единицу меньше количества вершин.
• Для каждого RUN сначала выведите количество узлов, скажем, N , а следующие N – 1 строк имеют форму (a, b), где a является родителем b.
• Каждый узел содержит не более 2 детей.

Подход: Проблема может быть решена с помощью Queue. Идея состоит в том, чтобы пройти по дереву с помощью BFS. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте карту, скажем, mp , чтобы проверить, включен ли узел в дерево или нет.
• Инициализируйте очередь для хранения узлов на каждом уровне дерева.
• Считайте 1 корневым узлом и вставьте его в очередь.
• Перебирать очередь, пока общее количество узлов в дереве не равно N . На каждой итерации вставляйте отдельные узлы каждого уровня дерева в очередь, используя функцию rand() и карту, а также вставляйте узел и родителя узла в массив
• Наконец, выведите значение N и массив.