Сбалансированность дерева

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

, , ,

Сбалансированным деревом называется дерево, в котором длины путей от корня до любого листового узла отличается не более, чем на 1.
Напишите функцию с приведенной сигнатурой, которая бы проверила, что дерево сбалансировано. Если нужно, можно создать вспомогательные функции.

bool is_tree_balanced(tree_node* tree_root)
{
  //ваш код
};
1 Цель задания быстрая проверка базовых знаний основных структур данных, алгоритмов и средств их реализации
2 Время выполнения 20 минут
3 Формат выполнения код пишется на компьютере или бумаге по выбору, без доступа к документации

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

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

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

  1. Можно ли ограничиться бинарным деревом?
  2. Я собираюсь использовать динамические контейнеры STL. Есть ли ограничения на их применение?

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

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

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