二叉搜索树(BST)指定范围元素提取至数组的问题及解决

你的判断完全正确——原代码的核心问题就是没有将递归调用返回的列表合并到结果中，导致只有当前符合范围的节点被加入列表，递归遍历左右子树找到的元素全部被丢弃了。下面是完整的修复方案：

问题分析 #

原代码的关键错误点：

• 调用root->left.findRange(min,max)和root->right.findRange(min,max)时，仅执行了方法但未处理返回的ListArray，递归结果完全丢失
• 当当前节点不在范围内时，同样只是触发了递归调用，但没有把递归得到的有效元素合并到结果列表

修复后的代码 #

我们可以借助ListArray提供的concat方法，将递归返回的列表直接合并到当前结果中，同时保持BST元素的升序输出（中序遍历顺序）：

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

关键说明 #

• 当当前节点在范围内时，先合并左子树结果、再插入当前节点、最后合并右子树结果，这完全对应BST的中序遍历，能保证输出的元素是升序排列的
• 所有递归调用的结果都通过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 full"); // 原注释有误，修正为更合理的提示
    } 
    for (int i=0;i<=l.lastIndex;i++) { 
        insertLast(l.storage[i]); 
    } 
}

BST类结构 #

template<typename E, typename F> 
class BinarySearchTree { 
public: 
    // 其他方法省略
    ListArray<E> findRange(E min, E max); 
private: 
    struct Node { 
        E elem; 
        BinarySearchTree<E,F> left; 
        BinarySearchTree<E,F> right; 
    }; 
    Node *root; 
    F compare; 
    // 私有辅助函数
    bool inRange(E num, E min, E max); 
};

内容的提问来源于stack exchange，提问作者Oscar Nydza