如何使用python BST实现"范围"

Question

目前我的代码允许我搜索特定的节点，我想编辑它，以便我可以在数字范围内搜索。例如，我有一份苹果的价目表，我想把所有价格在2美元到4美元之间的苹果添加到列表/字典中。

这是我当前的代码

def valueOf(self, key):
    node = self._bstSearch(self._root, key)
    assert node is not None, "Invalid map key."
    return node.value
def _bstSearch(self, subtree, target):
    if subtree is None:
        return None
    elif target < subtree.key:
        return self._bstSearch( subtree.left, target)
    elif target > subtree.key:
        return self._bstSearch(subtree.right, target)
    else:    
        return subtree

我想我应该编辑目标，将其从单个项目搜索更改为范围项目搜索，但我不是100%确定如何

Answer 1

使用递归序遍历:

def range(self, a, b):
    return self._traverse_range(self._root, a, b)
def _traverse_range(self, subtree, a, b, cumresult=None):
    if subtree is None:
        return
    # Cumulative variable.
    if cumresult is None:
        cumresult = []
    # Traverse LEFT subtree if it is possible to find values in required range there.
    if subtree.key > a:
        self._traverse_range(subtree.left, a, b, cumresult)
    # Push VALUE if it is in our range.
    if a <= subtree.key <= b:  # Change to strict "< b" to act like python's range
        cumresult.append(subtree.key)
    # Traverse RIGHT subtree if it is possible to find values in required range there.
    if subtree.key < b:
        self._traverse_range(subtree.right, a, b, cumresult)
    return cumresult