Восстановление бинарного дерева

Опубликовано Sep 30, 2011 в Деревья и графы | Нет комментариев


Дан отсортированный массив типа int. Напишите функцию, которая бы создала отсортированное бинарное дерево (BST-дерево) минимальной глубины из элементов этого массива.

struct tree_node {
           tree_node* left;
           tree_node* right;
           int data;
        };
tree_node* add_to_tree(const int* arr, int start, int end)
{
    //ваш код
}
1 Цель задания быстрая проверка базовых знаний основных структур данных и алгоритмов, средств их реализации
2 Время выполнения 20 минут
3 Формат выполнения код пишется на компьютере или бумаге по выбору, без доступа к документации

Критерии оценки FulcrumWeb:

Нужно продемонстрировать знание стандартных приемов работы с бинарными деревьями.

Ожидаемые вопросы:

  1. Что за дерево должно получиться на конкретном примере входного массива?

Оценка результатов:

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

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