c++ - 从 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 表达式或私有(private)函数。

代码如下:

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

创建一个私有(private)实现函数，让您通过对每个递归调用的引用传递数组。

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 变量是否在树的每个级别正确更新，但我假设这是一个偶然事件您的代码已经说明了这一点。

编辑:

鉴于无法对类标题进行编辑(这告诉我你的讲师只是 super 致力于教授糟糕的设计原则)，我们需要在你的函数中定义一个本地类来给我们一个内部函数我们可以递归。

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

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