Бинарное дерево минимальной высоты

Опубликовано Jan 17, 2012 в Деревья и графы | 6 коммент.

, , ,

Дан одномерный целочисленный массив. Нужно построить из его значений бинарное дерево поиска (BST) минимальной высоты. Желательно продемонстрировать использование стандартных STL контейнеров для C++. На C# постарайтесь не применять XML для описания структуры дерева.

//Структура узла
//    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:

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

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

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

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

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


Автор публикации:

6 Коммент. : “Бинарное дерево минимальной высоты”

  1. Аноним says:

    Например,

    public static Node BuildTree(int[] data)
    {
        var arr = data.ToArray();
        Array.Sort(arr);
        Func<int> Build = null;
        Build = (items, l, r) =>
            {
                if (r < l) return null;
                int medianIndex = (l + r) / 2;
                return new Node
                           {
                               Left = Build(items, l, medianIndex - 1),
                               Right = Build(items, medianIndex + 1, r),
                               Data = items[medianIndex]
                           };
            };
        return Build(arr, 0, data.Length - 1);
    }
    • Аноним says:

      Парсер кушает сигнатуры делегатов, удалите :(

      • Галина says:

        Знаем мы про эту проблему. Стараемся исправить. в связи с этим было бы хорошо, если бы вы отправили этот код, в котором пропал кусок, просто письмом на team@fulcrumweb.com.

  2. Галина says:

    Мы надеемся, что парсер больше ничего не кушает. Потерянный код найден модератором. И немного убрано лишнего – не нужны промежуточные массивы items и arr. Вот решение – оставим его, если автор не возражает.

        public static Node BuildTree(int[] data)
        {
            Array.Sort(data);
            Func<int, int, Node> Build = null;
            Build = (l, r) =>
            {
                if (r < l) return null;
                int medianIndex = (l + r) / 2;
                return new Node
                {
                    Left = Build(l, medianIndex - 1),
                    Right = Build(medianIndex + 1, r),
                    Data = data[medianIndex]
                };
            };
            return Build(0, data.Length - 1);
        }
    • Аноним says:

      Автор, разумеется, не возражает. Нужен ли промежуточный массив arr – зависит от требований к чистоте функции, а точнее от того можно ли изменять входной массив или нет. Вместо параметра лямбды “items” можно было бы использовать замыкание, но в оригинальном виде лямбду очень легко оформить в классический метод, ведь в рантайме решения с лямбда-функцией и вызовом метода все таки отличны, и может возникнуть желание переписать метод. Хотя, лямбда вызывается всего О(ln(n)) раз, так что лаконичность здесь наверняка приоритетнее быстродействия.

  3. Anonymous says:
    ...
    vector<int> numbers;
    ...
    Tree *addToBST(vector<int> numbers, int start, int end)
    {
    	if(end < start) return NULL;
    	int mid = (start + end)/2;
     
    	Tree *r = new Tree;
    	r->data = numbers[mid];
    	r->left = addToBST(numbers, start, mid-1);
    	r->right = addToBST(numbers, mid+1, end);
    	return r;
    }
     
    Tree *createMinimalBST(vector<int> numbers, int size)
    {
    	return addToBST(numbers,0,size-1);
    }
    ...
    sort(numbers.begin(), numbers.end());
    Tree *newRoot = createMinimalBST(numbers,numbers.size());

    Вот еще один вариант, взят из книги, но вместо массива – вектор используется.

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

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


*