Вставить элементы в массив из заданного диапазона на BST - PullRequest
Новая
       13

Вставить элементы в массив из заданного диапазона на BST

0 голосов
/ 14 мая 2018

Таким образом, я должен вставить элементы из BST, которые попадают в заданный диапазон, в список. Проблема, с которой я сталкиваюсь, заключается в том, что элемент вставляется только в том случае, если root->elem находится в диапазоне. Если это не очевидно, это не вставлено. Вот код: 

template<typename E, typename F>
ListArray<E> BinarySearchTree<E,F>::findRange(E min, E max) {

ListArray<E> elems;
if (isEmpty()) {
    return elems;
}
if(inRange(root->elem,min,max)){
    elems.insertLast(root->elem);
    root->left.findRange(min,max);
    root->right.findRange(min,max);
} else {
    if(root->elem < min){
        root->right.findRange(min,max);
    } else if (root->elem > max){
        root->left.findRange(min,max);
    }
}

return elems;
}

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

Заранее спасибо.

EDIT:

Используя функцию конкатенации (которая также была мне предоставлена), я смог вернуть список из рекурсии и объединить его с «первым» без необходимости использования лямбда-выражений или частных функций.

Код следующий: 

template<typename E, typename F>
ListArray<E> BinarySearchTree<E,F>::findRange(E min, E max) {
    ListArray<E> elems;
    if (isEmpty()) {
        return elems;
    }
    if(inRange(root->elem,min,max)){
        elems.concat(root->left.findRange(min,max));
        elems.insertLast(root->elem);
        elems.concat(root->right.findRange(min,max));
    } else {
        if(root->elem < min){
            elems.concat(root->right.findRange(min,max));
        } else if (root->elem > max){
            elems.concat(root->left.findRange(min,max));
        }
    }
    return elems;
}

Обратите внимание, что если элемент находится в диапазоне, я сначала вызываю функцию concat(...) перед вставкой элемента. Таким образом, элементы отображаются в порядке возрастания.

Функция concat() выглядит следующим образом: 

template<typename E, int N>
void ListArray<E,N>::concat(const ListArray<E,N>& l) {
    if (this->length() + l.length() > N) {
        throw MyException("The list is empty");
    }
    for (int i=0;i<=l.lastIndex;i++) {
        insertLast(l.storage[i]);
    }
}

Чтобы завершить это, реализация BST выглядит следующим образом: 

template<typename E, typename F>
class BinarySearchTree {
public:
    //All the different methods   
    ListArray<E> findRange(E min, E max);    
private:
    struct Node {
        E elem;
        BinarySearchTree<E,F> left;
        BinarySearchTree<E,F> right;
    };

    Node *root;
    F compare;
    //Some private functions
    bool inRange(E num, E min, E max);
};

1 Ответ

0 голосов
/ 14 мая 2018

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

template<typename E, typename F>
class BinarySearchTree {
    /*Whatever else is implemented*/
private:
    void findRange_impl(ListArray<E> & elems, E min, E max) {
        if (isEmpty()) {
            return;
        }
        if(inRange(root->elem,min,max)){
            elems.insertLast(root->elem);
            root->left.findRange_impl(elems, min, max);
            root->right.findRange_impl(elems, min, max);
        } else {
            if(root->elem < min){
                root->right.findRange_impl(elems, min, max);
            } else if (root->elem > max){
                root->left.findRange_impl(elems, min, max);
            }
        }
    }

public:
    ListArray<E> findRange(E min, E max) {
        ListArray<E> elems;
        findRange_impl(elems, min, max);
        return elems;
    }
};

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

РЕДАКТИРОВАТЬ:

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

template<typename E, typename F>
ListArray<E> BinarySearchTree<E,F>::findRange(E min, E max) {
    ListArray<E> elems;

    struct Inner {
        ListArray<E> & elems;
        E min, max;
        Inner(ListArray<E> & elems, E min, E max) : elems(elems), min(min), max(max) {}
        void findRange_impl(BinarySearchTree<E,F> * node) {
            if (node->isEmpty()) {
                return;
            }
            if(inRange(node->elem,min,max)){
                elems.insertLast(node->elem);
                findRange_impl(node->left);
                findRange_impl(node->right);
            } else {
                if(node->elem < min){
                    findRange_impl(node->right);
                } else if (node->elem > max){
                    findRange_impl(node->left);
                }
            }
        }
    };
    Inner inner(elems, min, max);
    inner.findRange_impl(root);
    return elems;
}

Насколько я знаю, не должно быть никаких [языковых / технических] ограничений для написания такого кода.

...