Суммирование элементов в дереве

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

, ,

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

C++                                           C#
struct tree_node                              public class Node
{                                             {
    tree_node* left;                             public Node Left;
    tree_node* right;                            public Node Right;
    int data;                                    public int Data;
}                                              } 

//Ваш код                                      //Ваш код

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

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

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

  1. Что значит вернуть все пути? Достаточно ли вернуть значения данных из узлов в правильном порядке или нужно вернуть указатели(ссылки) на узлы, то есть все поддерево? Или нужна новая динамическая структура с полным копированием данных и организацией собственных связей?
  2. C++: Я собираюсь использовать динамические контейнеры STL. Есть ли ограничения на их применение?
  3. C++: Я собираюсь организовать линейный односвязный список для возврата результата. Можно ли использовать для узла этого списка готовую структуру данных, оставив в ней одну из связей пустой, или создать новую структуру для этого?
  4. C#: Можно ли описать дерево в XML формате и работать с ним соответствующими средствами? Поддеревья, получаемые на выходе, при этом тоже будут выдаваться как XML.

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

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

В решении на C++ обязательно не должно быть утечек памяти.

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


Оставить комментарий

Ваш адрес email не будет опубликован.


*