将元素插入BST上给定范围的数组中

Question

所以我必须将属于给定范围的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，因为我被迫使用模板。我想它必须与我没有从任何递归情况返回列表的事实有关，但我不知道如何正确地做到这一点。

提前致谢。

编辑：

使用连接函数（也给了我）我能够从递归中返回列表并将其与“第一个”连接起来，而不需要lambda表达式或私有函数。

代码如下：

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);
};

Answer 1

创建一个私有实现函数，它允许您通过引用每个递归调用来传递数组。

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;
}

据我所知，编写这样的代码不应该有任何[语言/技术]限制。